;; Summer 1995 CS 61A
;; Midterm #2 Solutions
;; Question 1 [5 points total]: Scheme Expressions and Box-and-Pointer Diagrams
;; ============================================================================
;; The goal of this question was to test your understanding of list
;; structures and of how the Scheme interpreter prints them.
;;
;; > (list (mickey mouse))
;; This produces an error because mickey and mouse are
;; unbound variables.
;; ERROR
;;
;; > (cons '(computer science) '(is fun!))
;; ((computer science) is fun!)
;; +---+---+ +---+---+ +---+---+
;; | | | | | | | | /|
;; --------> | | | ----------------->| | | ----->| | | / |
;; | | | | | | | | | | |/ |
;; +-|-+---+ +-|-+---+ +-|-+---+
;; | | |
;; | | |
;; V V V
;; +---+---+ +---+---+ is fun!
;; | | | | | /|
;; | | | ----->| | | / |
;; | | | | | | |/ |
;; +-|-+---+ +-|-+---+
;; | |
;; | |
;; V V
;; computer science
;;
;;
;; > ((lambda (x) (list x x)) (quote happy))
;; The key point here is that (quote happy) is the same as 'happy,
;; and evaluating (list 'happy 'happy) gives:
;; (happy happy)
;; +---+---+ +---+---+
;; | | | | | /|
;; --------->| | | ----->| | | / |
;; | | | | | | |/ |
;; +-|-+---+ +-|-+---+
;; | |
;; | |
;; V V
;; happy happy
;;
;;
;; > (cdr '(1 (2 (3))))
;; The cdr of this list gives a list of ONE item [that one item
;; being the list (2 (3))]. So the answer is:
;; ((2 (3)))
;; +---+---+
;; | | /|
;; --------> | | | / |
;; | | |/ |
;; +-|-+---+
;; |
;; |
;; V
;; +---+---+ +---+---+
;; | | | | | /|
;; | | | ----->| | | / |
;; | | | | | | |/ |
;; +-|-+---+ +-|-+---+
;; | |
;; | |
;; V V
;; 2 +---+---+
;; | | /|
;; | | | / |
;; | | |/ |
;; +-|-+---+
;; |
;; |
;; V
;; 3
;;
;; > (list '(car (cons 1 2)) 10)
;; The quote before (car (cons 1 2)) makes everything inside the
;; parentheses a symbol, including car and cons. The answer is:
;; ((car (cons 1 2)) 10)
;; +---+---+ +---+---+
;; | | | | | /|
;; --------> | | | ---->| | | / |
;; | | | | | | |/ |
;; +-|-+---+ +-|-+---+
;; | V
;; | 10
;; V
;; +---+---+ +---+---+
;; | | | | | /|
;; | | | ----->| | | / |
;; | | | | | | |/ |
;; +-|-+---+ +-|-+---+
;; | |
;; | |
;; V V
;; car +---+---+ +---+---+ +---+---+
;; | | | | | | | | /|
;; | | | ----->| | | ----->| | | / |
;; | | | | | | | | | | |/ |
;; +-|-+---+ +-|-+---+ +-|-+---+
;; | | |
;; | | |
;; V V V
;; cons 1 2
;;
;;
;; SCORING: (1 point per expression)
;; -0.5 pt for incorrect scheme printout
;; -0.5 pt for incorrect box-and-pointer diagram, unless it matches
;; the (incorrect) scheme printout
;; -1 pt for saying ERROR if there wasn't one
;; Question 2 [7 points total]: Flip-tree
;; ======================================
;; The goal of this question was to test your understanding of
;; manipulating tree structures and of representing data using message
;; passing.
;;
;; Part A. (4 pts)
;; ---------------
(define (flip-tree tree)
(cond ((empty-tree? tree) the-empty-tree)
(else (make-tree (entry tree)
(flip-tree (right-branch tree))
(flip-tree (left-branch tree))))))
;;SCORING:
;; + 1 pt. for correct base case
;; + 2 pts. for correct tree recursion
;; + 1 pt. for respecting the abstraction barrier (but -2 for multiple
;; violations)
;;
;; Some common errors:
;;
;; - Using the leaf case as the base case, i.e.
;;
;; (and (empty-tree? (left-branch tree))
;; (empty-tree? (right-branch tree)))
;;
;; This not only fails when the original tree is the-empty-tree, but
;; also causes problems with nodes with a single branch. Although
;; this can be made to work with some extra tests, it's easier to let
;; the recursion "bottom out" at the empty trees which are the
;; "branches" of the leaves.
;;
;; - Getting the data abstraction mostly right, but using () instead of
;; the-empty-tree. This is part of the abstraction barrier as well.
;;
;; - Recursing on only one branch, e.g. from thinking about binary
;; search trees. This problem required the entire tree to be
;; traversed, not just one path to a leaf.
;; Part B. (3 pts)
;; ---------------
(define (make-tree value left right)
(lambda (m)
(cond ((eq? m 'entry) value)
((eq? m 'left-branch) left)
((eq? m 'right-branch) right)
(else (error "Unrecognized message:" m)))))
(define (entry tree)
(tree 'entry))
(define (left-branch tree)
(tree 'left-branch))
(define (right-branch tree)
(tree 'right-branch))
;;SCORING:
;; 3 pts. if perfect
;; 2 pts. for small error, but correct notion of message passing
;; 1 pt. for having some idea, but clearly misunderstanding how message
;; passing works
;; 0 pts. for having no idea
;;
;; Common errors:
;;
;; - Getting make-tree entirely right, but failing to have the selectors
;; pass messages correctly to their arguments. A common form of this was
;;
;; (define (entry tree)
;; ((make-tree (car tree) (cadr tree) (caddr tree))
;; 'entry))
;;
;; This is doomed to fail, since tree is a procedure (being itself the
;; result of a call to make-tree).
;;
;; - Giving only one argument "tree" to make-tree, and returning e.g.
;; (car tree) from the lambda expression when an 'entry message is
;; received.
;; Question 3 [6 points total]: Generic Operators and Coercion
;; ===========================================================
;; The goal of this question was to test your understanding of how the
;; data-directed implementation of generic operators and coercion
;; works. It involved applying the same ideas from the last two exercises
;; of Homework #4.
;;
;; Part A.
;; -------
;; Here, OPERATE-2 gets called once, and it immediately finds +NUMBER to
;; add the two numbers together.
;;
;; (number . 7)
;; SUM = 1
;;
;; Part B.
;; -------
;; OPERATE-2 gets called twice -- in the first invocation, one argument
;; is an (integer) number, and the other is a complex number. The integer
;; gets coerced to a complex number, and OPERATE-2 is called again. This
;; time, it finds +COMPLEX. +COMPLEX calls +C (with the contents of the
;; complex numbers, i.e., with the COMPLEX tag removed). +C makes a new
;; complex number after getting the REAL-PART and IMAG-PART of each
;; number. There are four calls total to REAL-PART and IMAG-PART, and
;; each of these calls makes a call to OPERATE to find the
;; REAL-PART-RECTANGULAR or IMAG-PART-RECTANGULAR procedures.
;; Even with the code written on the whiteboard, many students treated +C
;; as a black-box and said that SUM = 2.
;;
;; (complex rectangular 15 . 4)
;; SUM = 6
;;
;; Part C.
;; -------
;; OPERATE-2 gets called once for the ADD. OPERATE gets called twice
;; for the MAGNITUDE (this is what happens in exercise 2.51 of the text).
;;
;; (number . 17.0)
;; SUM = 3
;;
;; SCORING (2 points each part):
;; -0.5 pts for incorrect numerical answer
;; -0.5 pts for correct numerical answer but wrong Scheme printout
;; -1.0 pt for incorrect sum
;; We did not penalize for making the exact same Scheme printout error
;; twice. Common errors included not putting a dot between NUMBER and 7,
;; writing just "7", or adding extra quotes or parentheses to the printout.
;; Question 4 [5 points total]: A more forgiving doctor program
;; ============================================================
;; The goal of this question was to test your understanding of iterating
;; through a list and of making a small change to the doctor program.
;;
;; this is what we wanted:
(define (repeated? item item-list)
(define (iter item-list count)
(cond ((>= count 3) #t)
((null? item-list) #f)
((equal? item (car item-list))
(iter (cdr item-list) (1+ count)))
(else (iter (cdr item-list) count))))
(iter item-list 0))
;; SCORING:
;; 5 pts. for any working solution
;; 4 pts. for "almost" working solution, with minor mistake
;; (e.g. "off-by-one" errors)
;; 3 pts. for basically right, but with multiple minor mistakes or one
;; bigger mistake (e.g. infinite loop)
;; 2 pts. for some idea, using recursion
;; 1 pt. for some idea, without recursion
;; 0 pts. for blank page
;;
;; Common errors:
;;
;; - "Off-by-one" errors: e.g. returns #t iff there are 4 or more
;; occurences (or 2 or more), instead of 3 or more.
;;
;; - Thinking that the expression (1+ count) somehow magically changes
;; the value of count, rather than just returning count+1. This is a
;; serious conceptual error about functional programming, but if the
;; program worked under this false assumption only 1 point was lost.
;;
;; - Correct definition of helper procedure, but missing call to it.
;;
;; - Missing one of the base cases (e.g. never returns #t).
;;
;; - Sometimes returning a number instead of #t or #f.
;;
;; - Changing code outside of repeated?.
;;
;; - One common bug which is fairly subtle was to have the two base cases
;; in the helper function switched. This will incorrectly return #f in
;; the special case that the third occurence of item is at the very end
;; of the list.
;; Question 5 [6 points total]: Composing a list of functions
;; ==========================================================
;; The goal of this question was to test your understanding of
;; higher-order procedures and of manipulating list structures.
;;
;; We want to apply the procedures in order from right to left, but
;; taking the car of the list of procedures gives us the leftmost one
;; first. Thus, we defer applying that procedure until we have applied
;; all the procedures in the rest of the procs list to n.
;;
;; Either of these is the desired solution:
(define (compose-funcs procs)
(lambda (n)
(if (null? procs)
n
((car procs) ((compose-funcs (cdr procs)) n)))))
(define (compose-funcs procs)
(if (null? procs)
(lambda (n) n)
(lambda (n)
((car procs) ((compose-funcs (cdr procs)) n)))))
;; Some students realized that by reversing the list of procedures,
;; they could implement an iterative solution to compose-funcs:
(define (compose-funcs procs)
(lambda (n)
(define (iter curr-procs result)
(if (null? curr-procs)
result
(iter (cdr curr-procs) ((car curr-procs) result))))
(iter (reverse procs) n)))
;; SCORING:
;; -2 pts -- each significant error (up to -4 pts)
;; The most common errors were in the recursive call:
;; -- not applying (compose (cdr procs)) to n
;; -- trying to somehow cons the car and cdr of the the procs list
;; -- applying the procs to () or to (lambda (x) x)
;; -1 pt -- minor error (up to -2 pts)
;; The most common errors were:
;; -- not working with an empty list of procedures
;; -- passing the wrong argument name
;;
;; There were too many different answers to categorize, but basically the
;; scores came out like this:
;; 6 pts -- perfect solution
;; 5 pts -- works, but minor error
;; 4 pts -- will work with one significant change
;; 3 pts -- applies procedures in wrong order, or significant + minor error
;; 2 pts -- two significant errors, or just bits and pieces of a solution
;; 1 pts -- a bit or piece of the solution
;; 0 pts -- clearly didn't know how to solve problem