CS 61A Solutions to sample midterm 2 #1 1. What will Scheme print? Note: Please draw actual boxes, as in the book and the lectures, not XX and X/ as in these ASCII-art solutions. Also, please put in the start arrows! Sometimes it's hard to know where your diagrams are supposed to begin, especially if you use leftward and upward pointing arrows. > (map caddr '((2 3 5) (7 11 13) (17 19))) ERROR (caddr '(2 3 5)) is 5; (caddr '(7 11 13)) is 13. But (17 19) doesn't have a caddr, which would be the third element of a two-element list. The error is attempting to take the car of the empty list. The most common wrong answer was (5 13), thinking that the error would just slide under the rug. > (list (cons 2 (cons 3 5))) ((2 3 . 5)) --->X/ | XX--->XX---> 5 | | V V 2 3 There were two points to note in this problem: (cons 3 5) creates an improper list, and LIST is called with one argument, making a one-element list (whose spine is the topmost pair in the diagram). One error was to think that every call to CONS results in something that prints with a dot, like this: ((2 . (3 . 5))) But in fact Scheme never prints a dot if the cdr is a pair; if the ultimate pair of a chain of cdr-linked pairs doesn't have the empty list as its cdr, you get the improper list notation (2 3 . 5) The extra parentheses in the printed form show that the result is a one-element list whose element is a list structure (in this case, an improper list rather than an actual list). > (append (list '(2) '(3)) (cons '(4) '(5))) ((2) (3) (4) 5) --->XX--->XX--->XX--->X/ | | | | V V V V X/ X/ X/ 5 | | | V V V 2 3 4 The most problematic part of this for most students was the CONS. Some people, remembering that the arguments to APPEND must be lists, said that this produced an error -- but of course CONS can produce a list, if its second argument is a list, as it is here. [Fine print: In fact the *last* argument to APPEND is *not* required to be a list, although the others are. See the Scheme reference manual.] In this case, the CONS call produces the list ((4) 5). The asymmetry in the handling of (4) and (5) comes from the meaning of CONS in creating a list: the first argument, the car of the new pair, is an *element* of the resulting list, whereas the second argument, the cdr of the new pair, is a *sublist* of the resulting list. If this confuses you, think about what you'd expect (cons 4 '(5)) to do. The most common error, still about the CONS call, was to see that it has to do something different from the LIST call, but still try to make it treat its arguments symmetrically, resulting in the wrong answer ((2) (3) 4 5). > (list (cons '(0) '(1)) (append '(2) '(3))) (((0) 1) (2 3)) --->XX------------->X/ | | V V XX--->X/ XX--->X/ | | | | V V V V X/ 1 2 3 | V 0 LIST returns a list with as many elements as it has arguments -- in this case, two elements. The top two pairs in the diagram are the ones generated by LIST. CONS generates exactly one new pair. In this problem, the first pair on the second line of the diagram is the one generated by CONS. Its car is the pair on the third line, which is the list (0); its cdr is the second pair on the second line, which is the list (1). The important thing to see here is that the lists (0) and (1) do not play similar roles in the result, because of the way lists are defined. The car of a pair is a list *element*; the cdr of the same pair is a *sublist*. So the value returned by the CONS invocation is a list of two elements, namely (0) and 1 -- not (0) and (1); not 0 and 1. APPEND strings together the elements of its arguments, so in this case, the result of the APPEND invocation is the list (2 3). There were two common wrong answers to this part. One mistake was to put the last element of a sublist in the cdr of a pair, like this: --->XX------------->X/ ; WRONG! | | V V XX--->1 XX--->3 | | V V X/ 2 | V 0 The numbers 1 and 3 are attached to the cdrs of their parent pairs, rather than to the cars. The other common mistake was to leave out the pair just above the zero, like this: --->XX------------->X/ ; WRONG! | | V V XX--->X/ XX--->X/ | | | | V V V V 0 1 2 3 A less common, but more serious, error was to leave out part of the work by having parentheses in the diagram: --->XX------------->X/ ; WRONG! | | V V XX--->(1) XX--->(3) | | V V (0) 2 There are never any parentheses in a box and pointer diagram. The parentheses in the *printed representation* of a list structure are just a notation to represent *pairs* in the actual structure. Scoring: One point for each printed result; one point for each diagram, except for the first part, which got two points or none. 2. Binary search trees Although the ADT doesn't include empty trees, the program is easier to write if you allow for the possibility of getting an empty list as argument instead of a tree, because that's what happens when you try to recur for the children of a leaf node. On that assumption, here's one way to write it: (define (all-smaller? tree num) (or (null? tree) (and (< (entry tree) num) (all-smaller? (left-branch tree) num) (all-smaller? (right-branch tree) num)))) (define (bst? tree) (or (null? tree) (and (all-smaller? (left-branch tree) (entry tree)) (all-larger? (right-branch tree) (entry tree)) (bst? (left-branch tree)) (bst? (right-branch tree))))) Most people wrote equivalent programs using COND, which is fine, but I find this style cleaner when writing predicates. A BINARY TREE is just a tree in which each node has at most two children. A BINARY SEARCH TREE is a binary tree with the ordering constraints as described in the text. The text doesn't make that entirely clear, because their only use of binary trees is to represent the SET ADT, for which a BST is needed. Therefore, we didn't take off points if in part (a) you assumed the ordering relationship and therefore only checked the right branch of the tree, as long as you did the tree recursion properly in (b). Scoring: This and the remaining problems are graded on the scale 5 correct 3-4 has the idea 1-2 has an idea 0 other Having the idea, in this problem, means doing a tree recursion. The most common form of not having the idea was to think, in part (b), that the ordering must be checked only with respect to the root node, so you left out the recursive calls to BST?. We took off one point if you violated the binary tree ADT, using CAR and CDR instead of ENTRY, LEFT-BRANCH, and RIGHT-BRANCH. (If you thought that those three things are names of trees, rather than of procedures, you didn't have the idea.) A too-common error was to say things like (< (left-branch tree) (entry tree)) as if the left branch were a number! It's not; it's a tree. 3. Tree fanout. The best answer is (define (max-fanout tree) (accumulate max (length (children tree)) (map max-fanout (children tree)))) This takes advantage of the fact that ACCUMULATE requires a starting value for the accumulation, usually 0 or 1 in the book's examples, but we can use the fanout of this node as the starting value. Here's the non-higher-order, mutual-recursion version: (define (max-fanout tree) (max (length (children tree)) (max-fanout-forest (children tree)))) (define (max-fanout-forest forest) (if (null? forest) 0 (max (max-fanout (car forest)) (max-fanout-forest (cdr forest))))) Some people made this more complicated by using a one-element forest as the base case in max-fanout-forest, thereby requiring that max-fanout check for the special case of a leaf node. If this were a general problem about accumulating the MAX of arbitrary numbers, we couldn't use 0 as the base case, because all the numbers might be negative, so if anything the base case would have to be negative infinity. But here the numbers are node fanouts, and there's no such thing as a negative number of children! Note that max-fanout does not need a base case. The recursion happens either in MAP, for the first solution, or in MAX-FANOUT-FOREST, for the second solution. Having the idea, in this problem, mostly meant understanding the Tree ADT. The totally wrong solutions were ones that applied CAR and CDR to a Tree -- or, equivalently, the ones that said DATUM and CHILDREN but meant CAR and CDR. Note that there is no reference to DATUM in a correct solution to this problem! The fanout has nothing to do with the values in the nodes, only with the Tree's shape. Not only is CAR/CDR recursion a data abstraction violation, it's also a fundamental misunderstanding of this particular problem. It's often the case that similar problems could be posed for abstract Trees and for list structures viewed as trees. But if you use CAR/CDR recursion, you are thinking of each pair as a node in a binary tree, essentially, so the fanout is always 2! The whole issue of fanout doesn't arise unless you have real Trees to think about. CAR/CDR programs, or their equivalent -- such as programs with expressions of the form (not (pair? tree)) -- got at most 2 points, but more often 0 or 1. So did programs that confused trees with forests. Some not-so-bad programs tried to apply MAX to a list of lists of numbers, rather than to a list of numbers. Our general rule was that if we could fix your program by replacing a call to MAP with a call to FLATMAP, it got 3 points. A common problem, not so bad, was to get confused about the domain of MAX. This procedure takes numbers as arguments, not lists; you can't say (max '(1 2 3 4)) but you *can* say (apply max '(1 2 3 4)) or in this case, because all the numbers are positive, (accumulate max 0 '(1 2 3 4)) The advantage of ACCUMULATE over APPLY is that in some cases, people who used APPLY ended up applying MAX to an empty list -- in other words, trying to call MAX with no arguments. That's not allowed, but ACCUMULATE always calls MAX with exactly two arguments, if at all, so it doesn't have the same potential bug. All problems in this category lost only one point. The comments in the solution to question 2 about making unnecessary data structures apply here, too. Several people made trees in which the datum of each node was replaced by its fanout. Others made linear sequences of tree nodes. All of these things only complicate the program; whatever you end up doing to create the structure and then process it could instead solve the problem directly in one step. Scoring: 3 or more points for a solution that uses the Tree ADT correctly and actually computes fanouts and maximums. 2 or fewer points for a solution with car/cdr recursion, tree/forest confusion, nothing about fanouts, or nothing about maximum. 4. Data-directed programming. (define (plus x y) (let ((tx (type x)) (ty (type y))) (if (eq? tx ty) (attach-tag tx (+ (contents x) (contents y))) (let ((gxy (get tx ty)) (gyx (get ty tx))) (cond ((number? gxy) (attach-tag ty (+ (* gxy (contents x)) (contents y)))) ((number? gyx) (attach-tag tx (+ (contents x) (* gyx (contents y))))) (else (error "You can't add apples and oranges."))))))) The use of LET in this solution isn't essential; various rearrangements are possible and are equally good. Surprising numbers of people had trouble understanding what the problem was asking for. They wrote programs in which 3 dynes PLUS 4 centimeters equals 12 ergs! Sorry, 3 plus 4 is not 12 no matter how clever your coding style is. As the problem clearly stated, you were asked to write one procedure, the addition procedure, for a larger project that would also include a multiplication procedure when completed. Moral: don't be in such a hurry to write code. Make sure you understand the problem you are being asked to solve first! Another common way to get in trouble was to try to apply the number you found in the table (12, in the example) as a procedure. Just because there is an example in the book in which a table contains procedures as entries, that doesn't mean that every table has to contain procedures! This particular table contains numbers, for units that can be added together, and symbols, for units that can be multiplied. Scoring: 8 points for a perfect solution. 4-7 points for a flawed solution not grossly confused. 2-3 points for a grossly confused but not clueless solution. 0-1 point for a solution showing no understanding at all. In general we subtracted two points for each flaw, down to the minimum for the categories as indicated. Here are some 2-point errors that bottomed at 4 points: -- not checking the number? predicate -- not checking for the arguments being backwards in the table -- incorrect conversion formula -- violation of the attach-tag data abstraction -- wrong args to GET Here are some errors eligible for the 2-3 point range: -- checking explicitly for 'ft or 'in -- applying a non-procedure -- Lisp syntax errors like non-symbol formal parameters 5. OOP The central point of this question is that in the OOP paradigm, objects are used for everything, and the structure of the object classes reflects the structure of the real-world situation being simulated. (a) parenthood The class VANILLA has the class SCOOP as its parent, because a vanilla scoop is a particular kind of scoop. Is a scoop a special kind of cone? No. Is a cone a special kind of scoop? No. So the correct answer is "Neither." Most people got this; the most common wrong answer was to say that SCOOP should have CONE as its parent, probably because a scoop can be viewed as *part of* a cone. But the parent/child relationship isn't "a part of"; it's "a kind of." (b) flavors method (method (flavors) (map (LAMBDA (S) (ASK S 'FLAVOR)) scoops)) You *could* write the CONE class so that its instance variable SCOOPS would be a list of flavors (i.e., names of flavors) instead of a list of scoop objects. But that wouldn't be following the OOP paradigm. (Not to mention that using the name SCOOPS for a list of flavors would be really confusing!) So if we want to know the flavors in a cone, we have to ask each scoop for its flavor. A few people said something like (USUAL 'FLAVOR) instead of (ASK S 'FLAVOR), presumably because FLAVOR is a method of the SCOOP class, rather than of the VANILLA or CHOCOLATE class. But even if this could work, the whole idea of inheritance is that you can send the child class (e.g., VANILLA) the same messages you can send to the parent class (SCOOP). You don't have to know whether VANILLA handles the FLAVOR message itself or delegates the message to its parent. And in any case it wouldn't work; USUAL can only be used inside a DEFINE-CLASS, because otherwise it doesn't know what object you're talking about! (c) adding a scoop Given a particular ice cream cone, we want to add a particular scoop of vanilla ice cream to it -- not the VANILLA class, and not the word VANILLA. So the right answer is the last one listed: (ask my-cone 'add-scoop (instantiate vanilla)) The argument to INSTANTIATE is a class, not the name of a class. Scoring: 2 points each. No partial credit except that in part (B) leaving out the quotation mark before FLAVOR got one point.