;; Solutions for Midterm 1
;; CS 61A: Spring 1998
;; -----------------------------------
;; QUESTION 1 (6 points): all versions
;; (in order)
(define x1 (list (cons 'a 'b) (list 'c 'd)))
;; ((a . b) (c d))
;; +-+-+ +-+-+
;; x1-->|*|*+--->|*|/|
;; +++-+ +++-+
;; | |
;; | |
;; V V
;; +-+-+ +-+-+ +-+-+
;; |*|*| |*|*+-->|*|/|
;; +++++ +++-+ +++-+
;; | | | |
;; V V V V
;; a b c d
(define x2 (cons 'a (cons 'b (cons 'c 'd))))
;; (a b c . d)
;; +-+-+ +-+-+ +-+-+
;; x2-->|*|*|-->|*|*|-->|*|*|
;; +++-+ +++-+ +++++
;; | | | |
;; V V V V
;; a b c d
(define x3 (list 'a 'b 'c (cons 'd '())))
;; (a b c (d))
;; +-+-+ +-+-+ +-+-+ +-+-+
;; x3-->|*|*|-->|*|*|-->|*|*|-->|*|/|
;; +++-+ +++-+ +++-+ +++-+
;; | | | |
;; V V V V
;; a b c +-+-+
;; |*|/|
;; +++-+
;; |
;; V
;; d
(define x4 (append (list (cons 'a 'b)) (list '())))
;; ((a . b) ())
;; .-.-. .-.-.
;; x4 -> |*|*+-->|/|/|
;; `+"-' `-"-'
;; |
;; .-.-.
;; |*|*|
;; `+"+'
;; | |
;; a b
(define x5 '((1 2) 3 . 4))
;; ((1 2) 3 . 4)
;; .-.-. .-.-.
;; x5 -> |*|*+-->|*|*|
;; `+"-' `+"+'
;; | | |
;; | 3 4
;; |
;; .-.-. .-.-.
;; |*|*+-->|*|/|
;; `+"-' `+"-'
;; | |
;; 1 2
(define x6 '(1 (2 . 3)))
;; (1 (2 . 3))
;; .-.-. .-.-.
;; x6 -> |*|*+-->|*|/|
;; `+"-' `+"-'
;; | |
;; 1 .-.-.
;; |*|*|
;; `+"+'
;; | |
;; 2 3
;; -1 for each
;; -2 max for missing leading arrows
;; NOTE: Anything with a quote in it is considered to be unresolved and
;; credit was taken off for it. Missing pointers were taken off
;; partial credit because we couldn't tell if you understood what
;; was being pointed to.
;; ----------------------------------
;; QUESTION 2 (6 points): all verions
(define (chop m)
(map cdr (cdr m)))
(define (foo m)
(if (empty? m)
'()
(cons m (foo (chop m)))))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
;; Version A:
(define H '((1 2 3) (4 5 6) (7 8 9)))
;; A.
(chop H)
;; ((5 6) (8 9))
;; B.
(foo H)
;; (((1 2 3) (4 5 6) (7 8 9)) ((5 6) (8 9)) ((9)))
;; C.
(accumulate * 2 (map caar (foo H)))
;; 90
;; Version X:
(define H '((1 3 5) (7 9 11) (13 15 17)))
;; A.
(chop H)
;; ((9 11) (15 17))
;; B.
(foo H)
;; (((1 3 5) (7 9 11) (13 15 17)) ((9 11) (15 17)) ((17)))
;; C.
(accumulate + 2 (map caar (foo H)))
;; 29
;; GRADING: 2 points each
;; parital credit only if your error was
;; small
;; --------------------------------
;; QUESTION 3 (5 points): version A
(define (triad left label right)
(lambda (m)
(cond ((eq? m 't-car) left)
((eq? m 't-cbr) label)
((eq? m 't-cdr) right))))
;; A lot of people got this question wrong. Remember that
;; this question is about message passing! Here are the
;; correct answers:
(define (label node) (NODE 'T-CAR))
(define (left node) (NODE 'T-CBR))
(define (right node) (NODE 'T-CDR))
;; node is a triad! As such, it should be able to take
;; 't-car, 't-cbr, or 't-cdr as its argument, and return
;; the appropriate value.
;; 3 points for this part of the question. In general, it
;; was all or nothing. Here are some ways to get partial
;; credit:
;; -1 for not quoting 't-car, 't-cbr, 't-cdr
;; -1 for paren errors
;; To create the tree in the diagram, you must use triad
;; consistently and correctly. Here was a common answer:
;; this is incorrect!!
;; (triad (triad 1 3 4)
;; 5
;; (triad 7 8 11))
;; This answer got 1 out of 2 for ignoring the statement in the
;; question that "Leaf nodes will have empty lists as their
;; left and right children." Following this advice, the correct
;; answer is:
(triad (triad (triad '() 1 '())
3
(triad '() 4 '()))
5
(triad (triad '() 7 '())
8
(triad '() 11 '())))
;; Solutions using list, etc. scored no points, because that
;; wasn't how this problem asked you to create trees.
;; GRADING: One point for each of the selectors, two points for
;; constructing the tree. Notice that you could have defined the
;; selectors wrong and still have defined the trees correctly, if you
;; followed the abstraction. No credit for anything using pairs, but
;; partial credit for having some notion of the right idea.
;; --------------------------------
;; QUESTION 3 (5 points): version X
(define (triad label left right)
(lambda (m)
(cond ((eq? m 't-car) label)
((eq? m 't-cbr) left)
((eq? m 't-cdr) right))))
;; Define the selectors
;; 1 point
(define (label node) (node 't-car))
;; 1 point
(define (label node) (node 't-cbr))
;; 1 point
(define (label node) (node 't-cdr))
;; Define the tree
;; 2 points
(triad 5 (triad 3 (triad 1 '() '()) (triad 4 '() '()))
(triad 8 (triad 7 '() '()) (triad 11 '() '())))
;; Partial credit (1 point) was given for
;; (triad 5 (triad 3 1 4) (triad 8 7 11))
;; GRADING: One point for each of the selectors, two points for
;; constructing the tree. Notice that you could have defined the
;; selectors wrong and still have defined the trees correctly, if you
;; followed the abstraction. No credit for anything using pairs, but
;; partial credit for having some notion of the right idea.
;; -----------------------------------
;; QUESTION 4 (6 points): all versions
;; A. (1 pt)
;; count-if-member takes an item, x, and a list, s, and returns the number
;; of elements of s that are equal to x.
;; OR
;; count-if-member is a function that has as arguments
;; an element x and a list s, and returns the integer count of how many
;; entries in s are equal to x.
;; (We generally gave credit for anything that sounded even close. Just
;; because you got full credit does NOT mean your answer was necessarily
;; good. Compare your answer to the description above.
;; B. (1 pt)
;; remove takes an item, x, and a list, s, and returns a list equivalent to s
;; with all occurrences of x removed.
;; OR
;; Remove is a function that has as arguments an element x and a list
;; s, and a returns a new list constructed of all the elements that are
;; in s but are not equal to x, in the same order as they occur in s.
;; C. (4 pts : -0.5 pts for each wrong answer w/ minimum of 0 out of 4)
;; version A version X
;; A - 6 A - 12
;; B - 5 B - 7
;; C - 5 C - 7
;; D - 1 D - 1
;; E - 3 E - 11
;; F - 1 F - 1
;; G - 8 (given) G - 8 (given)
;; H - 12 H - 14
;; I - 1 I - 1
;; J - 4 J - 2
;; We accepted null? in place of empty? for A.
;; Note: For J, some students wrote (lambda (x) x),
;; the identity function which is OK.
;; ------------------------------------
;; QUESTION 5 (10 points): all versions
(define (make-inches L)
(lambda (unit)
(cond ((eq? unit 'inches) L)
((eq? unit 'feet) (/ L 12))
((eq? unit 'centimeters) (* L 2.54))
(else (error "Unknown unit")))))
(define (make-feet L)
(lambda (unit)
(cond ((eq? unit 'inches) (* L 12))
((eq? unit 'feet) L)
((eq? unit 'centimeters) (* L 30.48))
(else (error "Unknown unit")))))
(define (make-centimeters L)
(lambda (unit)
(cond ((eq? unit 'inches) (/ L 2.54))
((eq? unit 'feet) (/ L 30.48))
((eq? unit 'centimeters) L)
(else (error "Unknown unit")))))
;; 5a.
(define (length-value length-object unit)
(length-object unit))
;; The idea was to make the selector for the lenght object constructors
;; defined in the problem. You had to recognize that the length objects
;; themselves had all the operations to transform the length into a value
;; for any unit you wanted. All you needed to do was to tell it what unit
;; you wanted your answer in.
;; 5b.
(define (area-of-rectangle-in-sq-feet width height)
(* (length-value width 'feet) (length-value height 'feet)))
;; Since we know we want square feet, we just need to use our selector
;; above to get the values of length in feet, and then multiply to find
;; the area of the rectangle made by these two lengths.
;; Some people put:
(define (area-of-rectangle-in-sq-feet width height)
(* (width 'feet) (height 'feet)))
;; We did accept this answer for full credit since it does work for the
;; given constructors above, however THIS VIOLATES THE DATA ABSTRACTION
;; (such violations will not be tolerated in the future)! At this point,
;; we shouldn't have to worry about how a length is represented (as a
;; message passing object). If we decided to switch representations of
;; length objects to something else (such as a table of put's and get's
;; with the conversion functions), then this version would not work while
;; the first version would still work (given that the selector
;; "length-value" still worked properly). Actually, for the people
;; that got part A wrong, some got part B correct by assuming the selector
;; "length-value" worked, and used it properly :)
;; 5c.
;; It is a bad idea to coerce all types (float, rational, complex, ... )
;; to integer because there is a loss of information in the conversion,
;; and the answer will be, in general, inaccurate. 2.4 * 3+4I would come
;; out as 6.
;; Most people got credit for this if they mentioned inaccuracy or
;; loss of information.
;; 5d.
;; Defending the argument that coercion to any other type is also bad:
;; Coercing to floating point (limited precision) also loses information.
;; Coercing to rational, which can be done without loss of precision from
;; any finite floating point number that can be represented numerically
;; in the computer, or from any integer, may be expensive, since it
;; involves potentially very long integers.
;; You might have mentioned that these do not form a proper tower:
;; too large an integer "overflows" on conversion to float, and
;; too small a rational number "underflows" on conversion to float.
;; so
;; float
;; |
;; rational
;; |
;; integer
;; is wrong.
;; Attacking the argument:
;; If time and space is no object, and you are dealing only with scalar
;; values (not complex), then ratios of integers cover the cases of
;; float or integer.
;; That is, you can do this
;; rational
;; / \
;; integer float
;; Most people got credit for this as well.
;; 5e.
;; We accepted, with appropriate explanation (and even with some
;; sloppy explanation), that one can get away with 2, 3, or 4 coercion
;; routines. We expected 4: (I=integer, R=rational, F=float)
;; I to/from R and F to/from R
;; Some people assumed that if we converted to R (or with loss of info)
;; to F, then did the arithmetic in the target type AND LEFT IT IN THAT
;; TYPE, then all we need is 2. If it seemed to us that your answer
;; was intended to put this twist on the problem specification, we
;; gave you credit.
;; Unfortunately, these questions did not work as well as we would have
;; liked. Some people did not know what a "float" was (approximate
;; decimal number is a good explanation). What Pascal calls real,
;; if that is what you saw previously.
;; But there are infinitely more real numbers in math than
;; there are single-precision floating-point numbers in a computer..
;; -----------------------------------
;; QUESTION 6 (6 points): all versions
;; Version A: All Falses.
;; Version X: All Trues.
;; Explanations in order
;; - (car ''(hello)) returns quote.
;; - Intervals: The interval computation of sin ([0,pi]) is the interval
;; [0,1] because the maximum of the sin function on that interval
;; is 1, and the minimum is 0. sin(pi/2) is 1. So the range of that
;; function is NOT [0,0].
;; - Closure: closure of CAR would mean that you could always compute
;; the CAR of the result of a CAR. This is not true, since (car(car '(a)))
;; is an error.
;; - The function (lambda(x) (cons x x)) will return a pair. In scheme
;; anything that is not false is true and so the filter will return the
;; list "y".
;; - Abstraction: make-rat is used to implement the rational number
;; abstraction. attach-tag is used to implement a tagged data type,
;; abstractly associating a tag with the data item. These are quite
;; different abstractions. The fact that they are both implemented by
;; cons is irrelevant to the abstraction.
;; - The order in which the vectors specifying the sides of the frame are
;; given doesn't have to be the same.