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 15

3. 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


4. 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 ]

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;FIRST VERSION
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define U '( (3 15) 2 (1 (0 4) 32 ) 7 ))      
;1. How many top level elements are in list U?
;4

;2. What is (car U)?
;(car U) is (3 15)

;3. What is (caddr U)?
;(caddr U) is (1 (0 4) 32)

;4. Write an expression to get 15 from list U.
;(cadar U) gives 15.

;5. Write an expression that would get 0 from list U.
;(caadar(cddr U)) gives 0

(define (g x y)
  (cond 
    ((null? y) x)
    (else 
       (cons (car y) (g x (cdr y))))))
;6. Using the function g defined above trace and evaluate:
;(g '( 1 3 6) '(4 5 8) )
;(cons 4( g (1 3 6)(5 8)) 
;            (cons 5( g (1 3 6)(8)) 
;                       (cons 8( g (1 3 6)()) 
;                                   (1 3 6)
;
;The end result is (4 5 8 1 3 6)

;7. Write a function (change P x)that takes a list of integers P and an integer x,
;and doubles any of the list’s values that are divisible by x
(define (change P x)
  (cond
    ((null? P) P)
    ((list? (car P)) (cons (change (car P) x)(change (cdr P) x)))
    ((= 0(remainder (car P) x)) (cons (* 2 (car P)) (change (cdr P) x)))
    (else (cons (car P)(change (cdr P) x)))))
;(change '( 4 15 11 3 0) 3)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;SECOND VERSION
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define P '( (13 9 1) (5 (7 2) 4 ) 40 ) )  ;[Use this list for 1-5]
;1. How many top level elements are in list P?
;3 top level elements

;2. What is (car P)?
;(car P) is (13 9 1) 

;3. What is (cadadr P)?
;(cadadr P) is (7 2)

;4. Write an expression that would get 1 from list.P.
;(caddar P) gives 1.

;5. Write an expression that would get 2 from list P.
;(cadr(cadadr P)) gives 2

(define (f a b)
  (cond 
    ((null? a) b)
    (else (cons (car a) (f (cdr a) b)))))

;6. Using the function f defined above evaluate:
;(f '( 3 9 1) '(5 8 7) )
;(cons 3 (f (9 1)(5 8 7))
;            (cons 9 (f (1)(5 8 7))
;                     (cons 1 (f ()(5 8 7))
;                                  (5 8 7)
;
;end result is (3 9 1 5 8 7)


;7. Write a function (change P x) that takes a list of integers P
;and an integer x, and negates any of the list’s values that are
;multiples of x
(define (change P x)
  (cond
    ((null? P) P)
    ((list? (car P)) (cons (change (car P) x)(change (cdr P) x)))
    ((= 0(remainder (car P) x)) (cons (- (car P)) (change (cdr P) x)))
    (else (cons (car P)(change (cdr P) x)))))
;(change '( 4 15 11 3 0) 3)

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 ]

General:
1. Unless otherwise specified your homework should be written with the assistance of a computer. You should run/test/re-test any homework you do.
2. If you are told to bring in homework to class it should be printed and brought with you. 
3. All homework should have your name and period and date on it. This should be at the top of your code, or the top of the printed page. It should be printed on a printed page, not handwritten as an afterthought. 

Homework Server specific:
H1. Your assignment must RUN. It is much better to get the wrong answer than it is to have your function crash when someone runs it. 
H2. Your function names must match mine. 
H3. It is better to submit homework a day late than have nothing work. 
H4. The student Menu on the homework server has 4 critical sections that you must use:
    a. Profile: must be filled out with your correct email address, and any nickname you want to be called in class.
    b. Grades: should be verified any time you get a test back. This is to prevent an error in copying the numbers to the computer. It is your responsibility to check this in a timely manner. Do not wait until the last week of class to tell me there are mistakes. 
    c. Submit Homework: It is important to select the correct assignment before submitting your homework. Failure to do so can cause old assignments to be erased, and no credit being given to either.  The comments here are meant for you to tell me anything specific about your submission. Do not ask questions here, as they are only read when assignments are checked. 
    d. View Homework: This is how you verify that you submitted things to the correct location. It is also a record of all homework that you submitted. This is also how you view comments if you did something wrong.

Scheme Specific:
S1. You must have a working copy of DrRacket at home. If it does not work, you must fix it before you do anything else.
S2. Homework should be done using R5RS unless you are instructed otherwise. 
S3. When solutions are posted, you should compare to what you wrote. If you handed in a hard copy, you should still have the rkt file at home to check.

1-6 of 6