CS 61A Spring 1995 Midterm 3 solutions
1. Box & pointer diagrams
In the diagrams below, the arrows drawn with dots (......>) are
replaced by mutation with the ones drawn in bangs (!!!!!!>).
You didn't have to show the old ones to get credit.
> (let ((x (list 1 2 3 4)))
(set-cdr! x (caddr x))
x)
(1 . 3)
[Note the dot!!]
+---+---+ +---+---+ +---+---+ +---+---+
| | | | | | | | | | | /|
---------> | | | +....>| | | ----->| | | ----->| | | / |
| | | ! | | | | | | | | | | | |/ |
+-|-+-!-+ +-|-+---+ +-|-+---+ +-|-+---+
| ! | | |
| ! | | |
V ! V V V
!
1 ! 2 3 4
! ^
! !
!!!!!!!!!!!!!!!!!!!!!
[You didn't have to show the disconnected pairs to get credit; a single
pair whose car is 1 and whose cdr is 3 was enough.]
> (let ((x (list 1 2 3 4)))
(set-car! (cdr x) (cddr x))
x)
(1 (3 4) 3 4)
!!!!!!!!!!!!!
! V
+---+---+ +-!-+---+ +---+---+ +---+---+
| | | | ! | | | | | | | /|
---------> | | | ----->| ! | ----->| | | ----->| | | / |
| | | | | . | | | | | | | | |/ |
+-|-+---+ +-.-+---+ +-|-+---+ +-|-+---+
| . | |
| . | |
V V V V
1 2 3 4
[Notice that there are only four pairs in this diagram. It would
be an error to draw two extra pairs whose cars are 3 and 4. Make sure
you understand this point!]
> (let ((x (list 1 (list 2 3) 4)))
(set-car! (cadr x) (car x))
x)
(1 (1 3) 4)
+---+---+ +---+---+ +---+---+
| | | | | | | | /|
---------> | | | ----->| | | ----->| | | / |
| | | | | | | | | | |/ |
+-|-+---+ +-|-+---+ +-|-+---+
| | |
| | V
| |
| | 4
| |
| |
V |
|
1 |
^ V
! +---+---+ +---+---+
! | | | | | /|
!!!!!!!!!!!!+ | ----->| | | / |
| . | | | | |/ |
+-.-+---+ +-|-+---+
. |
V V
2 3
[Note that the new arrow points to the 1, not to the pair above it.
It's okay if you wrote another 1 near the 2 instead of drawing an
arrow across to the left. (It's *not* okay to duplicate pairs,
because that obscures the fact that modifying the one pair would
change two parts of the printed representation. But numbers aren't
mutable, so it doesn't really matter whether there's one one or
two ones.)]
Scoring: One point each. Both the printed form and the diagram
had to be right.
2. OOP passwords
(define-class (password-protect obj pwd)
(default-method
(if (eq? message pwd)
obj
(error "Password incorrect"))))
That's it! You have to use default-method because you don't know
ahead of time what the password will be, so your method must check
explicitly.
Scoring examples:
4 correct.
3 uses default-method but syntax not quite right:
(default-method (lambda (message) (if ...))).
3 Tries for a variable message:
(method pwd ...).
2 (parent obj).
2 Really bad syntax.
1 Uses default-method but has the counter example built in.
1 A bare glimmer of an idea.
0 Even worse.
By the way, there's no need for, e.g., (ask self obj). You can
just use the symbol obj to refer to an object's local variable.
3. Deep-map!
Here is the most elegant solution:
(define (deep-map! fn lst)
(cond ((null? lst) '())
((atom? lst) (fn lst))
(else (set-car! lst (deep-map! fn (car lst)))
(set-cdr! lst (deep-map! fn (cdr lst)))
lst)))
This solution depends on the fact that a value is returned for each
invocation. Also, it works for improper lists, even though we didn't
require that -- if you think about it the right way, handling the more
general case makes the problem easier, not harder.
Most people invented a solution that doesn't depend on the return value:
(define (deep-map! fn lst)
(cond ((null? lst) 'ok)
((atom? (car lst)) (set-car! lst (fn (car lst))))
(else (deep-map! fn (car lst))))
(cond ((null? lst) 'ok)
((atom? (cdr lst)) (set-cdr! lst (fn (cdr lst))))
(else (deep-map! fn (cdr lst))))
lst)
The only trouble with that solution is that most people who tried it
forgot to check for an empty argument in *both* CONDs.
There were also solutions with lots of checks for special cases, e.g.,
checking for a list in which each element is an atom, or handling the second
element of a list explicitly, etc. It's possible to get such a solution to
work, but really you should try to develop a stronger aesthetic sense about
trusting the recursion to handle the second element and so on.
Nothing in the problem suggests the use of the Tree abstract data type;
there should not have been any calls to DATUM or CHILDREN in your solution.
Don't be confused about the use of the word "tree" in the phrase "tree
recursion," which just means any situation in which there are two or more
recursive calls carried out from the same invocation of a procedure. The
tree ADT would only be relevant if the examples used make-node, etc.
Scoring examples:
4 Correct.
3 Correct except for base case(s).
2 Sequential (map!) instead of tree recursive.
1 (set! lst ...)
1 (set-car! some-non-pair ...)
0 (set! (car lst) ...)
0 Uses CONS
4. Stream of ones and zeros.
Okay, this was a hard problem, we admit. But many people did pretty
well with it.
The beautiful solution we were hoping for is this:
(define oz
(cons-stream '()
(interleave
(map (lambda (set) (cons 0 set)) oz)
(map (lambda (set) (cons 1 set)) oz))))
A few other ideas turned up that were clever but not easily workable.
Each of these ideas can be made to work, but with *much* more agony
than the solution above.
------
One idea was this, using the SUBSETS procedure from the course reader:
(define one-zero (cons-stream 1 (cons-stream 0 one-zero)))
(define oz (subsets one-zero)) ;; wrong!
The main problem with this is that the SUBSETS in the reader works only
for a finite stream. You can see this in two ways. From an algorithm
point of view, the problem is that the procedure must compute
(subsets (tail strm))
before it can produce even one element of its own result, so there is
an infinite recursion. From a mathematical point of view, *any* procedure
that claims to produce a stream of all the subsets of an infinite stream
must be incorrect, because the number of subsets of an infinite set is
uncountable, and a stream has to be at most countably infinite.
A second problem is that, since the stream one-zero contains duplicates,
its subsets will contain duplicates also.
To fix the first problem, what we can do is write a procedure that makes a
stream of the *finite* subsets of an infinite stream. (There are only
countably many of those, and it's all we need for this purpose.)
(define (n-subsets n set)
(cond ((= n 0) (stream '()))
((empty-stream? set) the-empty-stream)
(else (interleave-delayed (map (lambda (subset) (cons (head set) subset))
(n-subsets (- n 1) (tail set)))
(delay (n-subsets n (tail set)))))))
(define (finite-subsets set)
(define (helper n)
(interleave-delayed (n-subsets n set)
(delay (helper (1+ n)))))
(helper 0))
Note that, unlike our original solution to the oz problem, this program
won't work unless we use interleave-delayed.
To solve the second difficulty, we can write a remove-duplicates procedure for
infinite streams. (This is left as an exercise for the reader!)
------
Another clever attempt at a solution is this:
(define oz (map convert-to-binary integers)) ;; wrong!
where convert-to-binary is a procedure that returns a list containing ones
and zeros to represent its argument as a binary numeral, e.g.,
> (convert-to-binary 14)
(1 1 1 0)
> (convert-to-binary 20)
(1 0 1 0 0)
(We haven't actually written convert-to-binary; it's left as an exercise.)
The trouble with this approach is that it doesn't include the elements of
the desired result that have zeros at the left, and it doesn't include the
empty list.
One solution would be to compute all of the lists OF A GIVEN LENGTH using
a procedure convert-to-n-digit-binary and applying that only to the integers
between 0 and (2^n)-1, then string those together somewhat like the n-subsets
in the previous solution. Some students did this.
Another clever fix is to take the binary numerals and their complements, i.e.,
the strings of bits with each 0 replaced by a 1 and vice versa:
(define binaries (map convert-to-binary integers))
(define oz (cons-stream '() (interleave binaries (map complement binaries))))
Alternatively, take all the binary numerals starting with 1 and remove the
leftmost 1, so instead of (1) (1 0) (1 1) (1 0 0) (1 0 1) ... we have
() (0) (1) (0 0) (0 1) ... This is an especially short solution:
(define oz (map (lambda (n) (cdr (convert-to-binary n))) integers))
One student actually got the generate-one-at-a-time approach to work:
(define (next-element lst)
(cond ((null? lst) '(0))
((= (car lst) 0) (cons 1 (cdr lst)))
(else (cons 0 (next-element (cdr lst))))))
(define (make-oz element)
(cons-stream element (make-oz (next-element element))))
(define oz (make-oz '()))
We all had to read this over several times before we believed it! (And the
student made it harder by giving what I've called next-element the name
add-one, which it doesn't do, and which wouldn't give the right answer if
it did!) But it's quite impressive.
------
Solutions using the PERMUTATIONS procedure from the text have the same
problem as the SUBSETS approach: That procedure works only for finite
streams. But we could take permutations of finite streams and join them
together for the overall solution. Another problem with using PERMUTATIONS
is that _as written_
> (ss (permutations (stream 0 0 0 0 0)))
((0) (0) (0) (0) (0))
because the recursive call:
(permutations (remove x S))
will filter out all zeros. So instead of remove we need remove-first.
Here is a solution from Trey, once we fix that. Suppose we have
one-streams --> (() (1) (1 1) (1 1 1) (1 1 1 1) ... )
zero-streams --> (() (0) (0 0) (0 0 0) (0 0 0 0) ... )
Line them up like this to make a 2-D table:
() (1) (1 1) (1 1 1) ...
-------------------------------------------------------------
() | () | (1) | (1 1) | (1 1 1) |
(0) | (0) | (1 0) | (1 1 0) | (1 1 1 0) |
(0 0) | (0 0) | (1 0 0) | (1 1 0 0) | (1 1 1 0 0) |
(0 0 0) | (0 0 0) | (1 0 0 0) | (1 1 0 0 0) | (1 1 1 0 0 0) |
(0 0 0 0) | (0 0 0 0) | (1 0 0 0 0) | (1 1 0 0 0 0) | (1 1 1 0 0 0 0) |
. .
. .
. .
The entries in the table are gotten by appending each of the
indices. i.e. at (1 1) and (0 0 0) there is (1 1 0 0 0)
By constructing this table, you can find a list made of any number
of zeros and ones. So, if you find the permutations of each of the
entries in this table, you will get OZ.
(define oz
(remove-duplicates
(map stream->list
(flatmap permutations
(cross-product zero-streams one-streams)))))
(define (cross-product s1 s2)
(interleave-delayed
(map (lambda (x)
(append-streams (head s2) x))
s1)
(delay (cross-product s1 (tail s2)))))
Cross-product computes the table entries from the two streams.
> (ss (cross-product zero-streams one-streams))
(() (1) (0) (1 1) (0 0) (1 0) (0 0 0) (1 1 1) (0 0 0 0) (1 0 0) ...)
Since permutations returns a stream of streams, and we want lists,
I map stream->list to change all the inner streams to lists, then
remove any duplicates.
> (ss oz 10)
(() (1) (0) (1 1) (0 0) (1 0) (0 0 0) (0 1) (1 1 1) (0 0 0 0) ...)
The ordering is a little odd because of the interleaves.
------
Scoring:
4 correct
3 almost correct, or flawed but clever idea like (map binary integers)
2 (subsets one-zero-stream) or similar
1 not nearly correct but shows understanding of the exponential complexity
of the problem *or* of the difficulties of handling infinite streams
0 worse
NOTE: Far too many people used SET! or SET-CAR! in this problem. Streams
are a functional programming technique! They're in chapter 3 because
(1) they are the functional alternative to OOP for time-varying data;
(2) their *implementation* uses mutation (for memoization only).
In particular, if you compute the next element of the stream by mutating
the previous element, then you've changed the value of that previous
element, too! This is why mutation is problematic.
Group problem:
____________________
G: |
|<---------+
| |
| OO
| p: value
foo: 6 | b: (lambda (arg) ...)
|
|
maximizer ----------+-------> OO-----------------------------+
| p: arg |
____________________| b: (if (> arg value)...) value |
^ |
| |
| |
| |
_________|____________ |
E1: | |
|<-------------------------------------+
value: 6 |
______________________|
^
|
|
|
_________|____________
E2: |
|
arg: 6 |
______________________|
Scoring examples:
4 OK.
3 OK except missing the anonymous LET procedure.
2 foo is a procedure.
1 Two frames with VALUE bindings.
0 Maximizer procedure created in global frame.
Go back to the questions
Back to the Midterm/Final page