Here is the exam for reference:

Check out and compare to the .

I graded this year's final on a 120-point scale, and last year's on 60-points, so you have to scale by 2. That was just an accident---the grading plan is essentially the same this year as last year. This year's scores are 112, 101, 100x2, 96, 79, 78, 77, 76, 71, 65, 63, 59, 53, 48, 39, 15 (mean 72.5, median 76). I alloted 20 points to each of the numbered problems.

Grade cutoffs this year will probably be similar to 2002. The 2002 class was unusually strong, so that will probably not lead to as large a number of As. The scores above 70 are very strong, and likely to lead to Bs and some As.

1. Part A is exactly the same as the midterm problem 1C.
   
   In part B it's possible to write two separate functions for the sum and for the product, and then list the two results. But the problem is to define each function "directly by applications of the higher-order procedures." I gave 3/5 points for the separate functions.

   
   (define sum_and_product
     
     (eval_binary_tree
      
      (lambda (x y) (list (+ (first  x) (first  y))
                          (* (second x) (second y))
                          )
        )
      
      (lambda (x) (cond ((number? x) (list x x))
                        (else        (list 0 1))
                        )
        )
      )
     )      
   

   
   
   Part C exercises a very common algebraic form: accumulation of one operation (+ after another (*) has been applied pointwise (mapped. The dot product operation on vectors is probably the most commonly used function of this form. It's a very good idea to learn to recognize this pattern.

   
   (define (dot_product lst1 lst2)
     
     ((accumulate_lr 0 (lambda (x) x) +) (map * lst1 lst2))
     )
   

   
   
   Part D applies the accumulate after map pattern in a slightly more complicated form.

   
   (define (list_repeats lst1 lst2)
     
     ((accumulate_lr empty (lambda (x) x) append)
      (map (lambda (x y) (cond ((= x y) (list x)) (else empty))) lst1 lst2)
      )
     )
   

   
   
   
2. Many of you provided noniterative solutions. I awarded up to 3/5 points for perfect noniterative solutions, but with the opportunity to read the instructions a week in advance, you should make sure not to misunderstand such a question. And it's very important to be able to distinguish an iterative solution from a noniterative one.
   
   There are a number of variant solutions to part A. My favorite because it's elegant:

   
   (define (sum_diagonal lstlst)
     
     (define (sd sum lstlst)
       
       (cond ((empty? lstlst) sum)
             
             (else            (sd (+ sum (first (first lstlst))) (map rest (rest lstlst))))
             )
       
       )
     
     (sd 0 lstlst)
     )
   

   The most straightforward (and therefore probably the best to use in a real project):

   
   (define (sum_diagonal lstlst)
     
     (define (select n lst)
       
       (cond ((= n 1) (first lst))
             (else    (select (- n 1) (rest lst)))
             )
       )
     
     (define (sd sum count lstlst)
       
       (cond ((empty? lstlst)
              sum)
             
             (else            
              (sd (+ sum (select count (first lstlst)))
                  (+ count 1)
                  (rest lstlst)
                  )
              )
             )
       )
     
     (sd 0 1 lstlst)
     )
   

   A final exercise, to show that every nested iteration (the previous solution nests the iteration of select into the iteration of sd) can be written as a single unnested iteration. In a conventional procedural programming language, each nested level of iteration is a for loop.

   
   (define (sum_diagonal lstlst)
     
     (define (sd sum countrow countcol lstlst)
       
       (cond ((empty? lstlst)
              sum)
             
             ((= countrow countcol)
              (sd (+ sum (first (first lstlst)))
                  (+ countrow 1)
                  1
                  (rest lstlst)
                  )
              )
             
             (else            
              (sd sum
                  countrow
                  (+ countcol 1)
                  (cons (rest (first lstlst)) (rest lstlst))
                  )
              )
             )
       )
     
     (sd 0 1 1 lstlst)
     )
   

   
   
   In part B, lots of people presented noniterative solutions. There's a good argument for using the noniterative solution here (unless there's a very good implementation of append), but the exercise was to see how to do it iteratively.

   
   (define (merge_lists lst1 lst2)
     
     (define (ma mlst lst1 lst2)
       
       (cond ((empty? lst1)
              (append mlst lst2)
              )
             
             ((empty? lst2)
              (append (mlst lst1))
              )
             
             ((< (first lst1) (first lst2))
              (ma (append mlst (list (first lst1))) (rest lst1) lst2)
              )
             
             (else
              (ma (append mlst (list (first lst2))) lst1        (rest lst2))
              )
             )
       )
     
     (ma empty lst1 lst2)
     )
   

   
   
   Part C has exactly the same form as the iterative fast power operation that we studied. Just replace 1 with 0, * with +. Well worth figuring out on your own if you didn't see it during the exam.
   
   
3. The essence of all problems with the intset abstraction is that it provides no direct way to get a member of a set. That's what you should have focused on when studying the guide. You have to search for members. You can tell when you've found them all, either by removing them until a set is empty, or by counting up to the size given by intset_size.
   
   Part A is exactly the solution of the essential problem above. (I haven't tested these yet, but I think I have them right.) Here's a sort of minimalist solution, using only empty_intset?, member_intset?, and remove_intset, keeping as much information as possible in the intset representation. There's no particular reason to do it that way, it's just one way to generate a solution.

   
   (define (intset->list is)
   
     (define (list_if_member n is)
   
       (cond ((member_intset? n is) (list n))
              (else                  empty)
             )
       )
   
     (define (list_intset_geq->list lst is n)
   
       (cond ((empty_intset? is) lst)
   
             (else        (list_intset_geq->list
                           (append (list_if_member n       is)
                                   (list_if_member (- 0 n) is)
                                   lst
                                   )
                           (remove_intset n (remove_intset (- 0 n) is))
                           (+ n 1)
                           )
                          )
             )
       )
   
     (append (list_if_member 0 is)
             (list_intset_geq->list empty 1 is)
             )
     )
   

   It probably makes more sense to use a nice iterator (nextint) to produce positive and negative integers in the standard natural order 0, 1, -1, 2, -2, ...

   
   (define (nextint n)
   
     (cond ((< n 0) (- 1 n))
           (else       (- 0 n))
           )
     )
   
   (define (intset->list is)
   
     (define (list_intset_after->list lst is n)
   
       (cond ((empty_intset? is)
              lst
              )
   
             ((member_intset? n is)
              (list_intset_after->list (cons n lst)
                                       (remove_intset n is)
                                       (nextint n)
                                       )
              )
   
             (else
              (list_intset_after->list lst
                                       (remove_intset n is)
                                       (nextint n)
                                       )
              )
             )
        )
   
     (list_intset_after->list empty is 0)
     )
   

   The number of steps is a bit odd. It is not determined by the size of is. Rather, it is roughly the largest absolute value of a member of is.
   
   Once you've got intset->list above, you've cracked the essence of intset computation, and just need to deploy it appropriately.
   
   Part B:

   
   (define (intset_union is1 is2)
   
     (define (add_list_intset lst is)
   
       (cond ((empty? lst)
              is)
   
             (else
              (add_list_intset (rest lst)
                               (insert_intset (first lst) is)
                               )
              )
             )
       )
   
     (add_list_intset (intset->list is1) is2)
     )
   

   There is an odd asymmetry here. The rough number of steps is the largest absolute value of a member of is1, and has nothing to do with is2 (although each particular implementation of intset may give is2 an impact on the number of steps below the abstraction barrier).
   
   Part C:

   
   (define (intset_intersection is1 is2)
   
     (define (filter_list->intset lst isin isout)
   
       (cond ((empty? lst)
              isout)
   
             ((member_intset? (first lst) isin)
              (filter_list->intset (rest lst)
                                   isin
                                   (insert_intset (first lst) isout)
                               )
              )
   
             (else
              (filter_list->intset (rest lst)
                                   isin
                                   isout
                               )
              )
   
             )
       )
   
     (filter_list->intset (intset->list is1) is2)
     )
   

   Number of steps roughly the largest absolute value of a member of is1.
   
   You might prefer a symmetric solution:

   
   (define (intset_intersection is1 is2)
   
     (define (union_intersect_intset_after is1 is2 isout n)
   
       (cond ((empty_intset? is1)
              isout)
   
             ((empty_intset? is2)
              isout)
   
             ((and (member_intset? n is1) (member_intset? n is2))
              (union_intersect_intset_after
               is1 is2
               (insert_intset n isout)
               (nextint n)
               )                          
              )
   
             (else
              (union_intersect_intset_after
               is1 is2
               isout
               (nextint n)
               )
              )
             )
       )
   
     (union_intersect_intset_after is1 is2 empty_intset 0)
     )
   

   
   
   
4. Part A:

   
   ((eq? (car expr) 'if)
     (if (eval (cadr   expr) env)
         (eval (caddr  expr) env)
         (eval (cadddr expr) env)
         )
     )
   

   Crucial points: (car expr) is not evaluated. (cadr expr) is evaluated. Exactly one of (caddr expr) and (cadddr expr) is evaluated.
   
   Part B: I should have moved the star up ahead of the (not (pair? fn)). The very superficial answer is that we don't have a pair. The less superficial answer is that the if symbol would be evaluated, which is an error. But we'd fix that, similarly to the way we fixed lambda functions. The important robust answer is that this section of code is for the application of functions to already evaluated arguments. It's crucial to if that it controls the evaluation of the arguments. In LISP/Scheme jargon, if is a special form, rather than a function.
   
   Part C: m repetitions of eval applied to (weird 0) evaluates to (weird m+1). That is, the list of two things, the first of which is the symbol weird, and the second of which is the Scheme integer with the value m+1. I accepted a variety of notations to describe this as long as they were self consistent.



5. Part A: Most of you got these. If you didn't, figure out what happened. This exercise gets at the crux of the impact of rough running time on practical usefulness.

   f1	n^16
   f2	16n
   f3	4n
   f4	2n
   f5	n+4

   
   
   Part B exercises a very common form of efficiency consideration. It is almost always faster to sort collections of data than to search repeatedly in the unsorted forms. same_items1? takes n^2 steps, while same_items2? takes nlogn steps, which is much faster.
   
   
6. Part A: (assign x 0), (frame (bind x) (assign x 0) (f x)). There's no exact replacement for define. (define x 0) has different results depending on whether x is bound in the top frame of the current environment (in which case (assign x 0)) or not bound in the top frame (in which case (begin (bind x) (assign x 0)). Conspire has no way to test for this pre-existing binding without running the risk of failure if x is not bound.
   
   

   
   (define (make-incrementer)
     
     (let ((history empty))
       
       (lambda (n)
         
         (cond ((equal? n 'history) history)
               
               (else (begin (set! history (append history (list n))) (+ n 1)))
               )
         )
       )
     )
   
   (define increment (make-incrementer))
   

   You can also define increment directly, substituting in the code from make-incrementer:

   
   (define increment
     
     (let ((history empty))
       
       (lambda (n)
         
         (cond ((equal? n 'history) history)
               
               (else (begin (set! history (append history (list n))) (+ n 1)))
               )
         )
       )
     )
   

   But you can't succeed in the form

   
   (define (increment n)
     ...
   

   because every use of increment introduces a new frame, and you need a frame that keeps the same copy of history around for all uses of increment.

There will be some repetition of at least one problem identical or highly similar to a problem from the past (2002 midterm, 2002 final, or 2003 midterm).