CS 61A		Week 2		Lab and Homework Solutions


FIRST LAB:

1.  How to reverse the order in which coins are tried?

One solution is to reverse the order of the numbers in FIRST-DENOMINATION:

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 50)
	((= kinds-of-coins 2) 25)
	((= kinds-of-coins 3) 10)
	((= kinds-of-coins 4) 5)
	((= kinds-of-coins 5) 1)))

Another would be, using the original version of first-denomination, to
change COUNT-CHANGE and CC so that the variable KINDS-OF-COINS counts
upward instead of downward:

(define (count-change amount)
  (cc amount 1))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
	((or (< amount 0) (> KINDS-OF-COINS 5)) 0)     ; changed here
	(else (+ (cc (- amount
			(first-denomination kinds-of-coins))
		     kinds-of-coins)
		 (cc amount
		     (+ KINDS-OF-COINS 1))))))         ; changed here


2.  Explore the efficiency.  Here is what happens with (cc 5 2) in the
original order, as in the book:

> (cc 5 2)
"CALLED" cc 5 2
 "CALLED" cc 0 2
 "CALLED" cc 5 1
  "CALLED" cc 4 1
   "CALLED" cc 3 1
    "CALLED" cc 2 1
     "CALLED" cc 1 1
      "CALLED" cc 0 1
      "CALLED" cc 1 0
     "CALLED" cc 2 0
    "CALLED" cc 3 0
   "CALLED" cc 4 0
  "CALLED" cc 5 0
2

(I've deleted the "RETURNED" lines in the trace; it's easier to read this
way and doesn't affect our analysis.)

To try out just pennies and nickels backwards, I modified first-denomination
this way:

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 5)
	((= kinds-of-coins 2) 1)))

And here are the results:

> (cc 5 2)
"CALLED" cc 5 2
 "CALLED" cc 4 2
  "CALLED" cc 3 2
   "CALLED" cc 2 2
    "CALLED" cc 1 2
     "CALLED" cc 0 2
     "CALLED" cc 1 1
      "CALLED" cc -4 1
      "CALLED" cc 1 0
    "CALLED" cc 2 1
     "CALLED" cc -3 1
     "CALLED" cc 2 0
   "CALLED" cc 3 1
    "CALLED" cc -2 1
    "CALLED" cc 3 0
  "CALLED" cc 4 1
   "CALLED" cc -1 1
   "CALLED" cc 4 0
 "CALLED" cc 5 1
  "CALLED" cc 0 1
  "CALLED" cc 5 0
2

We get the same answer, but with 21 calls to CC instead of 13.  Why?
The extra calls are for attempts to match a small amount of money
with a large coin -- for example, to use a nickel in counting
four cents.  When the coins are tried in the book's order, by the
time we are thinking about four cents, we have already abandoned
the idea of using nickels and so we quickly find the four-pennies
solution.  But in backward order, we have to discover that a nickel
is too big for four cents, and then that a nickel is too big for
three cents, and so on.  (These situations give rise to the calls
with a negative amount of money; notice that there aren't any like that
in the first trace.)


3.  Modify CC to take a sentence of denominations.

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
	((or (< amount 0) (EMPTY? KINDS-OF-COINS)) 0)
	(else (+ (cc (- amount (FIRST KINDS-OF-COINS))
		     kinds-of-coins)
		 (cc amount (BUTFIRST KINDS-OF-COINS))))))


4.  type-checking

(define (type-check fn pred? value)
  (if (pred? value)
      (fn value)
      #f))


5.  build type-checking into function

(define (make-safe fn pred?)
  (lambda (value)
    (if (pred? value)
	(fn value)
	#f)))

--------------------------
SECOND LAB (front page)

Problem 1:

f	Any definition at all will do:
		(define f 'hello)		f is  hello
		(define f (+ 2 3))		f is  5
		(define (f x) (+ x 7))		f is  #<procedure f>

(f)	This expression says to invoke f as a procedure with no
	arguments.  For that to work, we must DEFINE f as a procedure
	with no arguments:
		(define (f) 'hello)		(f) is  hello
		(define (f) (+ 2 3))		(f) is  5
	Each of these is shorthand for an explicit use of lambda:
		(define f (lambda () 'hello))
		(define f (lambda () (+ 2 3))

(f 3)	This expression says to invoke f as a procedure with an
	argument, so we have to define it that way:
		(define (f x) (+ x 5))		(f 3) is  8
		(define (f x) 'hello)		(f 3) is  hello
		(define (f x) (word x x))	(f 3) is  33
	Again, these definitions are shorthand for lambda expressions:
		(define f (lambda (x) (+ x 5)))
		(define f (lambda (x) 'hello))
		(define f (lambda (x) (word x x)))

((f))	This expression says, first of all, to compute the subexpression
	(f), which invokes f as a procedure with no arguments.  Then, the
	result of that invocation must be another procedure, which is
	also invoked with no arguments.  So, we have to define f as a
	procedure that returns a procedure:
		(define (f) (lambda () 'hello))	     ((f)) is  hello
		(define (f) (lambda () (+ 2 3)))     ((f)) is  5
	Or without the shorthand,
		(define f (lambda () (lambda () 'hello)))
		(define f (lambda () (lambda () (+ 2 3))))
	Alternatively, we can let the procedure f return some procedure
	we already know about, supposing that that procedure can be
	invoked with no arguments:
		(define (f) +)		             ((f)) is  0
		(define f (lambda () +))
	As a super tricky solution, for hotshots only, try this:
		(define (f) f)			     ((f)) is  #<procedure f>
						     (((f))) is.... ?

(((f)) 3)  Sheesh!  F has to be a function.  When we invoke it with no
	   arguments, we should get another function (let's call it G).
	   When we invoke G with no arguments, we get a third function
	   (call it H).  We have to be able to call H with the argument 3
	   and get some value.  We could spell this out as a sequence of
	   definitions like this:
		(define (h x) (* x x))
		(define (g) h)
		(define (f) g)			(((f)) 3) is  9
	   Alternatively, we can do this all in one:
		(define (f) (lambda () (lambda (x) (* x x))))
	   or without the abbreviation:
		(define f (lambda () (lambda () (lambda (x) (* x x)))))

By the way, you haven't yet learned the notation for functions that accept
any number of arguments, but if you did know it, you could use
		(define (f . args) f)
as the answer to *all* of these problems!


Problem 2:

Of course you could just try this on the computer, but you should understand
the results.

(t 1+) means that we should substitute the actual argument, which is the
function named 1+, for t's formal parameter, which is f, in t's body,
which is (lambda (x) (f (f (f x)))).  The result of the substitution is

		(lambda (x) (1+ (1+ (1+ x))))

Evaluating this produces a function that adds three to its argument, so
((t 1+) 0) is 3.

(t (t 1+)) means to substitute (t 1+) for f in t's body.  If we actually
substituted the lambda expression above for f three times, we'd get a
horrible mess:

		(lambda (x) ((lambda (x) (1+ (1+ (1+ x))))
			     ((lambda (x) (1+ (1+ (1+ x))))
			      ((lambda (x) (1+ (1+ (1+ x))))
			       0))))

but what's important is the function, not the expression that produced
the function, so we can just mentally give (t 1+) the name 3+ and then
the result we want is

		(lambda (x) (3+ (3+ (3+ x))))

and if we apply that function to 0 we'll get 9.

For the final piece of the problem, we have to begin by computing (t t), which
is what we get when we substitute t for f in t's body:

		(lambda (x) (t (t (t x))))

Don't be confused!  Even though this lambda expression has x as its formal
parameter, not f, the argument has to be a function, because we're going to
end up invoking t on that argument.  In other words, (t t) returns as its
value a function that takes a function as argument.

Now, ((t t) 1+) means to apply the function just above to the argument 1+
which, in turn, means to substitute 1+ for x in the body:

		(t (t (t 1+)))

Well, this isn't so hard; we've really already done it.  (t 1+) turned
out to be 3+, and (t (t 1+)) turned out to be 9+.  By the same reasoning,
this will turn out to be 27+ (that is, 9+ three times), so when we apply
this to 0 we get 27.

Problem 3:

This is actually the same as problem 2!  The function S is identical to
1+, so the answers have to be the same.  It's more work if you actually
substitute values into the body of s, but you can avoid all that if you
realize that these problems are identical in meaning.

Problem 4:

If (g) is a legal expression, then g takes ZERO arguments.
If ((g) 1) has the value 3, then (g) has a PROCEDURE as its value.
(If we'd asked for more than one word, you could say "a procedure
of one numeric argument that returns a number" or something.)

Problem 5:

(define (substitute new old sent)
  (cond ((empty? sent) '())
	((equal? (first sent) old)
	 (sentence new (substitute new old (butfirst sent))))
	(else (sentence (first sent) (substitute new old (butfirst sent))))))



SECOND LAB (back page):

1.  Lots of expressions are possible, but the simplest is probably

(let
  ((a 3) (b (+ a 2)))
  (* a (- b 1)))

The key point is that inside the body of the LET, the value of B is 9,
not 5, because the A used in evaluating (+ a 2) is the global value, 7,
not the value assigned in the LET.

2.

(define (make-tester who)
  (lambda (x) (equal? x who)))

--------------------------

HOMEWORK:

1.16:  The goal is to use the algorithm of fast-exp on page 45, but
avoid using the recursive call as an argument to something else.  The
hint tells us to use an extra variable, a, which will contain part
of the result.

(define (fast-exp b n)
  (define (iter a b n)
    (cond ((= n 0) a)
	  ((even? n) (iter a (square b) (/ n 2)))
	  (else (iter (* a b) b (- n 1)))))
  (iter 1 b n))

We're supposed to keep the quantity a*b^n constant in all the invocations
of ITER for any specific problem.  If n is even, we square b and divide n by 2,
so we have
	a * (b^2)^(n/2)
which is indeed equal to a*b^n.  If n is odd, we have
	(a * b) * b^(n-1)
which is also equal to a*b^n.  So each invocation does keep the
overall value constant.  When we get to n=0, therefore, the value
of a must be the original value of b^n.

It's important to pay attention to what the problem says about
invariants; that's what this problem is about!


Exercise 1.31(a):  

;; you only needed to hand in one version
;; but by now you're ready to understand both:

;; recursive version:

(define (product term a next b)
  (if (> a b)
      1       ;; Note multiplicative identity is 1 not 0
      (* (term a)
	 (product term (next a) next b))))

;; iterative version:

(define (product term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(iter (next a) (* result (term a)))))
  (iter a 1))

;; factorial

(define (! n) (product (lambda (x) x) 1 1+ n))

;; pi
;; You have to run a few hundred terms to get a good approximation.
;; There are several possible ways to arrange the terms.  Here is one
;; way, in which the first term is 2/3, the second is 4/3, etc.

(define (pi terms) (* 4 (product
			 (lambda (x) (/ (* 2 (1+ (floor (/ x 2))))
					(1+ (* 2 (ceiling (/ x 2))))))
			 1 1+ terms)))

;; Here is another way, in which the first term is (2/3)*(4/3), the
;; second is (4/5)*(6/5), etc.  Notice that the value of a starts at
;; 3 and is increased by 2 for each new term.

(define (pi terms) (* 4 (product
			 (lambda (x) (/ (* (-1+ x) (1+ x))
					(* x x) ))
			 3
			 (lambda (x) (+ x 2))
			 terms )))

;; If you try to make it 2 * (4/3) * (4/3) * (6/5) * (6/5) * ... you'll
;; get the wrong answer, because you'll have one more number in the
;; numerator than in the denominator.



Exercise 1.32(a):  

;; you only needed to hand in one version

;; recursive form

(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
		(accumulate combiner null-value term (next a) next b))))

;; iterative form

(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(iter (next a) (combiner (term a) result))))
  (iter a null-value))

;; sum and product

(define (sum term a next b) (accumulate + 0 term a next b))

(define (product term a next b) (accumulate * 1 term a next b))



Exercise 1.33:  

;; The problem only requires one version but this too can be
;; recursive or iterative.  Recursive version:

(define (filtered-accumulate combiner null-value term a next b predicate)
  (cond ((> a b) null-value)
	((predicate a)
	 (combiner (term a)
		   (filtered-accumulate combiner
					null-value
					term
					(next a)
					next
					b
					predicate)))
	(else (filtered-accumulate combiner
				   null-value
				   term
				   (next a)
				   next
				   b
				   predicate))))

;; Iterative version:

(define (filtered-accumulate combiner null-value term a next b predicate)
  (define (iter a result)
    (cond ((> a b) result)
	  ((predicate a) (iter (next a) (combiner (term a) result)))
	  (else (iter (next a) result))))
  (iter a null-value))

;; (a) sum of squares of primes

(define (sum-sq-prime a b)
  (define (square x) (* x x))
  (filtered-accumulate + 0 square a 1+ b prime?))

;; (b) product of blah blah, using gcd from page 44

(define (prod-of-some-numbers n)
  (filtered-accumulate *
		       1
		       (lambda (x) x)
		       1
		       1+
		       n
		       (lambda (x) (= 1 (gcd x n)))))


1.35:  The definition of a fixed point is that it satisfies the
equation f(x)=x.  In this case, f(x)=1 + (1/x), so we are looking
for a number that satisfies
	1 + (1/x) = x
Multiply both sides by x and you get
	x + 1 = x^2
which is the definition of the golden ratio on page 38.

Therefore we can compute phi by calling

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1)


Exercise 1.41:

(define (double f)
  (lambda (x) (f (f x))))


Why does (((double (double double)) inc) 5) return 21 and not 13?
The crucial point is that DOUBLE is not associative.

> (((double (double double)) inc) 5)
21
> ((double (double (double inc))) 5)
13

DOUBLE turns a function into one that applies the function twice.
(DOUBLE DOUBLE) turns a function into one that applies the function
four times.
(DOUBLE (DOUBLE DOUBLE)) makes a function that applies (DOUBLE DOUBLE)
twice -- that is, make a function that applies the argument function
four times four times!



Exercise 1.43:  

(define (repeated f n)
  (lambda (x)
    (if (= n 0)
	x
	(f ((repeated f (- n 1)) x)))))

or

(define (repeated f n)
  (lambda (x)
    (if (= n 0)
	x
	((repeated f (- n 1)) (f x)))))

or

(define (repeated f n)
  (if (= n 0)
  (lambda (x) x)
  (lambda (x) (f ((repeated f (- n 1)) x)))))


We didn't assign 1.42, but if you followd the hint about it in 1.43,
you'd end up with this:

(define (repeated f n)
  (if (= n 0)
      (lambda (x) x)
      (compose f (repeated f (- n 1)))))


1.46

This problem is a little complicated in its details because there are so
many different procedures involved, with different domains and ranges.
But don't let that keep you from seeing the beauty of this extremely
general method!

(define (iterative-improve good-enough? improve)
  (define (iterate guess)
    (if (good-enough? guess)
	guess
	(iterate (improve guess))))
  iterate)

(define (sqrt x)  ;; compare to bottom of page 30 of SICP
  ((iterative-improve (lambda (guess) (< (abs (- (square guess) x)) 0.001))
		      (lambda (guess) (average guess (/ x guess))))
   1.0))

Some people were confused about sqrt because the original good-enough? takes
two arguments, and iterative-improve only allows for one.  But we are using
lexical scope so that the lambda expressions used as arguments to
iterative-improve have access to the starting value x.

(define (fixed-point f first-guess)  ;; compare to page 69
  ((iterative-improve (lambda (guess) (< (abs (- guess (f guess))) tolerance))
		      f)
   first-guess))

Here the structure is a little different from what's in the book, because
there is no variable NEXT to hold the next guess.  The solution above computes
(f guess) twice for each guess.  If you don't like that, you could use a more
complicated solution in which the argument to the good-enough procedure is a
sentence containing both old and new guesses:

(define (fixed-point f first-guess)
  ((iterative-improve (lambda (guesses)
			(< (abs (- (first guesses) (last guesses))) tolerance))
		      (lambda (guesses)
			(sentence (last guesses) (f (last guesses)))))
   (sentence first-guess (f first-guess))))

but I don't think the constant-factor efficiency improvement is worth the
added complexity of the code.


2.  Find the third perfect number.

The following solution uses a slightly non-obvious trick: when a
factor is found, we add in both FACTOR and (/ N FACTOR) at the same
time.  That is, when we find one factor, another factor is directly
computable and need not be searched for.  As a result, we need only
search numbers up to (SQRT N) instead of up to N or (/ N 2) as in
the most straightforward approach.  This makes the program run in
O(sqrt n) time instead of O(n), a substantial savings.

If you didn't think of that trick, the structure of the solution
would be essentially the same, except that the limit would be
greater and only one factor would be added to the sum at a time.

(define (perf? n)
  (define (iter limit test sum)
    (cond ((> test limit) sum)
	  ((= (remainder n test) 0)
	   (cond ((= test limit) (+ sum test))
		 (else (iter limit (+ test 1) (+ sum test (/ n test))))))
	  (else (iter limit (+ test 1) sum))))
  (= n (iter (sqrt n) 2 1)))

(define (next-perf n)
  (cond ((perf? n) n)
	(else (next-perf (+ n 1)))))

==> (next-perf 29)
496

By the way, perfect numbers are related to another kind of number called
Mersenne primes.  A Mersenne prime is a prime number of the form (2^p)-1
where p is prime.  (If p is composite, so is (2^p)-1.)  It turns out that
if (2^p)-1 is prime, then (2^(p-1))*((2^p)-1) is perfect.  So you can find
perfect numbers by starting with small primes p, seeing if (2^p)-1 is
prime, and if so, use the formula above.  What about the converse?  That is,
must every perfect number fit this formula?  If so, the third perfect
number must correspond to the third Mersenne prime.  It turns out that every
even perfect number must fit the formula; it is not known (or at least not in
1974 when the number theory book I'm reading was published) whether or not
there are any odd perfect numbers.  But there certainly aren't any small ones,
so the third prime p=5 gives rise to the third Mersenne prime (2^5)-1 = 31
and thence to the third perfect number (2^4)*31 = 496.  If you know all that,
you can solve the homework problem much more quickly.  The moral, as in
the Pascal's Triangle problem discussed in lecture, is that understanding the
problem better is often worth more than any amount of code mangling.  Thanks
to Andy McFadden for calling my attention to this approach.


3.  Formula for exp-iter invariant

The product of PRODUCT times [B to the COUNTER power]
is always equal to [B to the N power].

4.  EVERY:

(define (every f sent)
  (if (empty? sent)
      '()
      (se (f (first sent))
	  (every f (butfirst sent)) )))


------------------------
Extra Practice:

1. 
1.37.  The simplest solution is probably the following, which uses
a helper function and generates a recursive process:

(define (cont-frac n d k)
  (define (helper i)
    (if (> i k)
	0
	(/ (n i) (+ (d i)
		    (helper (+ i 1))))))
  (helper 1))

This says that

	helper(1) = N(1)/[D(1)+helper(2)]
	helper(2) = N(2)/[D(2)+helper(3)]

and so on, until we reach the Kth term:

	helper(K) = N(K)/[D(K)+0]

In the iterative version, we first compute x = N(k)/D(k), then use that to
compute N(k-1)/[D(k-1)+x], and so on until we reach the outermost fraction.

(define (cont-frac n d k)
  (define (iter k result)
    (if (= k 0)
	result
	(iter (- k 1)
	      (/ (n k) (+ (d k) result)))))
  (iter k 0))

Finally, here is a somewhat tricky version that avoids using a helper
procedure, but requires changing the functions N and D in the
recursive calls!

(define (cont-frac n d k)
  (if (= k 0)
      0
      (/ (n 1) (+ (d 1)
		  (cont-frac (lambda (x) (n (+ x 1)))
			     (lambda (x) (d (+ x 1)))
			     (- k 1))))))

(define (phi k)
  (/ 1 (cont-frac (lambda (i) 1.0)
		  (lambda (i) 1.0)
		  k))

> (phi 12)
1.61805555555556
> (phi 13)
1.61802575107296


1.38:  The numerator function is just (lambda (i) 1).  The denominator
function must return 1 most of the time, but one out of three times it
returns a computed even number instead.

(define (e k)
  (+ 2 (cont-frac (lambda (i) 1.0)
		  (lambda (i)
		    (if (= (remainder (- i 2) 3) 0)
			(* 2 (+ 1 (quotient (- i 2) 3)))
			1))
		  k)))

> (e 9)
2.71828358208955

Exercise 1.40:

(define (cubic a b c)
  (lambda (x) (+ (* x x x) (* a x x) (* b x) c)))




2.  Changing the order of the base cases in CC.  The original version is

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
	((or (< amount 0) (= kinds-of-coins 0)) 0)
	(else ...)))

How can changing the order of the first two clauses matter?  It must
be a situation in which *both* tests are satisfied.  Then the original
program will give the result 1, while the reversed version will give
the result 0.  But if both tests are satisfied, AMOUNT must be zero,
because of the first clause above.  So it can't be less than zero also.
Therefore, the only way the second test can be satisfied is if
KINDS-OF-COINS is also zero.  With the original version, (cc 0 0) will
give the result 1, whereas with the reordered version, (cc 0 0) will be 0.

As it turns out, no possible argument to COUNT-CHANGE will give rise to
a call to CC with both arguments zero.  Therefore, it's fair to say that
this difference doesn't really make a difference, if you think of CC as
just a helper procedure of COUNT-CHANGE and not as something that could
be called independently for its own sake.  But it's not quite trivial
to *prove* that CC is never called with both arguments zero.  The key
point is that in each of the two recursive invocations of CC, one
argument changes and the other remains the same.  Therefore, unless one
of the arguments was zero in the outer invocation, both can't be zero
in the recursive invocation.  But if either argument is zero we don't
get to the recursive invocations; one of the base cases will come into
play instead.

What's the right answer to (cc 0 0)?  That is, how many ways can we
count out zero cents using no coins?  One way -- use no coins!  So the
book's order is correct.



------------------------

Extra for experts:

1. This is a really hard problem!  But its solution comes up enough in
the literature that it has a name:  the Y combinator.  First here's
the combinator alone:

(lambda (f) (lambda (n) (f f n)))

And here's the factorial function using it:

(  (lambda (f) (lambda (n) (f f n)))
   (lambda (fun x)
     (if (= x 0)
	 1
	 (* x (fun fun (- x 1)))))  )

And now here's (fact 5):

(  (  (lambda (f) (lambda (n) (f f n)))
      (lambda (fun x)
	(if (= x 0)
	    1
	    (* x (fun fun (- x 1)))))  )
   5)

The trick is that instead of the factorial function taking a number
as an argument, it takes TWO arguments, a function (which will really
be itself when called) and a number.  The recursive call is done
using the function provided as argument.

The job of the Y combinator is to provide the function with itself
as an argument.


2. 
(define (partitions num)
  (pp num num))

(define (pp num chunk)
  (cond ((= num 0) 1)
	((or (< num 0) (= chunk 0)) 0)
	(else (+ (pp (- num chunk) chunk)
		 (pp num (- chunk 1))))))

Counting partitions is like making change, where the coins are
all the positive integers.