COMP 210 Homework #6

Fall 2002

Due Mon., Oct. 7. at the start of class

All problems will require all (applicable) steps from the design recipe, including a template. Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks (in particular: staple and provide questions), and the Grading Guidelines.

A short homework assignment for this week due to the exam.

Remember: Contract, purpose, header and test cases are always required!

1. (15 pts) Functions Processing Family Trees

   Using the following data definition of FamTree

A FamTree is

-- (make-unknown symbol)       
-- (make-child symbol number famTree famTree), where the symbol represents a name, the first FamTree is the mother's family tree, the second FamTree is the father's side, and the number is the birthyear.


And the following data definition for a Name+Generation tuple:

A NamGen is a (make-NamGen sym num) where name is the name of a person and gen is the generation number as measured from the root of some specified FamTree. That is, the child at the root of the FamTree is gen=0, their parents are gen=1, grandparents gen=2, etc.
(define-struct NamGen (name gen))

write a function earliest: FamTree --> NamGen, which returns the name and generation of the earliest (farthest back generation) known person in the family tree.

2. (75 pts total) Function of Two Non-trivial Inputs and Mutual Recursion
   
   
   1. (10 pts) Write a function that returns the n'th element of a list, or false if it is not in the list.
      
      
   2. (15 pts) Write a function that will "zip" to 2 lists together, that is
      (equal? (list 1 3 2 4) (zip (list 1 2 ) (list 3 4))
      Your function must be able to take all lists, including lists of unequal length and have well defined behavior for all lists. You need not specify which list's first element will appear first in the result, though if you can specify this, you may.
      
      
   3. (45 pts total) Consider the following data definition of a generalized list of symbols:
      ;; A GenList is
      ;; -- symbol
      ;; -- NSGenList
      
      ;;A NSGenList (Non-Symbol GenList) is
      ;; -- empty
      ;; -- (cons GenList NSGenList)
      
      GenList can be either just a symbol or a list of lists of lists of.lists of....of symbols.
      
      
      1. (5 pts) Draw the UML diagram for GenList and NSGenList
         
         
      2. (5 pts) Write the template for a function that processes a GenList. Note: list? can be used to detect a NSGenList.
         
         
      3. (10 pts) Write the template(s) for a function taking two GenLists, based on a Process Flow Analysis (see Lecture 15 and Lecture 16).
         
         
      4. (15 pts) Based on your templates, write a function, eqGL? that compares two GenLists and returns true if the two GenLists are the same. You may omit helper functions if they would consist of only one line of code.
         
         
      5. (10 pts) Write the same eqGL? function but with a single multi-way cond statement. Call this implementation "eqGL2?". You do not need to rewrite the contract, header and purpose, but you do need to test it against the same test suite used on eqGL?.
         
         
      6. (5 pts) Rewrite the above multi-way cond implementation by simplifying the cond statement. Call this implementation "eqGL3?". Once again, you do not need to rewrite the contract, header and purpose, but you do need to test it against the same test suite used on eqGL?.
         
         

   Pondering for the day: What's the difference between a GenList and expressions in Scheme?

90 points total.