Comp210: Principles of Computing and Programming
Fall 2004 -- Homework #6

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!

(15 pts) Functions Processing Family Trees
Using the following data definition of FamTree (for more details, see Lecture 14 )

;; A FamTree is 

;; - Unknown

;; - (make-child sym num FamTree FamTree)



;; Unknown is an empty FamTree

(define-struct Unknown (label))



;; a Child is a structure where

;; name is the name of a person

;; year is their birthyear

;; ma is a FamTree representing the person's mother

;; pa is a FamTree representing the person's father

;; (make-Child sym num FamTree FamTree)

(define-struct Child (name year ma pa))

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 are gen=2, etc.

(define-struct NamGen (name gen))

Write the function

;; earliest: FamTree --> NamGen 

;; Returns the name and generation of the earliest known 

;; (farthest back generation) person in the family tree.
;; If there are more than one people with the same earliest 

;; generation value, return any one of those people.

(define (earliest aFamTree) ...)

(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. (50 pts total) Consider the following data definition of a generalized list of symbols:
```
;; A GenList is either a

;; -- symbol

;; -- NSGenList

        

;;A NSGenList (Non-Symbol GenList) is either

;; -- 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.

Last Revised Tuesday, 24-Aug-2004 13:49:11 CDT

Comp210: Principles of Computing and Programming Fall 2004 -- Homework #6

Comp210: Principles of Computing and Programming
Fall 2004 -- Homework #6