Foundations of Computer Science
Fall 2007

For today you should have:

1) read from Sipser and answered the questions in notes03

2) finished off the examples from notes01 and notes02

3) started on the symbolic differentiator


For next time you should:

1) finish the symbolic differentiator

2) do the "Scheme challenges" below

3) bring hardcopies of your solutions to (1) and (2)

4) read from Sipser and answer the questions below


Some Scheme challenges
----------------------

Credits: the following two exercises are from Lynn Stein's
most recent implementation of FOCS

1) Write a procedure called 'repeatedly that takes two arguments --
   f', a procedure of one argument, and 'n, a number of times to apply
   'f -- and returns a function of one argument that applies 'f 'n
   times.

(define incr
   (lambda (x) (+ 1 x))) 

((repeatedly incr 3) 6) 
 9


For each of the following expressions, try to compute
the value in your head, then run it and check:

a) ((repeatedly (lambda (x) (* x x)) 3) 2)
   
b) ((repeatedly (repeatedly 1+ 4) 5) 200)



2) Write a procedure called 'repeatedly-until that takes a procedure
   'f of one argument and a procedure 'until of one argument, and
   returns a function of one argument that repeatedly applies 'f until
   (until x) evaluates to true (where x is the result of applying
   f).  The function returned by 'repeatedly-until should return
   the value of x that make (until x) true.

((repeatedly-until incr (lambda (x) (= (remainder x 10) 0))) 346)
350




Reading questions
-----------------

Sipser, pages 17-27

1) In what ways is finding a proof similar to writing a program?




2) In what ways is it different?




3) On page 22, Example 0.23 is an example of proof by contradiction
   applied to everyday thinking.

   Can you think of examples where proof by construction or proof
   by induction are used in everyday thinking?




4) How is Example 0.23 different from a mathematical proof?




5) How is proof by induction similar to writing a recursive
   function?  How is it different?




6) Do problem 0.10 on page 27.




7) Do problem 0.11 on page 27.




8) Do problem 0.12 on page 27.



Solutions
---------

; FOCS Homework 1 Solutions
; Fall 2007
; Allen Downey

; NOTE: the tests below are WILDLY inadequate for anything like
; reasonable testing.  Do not follow my example!


; append: takes lists a and b and returns a list that contains the elements
; of a followed by the elements of b
(define (append a b)
  (if (null? a) b
      (cons (car a) (append (cdr a) b))))

(append (list 1 2 3) (list 4 5 6))

; reverse: takes a list a and returns a list that contains the elements
; of a in reverse order
(define (reverse a)
  (define (iter a b)
    (if (null? a) b
        (iter (cdr a) (cons (car a) b))))
  (iter a '()))

(reverse (list 1 2 3))

; deep-reverse: takes a list a and returns a list that contains the elements
; of a in reverse order, with each of the elements also deep-reversed
(define (deep-reverse a)
  (define (iter a b)
    (cond ((null? a) b)
          ((pair? a) (iter (cdr a) (cons (deep-reverse (car a)) b)))
          (else a)))
  (iter a '()))

(deep-reverse (list '(1 2 3) '(4 5 6) '(7 8 9)))

; leaves: takes a tree and returns a list of the leaf elements, in preorder
(define (leaves t)
  (define (iter t s)
    (cond ((null? t) s)
          ((pair? t) (iter (car t) (iter (cdr t) s)))
          (else (cons t s))))
  (iter t '()))

(leaves (list 1 2))

(define tree (cons (cons 1 2)
                   (cons 3 4)))

(leaves tree)

(define tree2 (list '(5 6 7) '() tree))

(leaves tree2)