CS 61A Fall 1994 Midterm 2 solutions
1. Box & pointer diagrams
> (cons (append '(a b) '(c d)) '(e f))
((A B C D) E F)
Many people said ((a b c d) . (e f)) but Scheme never prints the
sequence ". (" in representing a list structure.
In the picture below, the starred pair is the one created by
the CONS invocation.
***********
*+---+---+* +---+---+ +---+---+
*| | |* | | | | | /|
--------->*| | | ----------->| | | ----->| | | / |
*| | | |* | | | | | | |/ |
*+-|-+---+* +-|-+---+ +-|-+---+
***|******* | |
| V V
|
| E F
|
V
+---+---+ +---+---+ +---+---+ +---+---+
| | | | | | | | | | | /|
| | | ----->| | | ----->| | | ----->| | | / |
| | | | | | | | | | | | | | |/ |
+-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+
| | | |
V V V V
A B C D
> (list (cons 'a 'b) (list 'c 'd) 'e)
((A . B) (C D) E)
+---+---+ +---+---+ +---+---+
| | | | | | | | /|
---------> | | | ----->| | | ----->| | | / |
| | | | | | | | | | |/ |
+-|-+---+ +-|-+---+ +-|-+---+
| | |
| | V
| |
| | E
V V
+---+---+ +---+---+ +---+---+
| | | | | | | | /|
| | | | | | | | ----->| | | / |
| | | | | | | | | | | |/ |
+-|-+-|-+ +-|-+---+ +-|-+---+
| | | |
V V V V
A B C D
> (caaddr '((a b c d e) (f g h i j) (l m n o p) (q r s t u)))
L
(cdr '((a b c d e) (f g h i j) (l m n o p) (q r s t u)))
===> ((f g h i j) (l m n o p) (q r s t u))
(cdr '((f g h i j) (l m n o p) (q r s t u)))
===> ((l m n o p) (q r s t u))
(car '((l m n o p) (q r s t u)))
===> (l m n o p)
(car '(l m n o p)) ===> L
The box and pointer diagram for this is just
-----> L
We accepted "you can't have a box and pointer diagram with no pairs"
and we accepted a single box around the L, but we didn't accept
anything with a pair above the L.
> (cons 'a (cdr '(((b)))))
(A)
(cdr '(((b)))) is the empty list, so this is equivalent to (cons 'a '()).
+---+---+
| | /|
---------> | | | / |
| | |/ |
+-|-+---+
|
|
V
A
Scoring: one point each, all or nothing.
2. Deep lists.
(define (deep-list? obj)
(cond ((null? obj) #t)
((atom? obj) #f)
((or (atom? (car obj))
(deep-list? (car obj)))
(deep-list? (cdr obj)))
(else #f)))
A deep list must be a list, so it can't be a non-null atom.
If the list is empty, then (trivially) all of its members satisfy
the condition given. If the list isn't empty, we look at its
first element. That element must be either a deep list or a
non-pair (that is, an atom). If either of those criteria is
met, we make sure the rest of the list is a deep-list.
The crucial idea here is that this is a tree recursive problem.
In other words, we aren't just looking at each element of a
sequence of elements; instead, we're looking at the elements,
and at elements of the elements, and at elements of elements of
elements, and so on, to any depth. It's a two-dimensional
problem. Therefore, any correct solution must use car/cdr
recursion, or the equivalent higher-order function:
(define (deep-list? obj)
(and (list? obj)
(null? (filter (lambda (element)
(not (or (atom? element)
(deep-list? element))))
obj))))
Scoring: Standard BH 5-point scale. Having the idea means
using tree recursion. Typical part-credit answers:
4 right except for base cases
3 tree recursion, but bad logic (e.g., always true)
2 checks elements, but not elements of elements
1 any recursion
By the way, many people seem to think that PAIR? and LIST? are
mutually exclusive. A list is either the empty list or *a pair*
whose cdr is a list.
Some people were confused by the recursive definition: a deep list
has deep lists as elements. (See also the recursive definition of
"list" in the previous paragraph.) Recursive definitions are just
like recursive procedures: There must be a base case. For lists,
the base case is the empty list. For deep lists, the base case is
having atoms as elements.
3. Time of day ADT.
(define (time-print-form time)
(word (hour time) ': (two-digit (minute time)) (category time)))
(define (two-digit num)
(if (< num 10)
(word 0 num)
num))
(define (24-hour time)
(+ (* (hour time) 100)
(minute time)
(if (equal? (category time) 'pm) 1200 0)))
(define (make-time hr min cat)
(+ (* hr 100)
min
(if (equal? cat 'pm) 1200 0)))
(define (hour time)
(if (>= time 1200)
(- (div time 100) 1200)
(div time 100)))
(define (minute time)
(remainder time 100))
(define (category time)
(if (>= time 1200) 'pm 'am))
The most common serious errors were writing a non-function in part (a) and
rewriting make-time with the wrong number of arguments in part (c). These
errors were the ones that gave rise to the most complaints about harsh
grading, but I really think they're about crucial issues in the course.
Part (a) says, "Write a FUNCTION time-print-form that takes a time as its
argument and RETURNS a word of the form 3:07pm." In week 7 of the course
you should know what it means for a function to return a value! Some people
said they were confused by the fact that the word "print" is part of the
function's name, but a "print form" is the form in which we want things to
be printed; computing the print form of a time doesn't mean that we should
actually print it! Maybe the print form will be used as part of a larger
sentence that we'll want to print later.
Part (c) says, "Now we decide to change the *internal* representation of
times to be a number in 24-hour form. BUT WE WANT THE CONSTRUCTOR AND
SELECTORS TO HAVE THE SAME INTERFACE SO THAT PROGRAMS USING THE ABSTRACT
DATA TYPE DON'T HAVE TO CHANGE." That means that the arguments to make-time
must be the same things they were all along: an hour (in 12-hour time), a
minute, and a category (am/pm).
Many people returned 3:7pm instead of 3:07pm in part (a), because they
thought that it would be sufficient to say something like
(time-print-form (make-time 3 07 'pm))
The trouble is that Scheme interprets 07 as the number 7; Scheme doesn't
remember exactly how you typed the number. This was a minor error.
Many people, in part (c), changed the internal representation to something
other than a number, e.g., a list of two numbers. I've spoken with four
students who didn't understand why this was wrong, and I asked them to
read the first sentence of part (c), and they said "... representation of
times to be in 24-hour form." And I said, "No, read it again." On the
third or fourth try they'd finally read the words "a number." Sigh.
Typical errors and scores:
4 3:7pm
3 changes internal form to (15 7) instead of 1507
2 printing in (a) or wrong args in (c), as above
1 glimmers of using the abstraction
4. Fix message passing for dyadic operators
(define (make-rectangular x y)
(define (dispatch m)
(cond ((eq? m 'real-part) x)
((eq? m 'imag-part) y)
((eq? m 'magnitude)
(sqrt (+ (square x) (square y))))
((eq? m 'angle) (atan y x))
((EQ? M 'ADD)
(LAMBDA (Z)
(MAKE-RECTANGULAR (+ X (REAL-PART Z))
(+ Y (IMAG-PART Z)))))
(else (error "Unknown op -- make-rectangular" m))))
dispatch)
The lines in capital letters are the only changes. It's okay
to use the book's +c procedure instead of calling make-rectangular:
((eq? m 'add) (lambda (z) (+c dispatch z)))
and it's okay to use (z 'real-part) instead of (real-part z).
(That's not a violation of data abstraction because we're writing
make-rectangular, the constructor for the ADT, and it has to know
how complex numbers are implemented!)
Having the idea means that make-rectangular accepts an ADD message
for which it returns a function of another complex number.
Common errors included giving make-rectangular extra arguments
and giving dispatch extra arguments. Probably that's because you
didn't understand the significance of all the parentheses in
(define (+complex z1 z2)
((z1 'add) z2))
Go back to the questions
Back to the Midterm/Final page