CS 3 Final exam solutions 1. What will Scheme print? > (caddar '((a b c d e f) (g h i j k l) (m n o p q r)) C (car '(...)) ==> (a b c d e f) (cdr '(a b c d e f)) ==> (b c d e f) (cdr '(b c d e f)) ==> (c d e f) (car '(c d e f)) ==> c Note, (C) is wrong. 'C is wrong. '(C) is wrong. Just C. > (append (list '(a b) '(c d)) (cons '(e f) '(g h))) ((A B) (C D) (E F) G H) (list '(a b) '(c d)) ==> ((a b) (c d)) (cons '(e f) '(g h)) ==> ((e f) g h) > (every lambda (x) (item x '(a b c d e f g h))) 2514) (B E A D) Numbers are words! > (keep (lambda (x) (even? (count x))) '(john paul george ringo)) (JOHN PAUL GEORGE) Keep the ones with an even number of letters. > (leaf? (make-node '(a b) '())) #T If it has no children (the second argument to make-node) then it's a leaf node. > (filter (lambda (x) #t) '(back in the ussr)) (BACK IN THE USSR) This says "keep every element of the list" because the predicate always returns true. Scoring: 1/2 point each, round up. 2. Which can be used in (repeated _____ 4)? cdr: YES. ((repeated cdr 4) '(the continuing story of bungalow bill)) ==> (BUNGALOW BILL) cons: NO. Repeated can only be used with functions of one argument. even?: NO. The domain of EVEN? is numbers, and its range is Booleans, so (even? (even? 12)) would be an error. (lambda (x) (* x x)): YES. (repeated ... 4) is the function that takes its argument to the 16th power. ((repeated (lambda (x) (* x x)) 4) 3) ==> 43046721 random: YES. It's a little silly, but ((repeated random 4) 1000) would be expected to give numbers around 60, on average. (But *sometimes* it gives an error.) length: NO. The domain of LENGTH is lists, and its range is numbers, so (length (length '(the night before))) is an error. Scoring: 1/2 point each, rounded down. 3. Middle word of a sentence. (define (middle sent) (if (< (count sent) 3) (first sent) (middle (bl (bf sent))))) ;;;;;;;;;;; OR ;;;;;;;;;;;;;;;; (define (middle sent) (item (quotient (+ (count sent) 1) 2) sent)) Or several variations on either of these, including the use of REPEATED to reinvent ITEM, and the use of EVEN? to deal with the possible remainder separately. The most common one-point-off error was to return SENT rather than (FIRST SENT) in the base case. Even if the sentence only has one word in it, a one-word sentence isn't the same thing as a word, which is what you were asked to return. QUOTIENT computes an integer quotient, discarding any fractional part of the result. If you use / instead, it's harder to get right. 4. Check whether a two-arg predicate holds for every pair in a list: (define (pairs-checker pred) (lambda (lst) (true-for-all-pairs? pred lst))) (define (true-for-all-pairs? pred lst) (cond ((null? lst) #t) ((null? (cdr lst)) #t) ((pred (car lst) (cadr lst)) (true-for-all-pairs? pred (cdr lst))) (else #f))) Since true-for-all-pairs? was a homework problem, this should have been pretty easy. A common mistake was to try true-for-all? instead. That would make sense only for one-argument predicates, not two-argument ones. Another way to do it, without needing a helper function, is this: (define (pairs-checker pred) (lambda (lst) (cond ((null? lst) #t) ((null? (cdr lst)) #t) ((pred (car lst) (cadr lst)) ((PAIRS-CHECKER PRED) (cdr lst))) (else #f))) The changed part is in capital letters. It's an interesting use of recursion. Notice that there are two sets of parentheses enclosing the capital letters; the inner one invokes pairs-checker, returning a predicate, and the outer one applies that predicate to (cdr list). Scoring: The worst mistake was to return something other than a procedure, i.e., not to use lambda. The maximum possible score with that error was 2, and most got even less. 5. Two consecutive elements twice? (define (samepairs? lst) (cond ((< (length lst) 3) #f) ((mem2? (car lst) (cadr lst) (cdr lst)) #t) (else (samepairs? (cdr lst))))) (define (mem2? a b lst) (cond ((null? (cdr lst)) #f) ((and (equal? a (car lst)) (equal? b (cadr lst))) #t) (else (mem2? a b (cdr lst))))) I thought this was an easy problem, but I was surprised to see a lot of messy answers, even among the ones that worked. One too-common error was to think that member? means subset?: > (member? '(b c) '(a b c d)) #F (b c) is *not* a member of (a b c d)! Another common error was to check whether a pair of consecutive elements occurs *anywhere* in the original list, rather than only in the part of the original list to the right of their first appearance. Most solutions that started something like (define (samepairs? lst) ;; wrong (helper lst lst)) were of that sort. Many people used APPEARANCES. Strictly speaking, this is ruled out by the problem statement, which says that samepairs? should work for *lists*, not words and sentences, which are the domain of appearances. But we gave credit if you got it to work, which most people didn't. Most such solutions didn't insist that the second appearance of the two elements be consecutive, so they would return #T for all three of the examples shown in the exam, instead of returning #F for the second one, as a correct solution does. Messy but correct solutions involved making a list of pairs of elements. (There were also some incorrect solutions along those lines.) A similar approach is like the one shown above, but with an unnecessary creation of a list of two elements, which are then broken out: (define (samepairs? lst) ;; weird (cond ((< (length lst) 3) #f) ((mem2? (LIST (car lst) (cadr lst)) (cdr lst)) #t) (else (samepairs? (cdr lst))))) (define (mem2? PAIR lst) (cond ((null? (cdr lst)) #f) ((and (equal? (CAR PAIR) (car lst)) (equal? (CADR PAIR) (cadr lst))) #t) (else (mem2? PAIR (cdr lst))))) This works but is harder than necessary. Several people combined all the elements into one long word, with (ACCUMULATE WORD ...), and then looked in that word for a substring with the desired pair. Aside from the general point about the argument being a list, not a sentence, there is a second problem with this approach: Suppose the argument list is (abc def x y ab cdefg z w) Your program will think that AB CDEFG is a second appearance of ABC DEF. People were misled by the fact that the examples shown had one-letter words, but that wasn't part of the problem description. 6. Find the largest number of children of any node in a tree. (define (max-children tree) (if (leaf? tree) 0 (max (length (children tree)) (reduce max (map max-children (children tree)))))) That's the easiest way. If you want to use mutual recursion with a procedure that works on forests, it'd look like this: (define (max-children tree) (max (length (children tree)) (max-children-in-forest (children tree)))) (define (max-children-in-forest forest) (if (null? forest) 0 (max (max-children (car forest)) (max-children-in-forest (cdr forest))))) The worst problems were no tree recursion (at most 1 point) and using cheap trees (that is, taking the car or cdr of a tree, at most 2 points). We were particularly unsympathetic to solutions that invoked + anywhere, since we take this to mean that you copied something out of the book without understanding it. 7. vector-deep-member? (define (vector-deep-member? thing vec) (vdm-help thing vec (- (length vec) 1))) (define (vdm-help thing vec index) (cond ((< index 0) #f) ((equal? thing (vector-ref vec index)) #t) ((and (vector? (vector-ref vec index)) (vector-deep-member? thing (vector-ref vec index))) #t) (else (vdm-help thing vec (- index 1))))) By far the most common mistake was to replace the third COND clause with ((vector? (vector-ref vec index)) ;; wrong (vector-deep-member? thing (vector-ref vec index))) The trouble with this is that if an element is a vector, but that sub-vector doesn't contain THING, then you just return false without looking at later elements that might contain it. In the example in the exam, as soon as you notice that 3 is not an element of #(27 92), you return #f without looking at the rest of the big vector. But if you made this mistake, don't feel too bad; all the TAs did, too. Another common small mistake was to use (length vec) as the largest possible index, rather than one less than that. A more serious mistake was to allow elements of vectors only two deep, instead of at any depth. People who did that also often thought that MEMBER? works for vectors. It doesn't! Worst of all were the people who modified the argument vector (by using vector-set!). Why would you do that? 8. Satisfiability. This is the standard computer science example of a problem that's hard for computers -- not meaning that it's hard to write the program, but rather that it takes a long time for the computer to carry out the program. Adding one more argument to the predicate doubles the time required. (define (satisfiable? pred num-args) (not (null (filter (lambda (args) (apply pred args)) (all-tf num-args))))) (define (all-tf num) (if (= num 0) '(()) ;; a list containing an empty list (let ((small (all-tf (- num 1)))) (append (map (lambda (x) (cons #t x)) small) (map (lambda (x) (cons #f x)) small))))) Most people didn't even try this one. Among people who had the general idea, the most common error was to get the arguments to append wrong in all-tf, e.g., (append (cons #t small) (cons #f small)) ;; wrong Instead of using FILTER, some people tried it with MAP: (and (map (lambda (args) (apply pred args)) (all-tf num-args))) ;; wrong (reduce and (map ...)) ;; also wrong The first of these is wrong because AND takes individual Booleans as arguments, not one list of Booleans. The second would be correct except that AND is a special form, so it can't be an argument to REDUCE. Hardly anyone remembered to say (apply pred args) instead of (pred args). The latter is wrong for the same reason as (and (map ...)): pred takes individual Booleans as arguments, not a list of Booleans. Scoring: If you had ALL-TF right but completely messed up SATISFIABLE?, you got three points. If the other way around, you got two points.