### Announcements

#### S6. Final list practice problems + Solutions

posted Nov 8, 2012, 6:16 AM by Samuel Konstantinovich   [ updated Nov 15, 2012, 5:13 AM ]

 1. Write a function (duplicate L) that makes a second copy of every item of the list. (assume no sublists)Example: (duplicate '(1 3 9 2 4)) -> (1 1 3 3 9 9 2 2 4 4)2. 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 153. 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 04. Write a function (clear L x) that deletes all of the elements of a list L that are smaller than x. This should work if L has sublists.;Example:;(clear '(3 9 2 4 (1 9 4)) 5)  is (9 (9));(clear ;(1 2 (5 6) (1 2) 6) 4) is (( 5 6)()6)SOLUTIONS:(define (duplicate L)  (if (null? L)   ;you can use if or cond      L       (cons (car L)(cons (car L) (duplicate (cdr L))))))(define (addAllPos L)  (cond    ((null? L) 0)    ((list? (car L)) (+ (addAllPos (car L))(addAllPos (cdr L))))    (else (+ (abs (car L))(addAllPos(cdr L))))))(define (countEmpty L)  (cond    ((null? L) 0)    ((null? (car L))(+ 1 (countEmpty (cdr L))))    ((list? (car L))(+ (countEmpty (car L))(countEmpty (cdr L))))    (else (countEmpty (cdr L)))));EDIT:  changed > to  >= (define (clear L x)  (cond     ((null? L) L)    ((list? (car L)) (cons (clear (car L) x)(clear (cdr L) x)))    ((>=(car L) x) (cons (car L) (clear (cdr L) x)))    (else (clear (cdr L) x))))

#### S5. Quiz2 Solutions

posted Oct 29, 2012, 8:39 AM by Samuel Konstantinovich   [ updated Nov 15, 2012, 5:13 AM ]

#### S4. Test 2 Solutions

posted Oct 19, 2012, 6:10 AM by Samuel Konstantinovich   [ updated Nov 15, 2012, 5:13 AM ]

 ;Continue working on labs 4-6. ;Lab4: skip maxHail if you get stuck;Lab5: if getNth is too tricky, try length first. ;Lab6: after you can differentiate between cons/append;      try writing functions:  ;      a. (reverse L)  hint: use append;      b. (removeNth L n) deletes the value at the nth position;             if the n is longer than the list then return the list;      c. (insertNth L n value)  places the value in the list ;            at the nth position. If the n is longer than the list ;            place the value at the end of the list. ;SAMPLE SOLUTIONS to test problems ;Between(define (between x a b)  (or (and (< x a) (> x b))      (and (> x a) (< x b))))(define (between x a b)  (or (< a x b) (< b x a)))  ;Sum of Squares:(define (sumOfSquares n)  (if (= n 0) 0 (+ (* n n) (sumOfSquares (- n 1)))));CountDigitsMoreThan:;useful function to help(define (singleDigit? n)   (= 0 (quotient n 10)));naive solution: extra booleans;positive side effect: you can change the order of the cond ;without breaking the function(define (countDigitsMoreThan n v)  (cond    ( (and (< n v)  (singleDigit? n)) 0)    ( (and (> n v)  (singleDigit? n)) 1)    ( (and (< n v) (not (singleDigit? n))) (countDigitsMoreThan (quotient n 10)v))    ( (and (> n v) (not (singleDigit? n))) (+ 1 (countDigitsMoreThan (quotient n 10)v)))));Standard solution: 4 way cond statement(define (countDigitsMoreThan n v)  (cond    ( (and (> n v) (singleDigit? n)) 1)    ( (singleDigit? n) 0)    ( (> (remainder n 10) v) (+ 1 (countDigitsMoreThan (quotient n 10)v)))    ( else  (countDigitsMoreThan (quotient n 10)v))));Insightful Solution: 3 way cond statement(define (countDigitsMoreThan n v)  (cond    ( (and (> n v) (singleDigit? n)) 1)    ( (singleDigit? n) 0)    ( else (+             (countDigitsMoreThan (remainder n 10)v)            (countDigitsMoreThan (quotient n 10)v)))));(countDigitsMoreThan 12345679 0);(countDigitsMoreThan 12345679 2);(countDigitsMoreThan 12345679 3);SumSequence  1  -1/2   1/3   -1/4    1/5   -1/6     1/7    -1/8  .... (sumSequence n)  (cond    ((= n 1) 1)    ((even? n) (+ (/ -1 n) (sumSequence (- n 1))))    (else      (+ (/ 1 n) (sumSequence (- n 1))))));(newline);(* 1.0(sumSequence 1));(* 1.0(sumSequence 2));(* 1.0(sumSequence 3));(* 1.0(sumSequence 4))

#### S3. Recursion notes/problems

posted Oct 10, 2012, 6:18 AM by Samuel Konstantinovich   [ updated Nov 15, 2012, 5:12 AM ]

 ;Numerical Recursion Wrap Up:;The tools we used with recursion so far:;A. generate a sequence of numbers, ;   -incrementing with + or - (count uses + or - 1);   -fibonacci like patterns;   -other patterns halving/doubling/etc.  ;B. separate an integer digit by digit;   -remainder by 10 gives the last digit;   -quotient by 10 gives the rest of the number ;;Now decide what do you do with all those values? ;Do you add/multiply them all together?;Do you add/multiply some of them?;C. Iterative solutions (formerly head recursion);   -Keeps the answer partly done as you go along;   -More challenging conceptually;   -This topic is going to be an extra credit topic;    (on the last scheme exam, and the final exam);More recursive Problems: (easy/medium/hard);1. (sumOddDigits n) ;   this adds all of the digits that are odd, ignores the rest ;   (sumOddDigits 12345) -> 9  because you add the 1 3 and 5 only.;2. lets analyze the fib function regular recursion we started with (see below):(define (fib n)  (cond    ((= n 0 ) 0)    ((= n 1 ) 1)    (else (+ (fib (- n 2))(fib(- n 1))))));assume each comparison (=) costs \$0.01;assume each + or - costs \$1.00;(fibcost 0) is 0.01, because fib would use the 1st =;(fibcost 1) is 0.02, because fib used the 1st and 2nd =;(fibcost 2) fib uses both ='s, then uses + and two -'s, and calls more fibs.; this means the cost of fib2 is the cost of fib2, PLUS the cost; of the other two fib calls. This means the fibcost function; grows like the fib sequence grows. (Write some costs out on paper!); This requires some thinking and writing out on paper;CHALLENGE:;3.(reverseDigits n) n is any integer (requires exponents, and numdigit) this is more challenging;   (reverseDigits 123) -> 321  ;   (reverseDigits 32451) -> 15423;SOLUTIONS TO 2 and 3:(define (fibcost n)  (cond    ((= n 0) .01)    ((= n 1) .02)    (else (+ 3.02 (fibcost (- n 1))(fibcost(- n 2))))))(display "fibcost(3)=")(fibcost 3)(display "fibcost(4)=")(fibcost 4)(display "fibcost(5)=")(fibcost 5);3 CHALLENGE PROBLEM:(define (len x)  (if (< x 10) 1 (+ 1 (len (quotient x 10)))))(define (MyReverse x)  (if (=(quotient x 10)0)      x      (+ (* (remainder x 10)            (expt 10 (- (len x)1) ))         (MyReverse (quotient x 10)))))(display "reverse(51234)=")(MyReverse 51234);Iterative challenge problem (no exponents!)(define (reverseIterative x)  (helpRev x 0))(define (helpRev  x s)  (if (= x 0)      s      (helpRev  (quotient x 10) (+ (remainder x 10)(* 10 s)))))(display "reverse(5123114)=")(reverseIterative 5123114)

#### S2. Sample Recursive Functions

posted Oct 9, 2012, 5:22 AM by Samuel Konstantinovich   [ updated Nov 15, 2012, 5:12 AM ]

 ;a divisible function to help write other functions(define (divisible?  a b)  (= 0 (remainder a b)));a different way of writing your own gcf;it doesn't check all integers for divisibility(define (gcf a b)  (if (= b 0)      a      (gcf b (remainder a b))));a different way of writing prime using gcf or divisible ;in the help function(define (prime? n)  (primehelp n 2))(define (primehelp n x)  (cond    ((>(gcf n x) 1) #f);ALTERNATE:  ((divisible n x) #f)    ((> x (sqrt n)) #t)    (else (primehelp n (+ x 1)))));improved sum function with if statement;to check the order of the terms. This;allows you to put two integers in ANY order;and still calculate the sum correctly;Regular recursive sumAtoB:(define (sumAtoB a b)  (if (> b a)      (helpsumab a b)      (helpsumab b a)))(define (helpsumab a b)  (if (> a b)      0      (+ a (helpsumab (+ a 1) b))));ITERATIVE SOLUTION to sumAtoB:(define (sumAtoB a b)  (if (> b a)      (itrsumab a b 0)      (itrsumab b a 0)));headsumab is the helper for (sumAtoB)(define (itrsumab a b s)  (if (> a b)      s     (itrsumab (+ a 1) b (+ s a))))

#### 1. Homework Policies

posted Oct 8, 2012, 4:18 PM by Samuel Konstantinovich   [ updated Oct 10, 2012, 6:18 AM ]