;; 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.