2014-10-29

posted Oct 29, 2014, 4:59 AM by Samuel Konstantinovich   [ updated Oct 29, 2014, 6:20 AM ]
;Goal: Practice with lists.
;There are parts A,B,C

A. Do Now/mini Lab:

;Consider this incomplete reverseList:

(define (reverseList L)
  (cond
    ((null? L) L)
    (else             ???)))

;Hint for people that had problems:
;Conceptually, pretend there is a built in function that does what you want this 
;function to do, except not on the entire list.

;1 Given a list L, how would you use the functions below to create L in reverse? 
;(car x)
;(cdr x)
;(reverseList x) ; where you cannot use reverse on ALL of L.
;Now complete reverseList!

(reverseList '(1 2 9 5 0) )  -> (0 5 9 2 1)
(reverseList '(1 2 (9 5) 0) )  -> (0 (9 5) 2 1)

;2. Complete the function (reverseListSub L) that not only reverses the top level 
;elements, but will go inside sublists and reverse those as well.
(reverseListSub '(1 2 9 5 0) )  -> (0 5 9 2 1)
(reverseListSub '(1 2 (9 5) 0) )  -> (0 (5 9) 2 1)
(reverseListSub '(1 (2 (9 5)) 0) )  -> (0 ((5 9) 2) 1)


B. Practice Problems 
-You will have time to work on these tomorrow, you should start them now. 
-AT LEAST read the problems and think about them at home, or better yet work on some of them. 

1. Write a function (addAllPos L) that calculates the sum of all the values of a list of integers L, but add the positive value of a  number if it is negative. This should work if L has sublists.
Examples: 
(addAllPos '(-1 1)) is 2   
(addAllPos '(-3 (-4 -5) 3)) is 15

2. Write a function (sumAtoB a b) that takes two integers a and b such that a < b. The function adds all integers from a to be inclusive.
(sumAtoB 1 3) -> 6
(sumAtoB 1 4) -> 10
(sumAtoB 2 4) -> 9
(sumAtoB 10 12) -> 33

2b. Make it better and allow for a<b  and a > b.

3. Write a function (hasSublists? L) that returns true when any of the top level elements of L are lists. 

(hasSublists? '( 2 3 4))  -> #f
(hasSublists? '( 2 (3) 4)) -> #t
(hasSublists? '( )) -> #f
(hasSublists? '( () )) -> #t


4. Write a function (countEmpty L) that counts the number of empty lists are contained in a list L which may have sublists.
(countEmpty '( 3 2  ( ) ( ) ) is 2
(countEmpty '( 2 (9 ( ) ( ) ) ( ) ) ) is 3
(countEmpty '() ) is 0

;5 Trace practice
;Assume L cannot be an empty list or contain any empty lists
(define (what L)
  (cond
    ;First two cases process sublist
    ((and (list? (car L)) (null?(cdr L)))   (what (car L)))
    ((list? (car L))   (max (what (car L)) (what (cdr L))))
    ;second two cases process non-sublists
    ((null?(cdr L))   (car L)) 
    (else      (max (car L) (what (cdr L))))))
;Trace through the following:  (verify on a computer)
(what '( 12 (14 ( 2) ) 3))


C. CHALLENGES:

We write numbers in decimal (also known as base 10). Computers only store/process data using binary numbers (base 2). There are many other useful number bases that we use every day, base 60 is used in clocks, base 16 is used by many artists when naming colors on a computer. You should learn more about these bases, but the topic has been eliminated from school entirely. 

These problems require that you learn to convert numbers into different bases. You must understand the algorithms before you start writing the code. I don't expect you to come up with the algorithm on your own, but I do expect you to implement it yourself. You should wiki/google number base conversion to get an idea of how it works before attempting the examples. 

;;;PART A, basic conversion

1. Write a function binary to decimal:
;(btod x)    
;precondition:
;x must be an integer that consists of 1's and 0's
;that represents a binary number
;postcondition
;the value returned is the decimal equivalent of the 
;binary number x
(btod 1000) is 8
(btod 1001) is 9
(btod 10010) is 18
(btod 11110) is 30

2. Write a function to convert decimal to binary:
;(dtob x)
;precondition:
;x is any integer
;postcondition:
;the value returned is an integer that consits of 0's and 1's
;that represents a binary number equivalent to x
(dtob 10) is 1010
(dtob 8) is 1000
(dtob 13) is 1101
(dtob 50) is 110010

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;PART B, any base conversion
;You can easily convert your functions to work with any base 10 or lower:

3. Write a function base N to decimal
;(ntod x n)
;precondition:
;x must be an integer that consists of digits that are strictly less than n.
;the digits of x represent a base n number
;n <= 10
;postcondition
;the value returned is the decimal equivalent of the number x

base 3 examples:
(ntod 100 3) is 9
(ntod 101 3) is 10
(ntod 110 3) is 12

base 4 examples:
(ntod 100 4) is 16
(ntod 101 4) is 17
(ntod 212 4) is 38

4. Write a function decimal to base N
;(dton x n)
;precondition:
;x is any integer
;postcondition:
;the value returned is an integer that consits of digits strictly less than n
;that represents a base n equivalent to x

base 3 examples:
(dton 9 3) is 100
(dton 10 3) is 101
(dton 12 3) is 110

base 4 examples
(dton 16 4) is 100
(dton 17 4) is 101
(dton 36 4) is 210

5. Write a function that converts from base N to base M:
(ntom x n m)
example:
(ntom 1000 2 3)  is 22.
This means take the binary number 1000, and convert it to base 3. 
We need to use decimal as a middle step: 1000 is 8 in decimal, 8 in decimal is 22 in base 3.

How can you test this function? 
Come up with test cases that you know the answer to!


;;;PART C, advanced conversion
;
;How do we handle number bases higher than 10?!?!?
;We will use lists instead of integers to store the digits:
;in base 16, 13AF is a number, A stands for 10, F stands for 15... but we cannot write
;that way in an integer, instead we will write it as: '( 1 3 10 15)  

6. Improve your dton to give a list of digits as follows:
(dToAnyN x n)
;precondition:
;x must be an a list of numbers each strictly less than 10.
;postcondition
;the value returned is the base N equivalent of the number stored in list x.
(dToAnyN 13 2) -> ( 1  1  0  1)
(dToAnyN 36 4) -> ( 2  1  0 )
;now hex examples:
(dToAnyN 15 16) -> ( 15 )  
(dToAnyN 16 16) -> ( 1  0 )
(dToAnyN 33 16) -> ( 2  1 )
(dToAnyN 63 15) -> ( 3 15 )


7. improve your ntod to take a list of digits as follows:
(anyNtoD x n)
;precondition:
;x must be a list of integers each strictly less than n
;postcondition
;the value returned is the decimal equivalent of the number stored in list x. 
(anyNtoD '(1 1 0 1) 2) -> 13
(anyNtoD '(1 1 0 1) 3) -> 37 
(anyNtoD '(3 15) 16)  -> 63


Comments