CS61A Summer 2003 Midterm I Solutions

1.   Recursion Versus Iteration

     Part A: 

     (define (remove index lst)
       (if (= index 1) 
	   (cdr lst)
	   (cons (car lst) (remove (- index 1) (cdr lst)))))

     Part B:

     (define (remove index lst)
       (define (remove-iter index lst result)
	 (if (= index 1)
	     (append result (cdr lst))
	     (remove-iter (- index 1) 
			  (cdr lst) 
			  (append result (list (car lst))))))
       (remove-iter index lst '()))

     There were many solutions that were quite a bit more complicated
     then neccessary. Some sought relationships between the length of
     the list and the index; none exist as far as we can tell. Getting
     the APPEND/LIST business right in Part B was tricky, but most
     people did realize to put the "so-far" variable first. 


2.   Higher-Order Functions

     Part A (2 points):

     (define (make-keeper func)
       (lambda (sent) (keep func sent)))

     Part B (5 points):

     (define (make-keeper func)
       (lambda (sent)
	 (cond ((empty? sent) '())
	       ((func (first sent))
		(se (first sent) ((make-keeper func) (bf sent))))
	       (else
		((make-keeper func) (bf sent))))))

     To our delight, almost everyone got both parts of this problem
     right. The most common mistake was to forget to call the function
     *returned by MAKE-KEEPER* in the recursive cases of Part B. 


3.   Functions and Higher-Order Procedures

     (define (find-func func-list domain range)
       (if (equal? (map (car func-list) domain) range)
	   (car func-list)
	   (find-func (cdr func-list) domain range)))

     Some students wrote helpers to determine the equality of two
     lists, forgetting that the built-in EQUAL? already does this. A
     few people misintrepreted the problem to mean that the Nth
     function in the list of functions should yield the Nth element of
     the range when applied to the Nth element of the domain. We
     should have chosen example calls where the length of the list
     of functions was not the same as the domain/range; instead, we
     wrote on the board during the exam not to make this assumption.

     One person came up with the 100% higher-order function version:

     (define (find-func func-list domain range)
       (car (filter (lambda (f) (equal? (map f domain) range)) func-list)))


4.   Abstraction   

     (define (make-superlist lst)
       (list lst (length lst) (listlast lst)))

     (define (superlist-car suplst)
       (caar suplst))

     (define (superlist-length suplst)
       (cadr suplst))

     (define (superlist-last suplst)
       (caddr suplst))

     The point of this question was to build extra information into
     the superlist at the time of its construction. 

     One person attempted to use a procedural representation for
     superlists:

     (define (make-superlist lst)
       (lambda (which) (which lst (length lst) (listlast lst))))

     (define (superlist-length suplst)
       (suplst (lambda (lst length last) length)))

     However, the body of a procedure is evaluated when the procedure
     is invoked, not when it is made. Hence, each time you supply a
     value for WHICH, all the arguments to WHICH -- lst, (length lst)
     and (listlast lst) -- are evaluated anew. 
     
     A slightly more challenging version of this problem would have
     asked you to write SUPERLIST-CDR, which must itself return a
     superlist:

     (define (superlist-cdr suplst)
        (make-superlist (cdr (car suplst))))


5.   Winning Subsets

     (define (adds-to-n? n lst)
       (cond ((= n 0) #t)
	     ((null? lst) #f)
	     (else (or (adds-to-n? (- n (car lst)) (cdr lst))
		       (adds-to-n? n (cdr lst))))))

     The grading on this problem is as follows:
     Base cases (first two blanks): (3 Points)
     +1: For something reasonable
     +1: Working #t case
     +1: Working #f case
     
     -1: Wrong order for #t/#f case

     Recursive Cases: (4 Points)
     +1: cdr-ing the list
     +1: one of the recursive cases having (- n 1)
     +1: one of the recursive cases leaving n alone
     +1: for having everything correct


6.   Find Dat Bug

     Part A (3 points):
     
     What does (split 'abc) return? (a b)

     Change line 5 to (cond ((empty? wd) (se cur))) to fix. 

     Many people thought calling SE with no arguments is an error or
     returns a procedure. Neither is the case! Many of the built-in
     functions in Scheme that take any number of arguments return
     their identity element when called with none:

     (+) ==> 0
     (*) ==> 1
     (or) ==> #f
     (se) ==> ()

     Part B (4 points):

     Change line 6 to ((equal? (first cur) (first wd)) to fix. 

     There was no other correct answer.