• taking a practice exam that is similar to the type of exam you will take in the same amount of alloted time
• going over the exam to answer any questions you have
• answering questions you may have on the 1st in class quiz you took on Monday, March 26th
• answering questions you may have on homeworks

1. Write a procedure each-greater that takes two lists of numbers and checks that every number in the first list is larger than the corresponding number in the second list. Assume all the entries in both lists are numbers and that the two lists have the same length. For example:

     STk> (each-greater '(15 8 9 4) '(5 4 6 2)) 
     #T ; because  15>5, 8>4, 9>6, 4>2
     STk> (each-greater '(10 20 30) '(1 20 13)) 
     #F ; because  20=20 violates the condition
   
   

2. Write a procedure every-other that returns every other element from a list, starting from the second one. If the list has a single element it should return an empty list. The list can have either an even or an odd number of elements. For example,

     STk> (every-other (list 3 5 7 9) )   
     (5 9)
     STk> (every-other (list 'a 'b 'c) )  
     (b)
     STk> (every-other '(a) )  
     ()
     STk> (every-other '() )  
     ()
   
   

3. Write a procedure (interleave list1 list2) to combine two lists into a single list in an alternating manner. Assume that the two lists have the same length. Your interleaved list may start with an element from either list, but should be consistent throughout. For example:

     STk> (interleave '(1 2 3) '(a b c)) 
     (1 a 2 b 3 c)
     STk> (interleave '() '()) 
     ()
   
   

4. Write a procedure (count-additions tree) that takes as argument an arithmetic expression written in scheme using prefix notation and counts the number of additions present in the expression. For example:

     STk> (count-additions 'e) 
     0
     STk> (count-additions '(* e r)) 
     0
     STk> (count-additions '(* (+ 1 2) (+ 9 e))) 
     2
     STk> (count-additions '(+ (* 4 e) (/ (+ a b) (+ c d)))) 
     3
   
   

5. Write a procedure (make-accumulator init) that returns a procedure which is an accumulator. i.e. a procedure that when called with a numeric argument accumulates its argument into a sum. When multiple accumulators are created, each should maintain its sum independently of the others [Hint: you need to maintain the local state]. It should work like this:

     STk> (define a1 (make-accumulator 0))
     a1
     STk> (a1 4) 
     4 ; since 4 is 4+0
     STk> (a1 10) 
     14 ; since 14 is 4+10
   
   

6. Student records for three colleges in the same university system are combined in a common database. The student records for each college differ in their representation of the birthdate sub-records.

   College 1 uses format1 for the birthdate: (list `3-letter-month-name day year)
   for example: (`Mar 1 1985)
   College 2 uses format2 for the birthdate: (list year month day)
   for example: (1985 3 1)
   College 3 uses format3 for the birthdate: (list month day year-in-2-digits)
   for example: (3 1 85)

   You have been hired by central administration to tag all the birthday records with the labels `format1, `format2, or `format3 according to the type of the birthday format. This will make it easy for an application to recognize the various formats.

   a) Write a procedure (attach-birthday-tag birthday-record) which will take a birthday-record, automatically detect which format is being used, and return the birthday-record with the appropriate tag attached. You may find the (number? x) predicate useful.

   b) Write a generic selector (get-year birthday-record) which will return the year of birth as a four-digit integer, regardless of the birthday-record format. You may assume that all birthdates occurred during the 20th century--that is, during the 1900's.

7. (This question is a bit tougher.) Below is some message passing code for representing sets as unordered lists without repetitions.

   (define (make-unordered-set lst)
   
     (define (empty?) (null? lst))
   
     (define (element-of-set? x) (member x lst))
   
     (define (dispatch op)
       (cond ((eq? op 'empty?) empty?)
             ((eq? op 'count) (length lst))
             ((eq? op 'element-of-set?) element-of-set?)
             (else "unknown op")))
   
     dispatch)
   
   (define s1 (make-unordered-set (list 1 2 3)))
   

   Extend this representation to include an operation same-set? to determine if two sets in this representation contain exactly the same elements.
   

Copyright: © 2006 by the Regents of the University of Minnesota
Department of Computer Science and Engineering. All rights reserved.
Comments to: Maria Gini
Changes and corrections are in red.