CS 61A Fall 1996 Midterm 2 solutions 1. expression trees (a) Many people got confused about which abstract data type we're using. As the problem clearly states, you are given the constructor MAKE-TREE with two arguments, and the selectors DATUM and CHILDREN. (define (treeify computation) (if (number? computation) (make-tree computation '()) (make-tree (cadr computation) (list (treeify (car computation)) (treeify (caddr computation)))))) The most common errors were about the base case: * Suppose the argument is a number. What should the result be? IT MUST STILL BE A TREE! You can't just return the number; numbers are not in the range of this procedure. * The problem statement specifically says, "the argument to treeify is a NONEMPTY list..." Many people always use NULL? by reflex as their base case test. It's not too bad if you make that test unnecessarily, in addition to the correct test, although it makes your program harder to read. But some people checked for an empty list as their *only* base case test. In any problem involving trees, you have to consider leaf nodes as a base case! * Some people used things like (NUMBER? (CAR COMPUTATION)) as the base case test. It's possible to write a working procedure with that approach, but it's much harder to avoid bugs, and the result is very hard to read and understand. Perhaps you were influenced by the fact that the domain is supposed to be lists, which is true, but it doesn't hurt to extend the domain if that improves the structure of the procedure. Other people thought that something like (3) -- a list of one element -- could be an argument, but the problem statement says "either a number or a list of three elements," not "a list of either a number or three elements." The next most common errors were data abstraction violations: * Some people called make-tree with three arguments, following the model of the binary tree ADT in the text. This problem was about the more general tree ADT in which a node can have any number of children, even though in this example the nodes do have only two. [Why would that make sense? Maybe this procedure is part of a larger program in which we also generate expression trees from Scheme expressions like (+ 3 4 5 6).] * Others applied the selectors DATUM and CHILDREN to the procedure's argument, which is *not* a tree. It's just as much a data abstraction violation to use it when not appropriate as to not-use it when it is appropriate. But the worst error that came up more than once is to say one of these: ((treeify (car computation)) (treeify (cadr computation))) '((treeify (car computation)) (treeify (cadr computation))) instead of calling LIST. If you don't understand why that's wrong, ask your TA to meet with you. (b) The most common error here was to think that the domain of the procedure should be computation lists, like the domain of TREEIFY, instead of trees. To make the solution clearer, I'm going to separate out the timing of an operator as a helper procedure, although that isn't required. (define (op-time operator) (cond ((member op '(+ -)) 1) ((member op '(* /)) 5) (else 0))) Some students treated a datum other than one of the four operators as an error here, which is okay, but this way makes it okay for me to call OP-TIME for a datum that turns out to be a number, which will make the rest of the solution cleaner. The most elegant solution uses higher-order procedures: (define (time tree) (accumulate + (op-time (datum tree)) (map time (children tree)))) That's it! The base case for leaves is handled implicitly by MAP. This uses the version of ACCUMULATE on page 116 of the text. Here's a more straightforward solution: (define (time tree) (if (null? (children tree)) 0 (+ (op-time (datum tree)) (time (car (children tree))) (time (cadr (children tree)))))) The common errors didn't really fall into categories. Here they are: * Trying to add a number to a list, like this: (+ (op-time (datum tree)) (map time (children tree))) The value returned by MAP is a list, not a number, so it's not in the domain of +. You have to use something like ACCUMULATE to add up all the numbers in the list. * Confusing the symbols +, -, etc. with the procedures that are the values of those variables. So for example you can say (eq? (datum tree) '+) but not (eq? (datum tree) +) * A related mistake of a different sort is to expect Scheme to evaluate those symbols when they appear in a list, like this: (let ((+ 1) (- 1) (* 5) (/ 5)) (+ (datum tree) ...)) Aside from the fact that the addition won't happen, because you've changed the meaning of the symbol + so that it no longer means addition, the value of (datum tree) is the symbol at that node, not whatever value that symbol might have as a variable. For example, what do you expect to be the value of this expression: (let ((a 5)) (car '(a b c))) The answer is A, not 5. This mistake is similar. * A minor mistake is using EQ? to compare numbers. Use = for numbers, EQ? for symbols. * You can't solve a tree problem iteratively! (Strictly speaking that isn't true; if you're really clever and perverted you can write an iterative procedure that uses lots of extra data structures. But nobody did that, and you can't do the naive sort of iteration that you did try.) Solutions like (define (time tree) (define (time-helper tree count) ...) (time-helper tree 0)) at best consider only one child of each branch node, and more often lose both branches. The hallmark of tree problems is that there is more than one recursive call in the procedure. Scoring: 7 correct. 6 one really tiny error, or correct except for a mistake in the base case. 5 no base case at all but otherwise correct, or data abstraction violations in working code. 3-4 one part (treeify or time) works, or both parts almost work. 1-2 neither works, but some understanding shown. 0 even worse. 2. Adding data abstraction. (a) You were asked to implement the TRIAL data type, not the QUEUE data type. (define make-trial list) (define trial-nums car) (define trial-sum cadr) (define trial-rest caddr) Of course you can choose different names, but the implementation has to use list, car, cadr, caddr because you are told "Each trial is a list of three elements..." We didn't deduct points if you *separately* implemented a queue ADT, something like this: (define make-new-queue list) (define append-queues append) (define queue-first car) (define queue-rest cdr) but that wasn't required. People who tried it generally failed to notice that the two places in ADDUP that create queues do it differently, so two constructors are needed. What we DID deduct for is a mixed type, a queue-of-trials, like this: (define trial-nums caar) ; wrong! (define trial-sum cadar) (define trial-rest caddar) That was the most common error. Two others that came up in several papers: * Moving some of the algorithm of ADDUP into the constructor, like this: (define (make-trial queue) ; wrong! (map (lambda (new) (list (cons new (caar queue)) (+ new (cadar queue)) (remove new (caddar queue)))) (caddar queue))) * A really really bad error was to chop random pieces of code out of ADDUP and try to use them out of context, like this: (define queue (list trial)) ; very wrong! (define trial (car queue)) Where do you think your definition of QUEUE finds a value for TRIAL? These alleged constructors and selectors aren't even procedures. We gave zero points to any solution that included things like this. (b) Rewriting ADDUP. Since you were given such a narrow task, rewriting existing procedures to use the trial ADT, there is only one possible correct solution: (define (addup nums goal) (addup-helper (list (MAKE-TRIAL '() 0 nums)) goal)) (define (addup-helper queue goal) (cond ((null? queue) #f) ((eq? (TRIAL-SUM (car queue)) goal) (TRIAL-NUMS (car queue))) (else (addup-helper (append (cdr queue) (map (lambda (new) (MAKE-TRIAL (cons new (TRIAL-NUMS (car queue))) (+ new (TRIAL-SUM (car queue))) (remove new (TRIAL-REST (car queue))))) (TRIAL-REST (car queue)))) goal)))) The invocations of the new constructor (twice) and of the new selectors (six times) are capitalized above. There were three common kinds of errors here: * missing some of the changes * not using (car queue) as the argument to the selectors * using the new constructor or selectors where inappropriate A less common error was to insert the names of selectors in the code but not invoke them, or invoke them with no argument at all. By the way, we made an error in the original procedure; we should have used = rather than EQ? in the second COND clause. Scoring: Two points off for each of the following: * part (a): bad ADT * part (b): missing some of the changes * part (b): not using (car queue) as the argument to the selectors * part (b): using the new constructor or selectors where inappropriate Anything worse than that got zero. In some cases we took off an odd number of points if two errors seemed related in a way that made it seem unfair to subtract two points for each one. 3. Data-directed disassembler (define (assembly instruction) (let ((op (list-ref ops (car instruction)))) (printer (cons (car op) (cdr instruction)) (cadr op)))) You don't have to use the LET (instead calling list-ref twice) but really there is no other good solution. We allowed NTH in place of LIST-REF, but you should really learn LIST-REF, which is the Scheme standard for selecting an element from a list. The crucial point is that ASSEMBLY is data-directed in the sense that it looks up the opcode in the table OPS instead of checking explicitly for each possibility. (PRINTER is also data-directed in that it uses the information from OPS to determine the order in which operands are printed, but you didn't have to write that part.) For the most part people either got the point or didn't. There were a few minor errors, e.g., LIST instead of CONS or CDR instead of CADR. The most common major error was to think that because the problem says "data directed" it has to use PUT and GET. Scoring: 3 correct 2 has the idea 1 has an idea 0 other 4. Box & pointer diagrams > (append '(a b) '()) (A B) --->XX----->X/ | | V V A B The empty list has no elements, so it doesn't contribute anything to the APPEND. > (cons '(a b) '()) ((A B)) --->X/ | V XX----->X/ | | V V A B The pair at the top, to which the initial arrow points, is the one created by the CONS. There are two ways to think about this: (1) CONS adds one new element at the front of an existing list. In this case, the existing list was empty, so CONS creates a one-element list. (2) CONS always creates exactly one pair, whose car and cdr are the two arguments. In this case the car is (A B) and the cdr is the empty list. A few people got that part wrong because they showed the printed result in dotted form: ((a b) . ()). Scheme never prints a dot followed by an open parenthesis! It uses list notation instead. > (list '(a b) '()) ((A B) ()) --->XX----->// | V XX----->X/ | | V V A B The two pairs in the top row are the ones generated by LIST. It always creates a list whose length is the number of arguments, which is two in this example. The first element is (A B); the second is the empty list. That second pair has a slash in both boxes; the slash in the car means that the empty list is an element; the slash in the cdr means that this is the end of the top-level list. We did accept notations such as ... --->X/ | V / but in fact there's no reason to denote an empty list in the car of a pair differently from an empty list in the cdr! > (caadr '((1 2) (3 4))) 3 The "box and pointer diagram" is also just 3 in this trivial case, since there are no pairs in the result. (cdr '((1 2) (3 4))) --> ((3 4)) (car '((3 4))) --> (3 4) (car '(3 4)) --> 3 Scoring: one point each. No more than one point off for leaving the initial arrow out of all the diagrams. ----------------------------------- If you don't like your grade, first check these solutions. If we graded your paper according to the standards shown here, and you think the standards were wrong, too bad -- we're not going to grade you differently from everyone else. If you think your paper was not graded according to these standards, bring it to Brian or your TA. We will regrade the entire exam carefully; we may find errors that we missed the first time around. :-) If you believe our solutions are incorrect, we'll be happy to discuss it, but you're probably wrong!