CSC 171
Homework 6

Assigned Mar 17, due Mar 24

This assignment will involve the material of chapters 14-19: lists of lists, multiple lists, local definitions, and generalizing functions.

This assignment may be done in pairs, following the principles of Pair Programming. Turn in one assignment with both students' names on it.

Programming

For all the programming assignments, be sure to follow the design recipe. Write your function contract, examples, and function definition in the Definitions Window, save it to a file, and e-mail me this file. Also test your program: since you've already included examples in the Definitions window, you should be able to hit the Run button and see all the results (along with what you said they "should be"). Save the resulting Interactions window to a text file and e-mail me this file too. Be sure to choose meaningful names for functions and parameters, and watch for opportunities to re-use functions you, I, or the textbook have already written.

Also turn in a log of how many errors of different kinds you encountered in the assignment, with brief comments describing each one ("mismatched parentheses" is self-explanatory, but more complex errors might need more description). You may do this using the PSP forms, or simply by keeping track in a text file or on paper and turning it in.

• Do problem 12.4.2 in the textbook (rearranging words). Note that the textbook has already developed the function arrangements (which I named perms in class); in fact, we've already developed insert-everywhere-in-all-words in class, but it requires another function insert-everywhere-in-one-word, which may in turn require its own auxiliary function.

• Copy the definitions of the person and unknown structures from my lecture notes (lecture 21 or lab 21), and develop the following functions:

  count-ancestors : ftree -> number

  which tells how many people are in the tree, not counting unknowns. Note that a person does count as his/her own "ancestor"; trust me, that makes it easier.

  earliest-year : ftree -> number

  which finds the earliest birth year of anyone in the tree

  eye-colors : ftree -> list of strings

  which produces a list of all the eye colors that appear in the family. If there are three blue-eyed people in the family, the word "blue" should appear three times in the list.

  ftree=? : ftree ftree -> boolean

  which tells whether two ftrees are the same, i.e. they have exactly the same names, eye colors, birth years, and parental relationships.
  Hint: Read chapter 17 before trying this!

  Note: for each of these, you may write two separate functions (one for ftree and one for person), or "smoosh them together" into one function; I would prefer that you do at least one each way.

• In a separate definitions window, copy the definitions of person and person-list for top-down family trees from my lecture notes (lecture 22 or lab 22), and develop the following function:

  count-descendants : person -> number

  which tells how many people are in the tree. A person does count as his/her own "descendant".
  You'll need an auxiliary function count-descendants-in-list which operates on a person-list.

• Choose one of the above functions that needed an auxiliary function, and rewrite it using local to hide the auxiliary function. (For example, count-descendants might be rewritten as count-descendants-with-local, so you can keep them both in the same definitions window.) You won't be able to write test cases for the auxiliary function, but all the test cases for the main function should still work.

• Read chapter 17 of the textbook, and develop the following functions:

  cross: list-of-strings list-of-numbers -> list-of-lists

  (see problem 17.1.2 in the textbook)

  dot-prod: list-of-numbers list-of-numbers -> number

  Takes in two equal-length lists of numbers, multiplies corresponding numbers, and adds up the results. For example,
  (dot-prod (list 1 2 3) (list 4 5 6)) should be 1*4+2*5+3*6 = 4+10+18 = 32

  merge: sorted-list-of-nums sorted-list-of-nums -> sorted-list-of-nums

  (see problem 17.6.1 in the textbook)

  intersect: list-of-nums list-of-nums -> list-of-nums

  Finds all the numbers that are in both of the original lists. For example,
  (intersect (list 3 8 0 4 2) (list 5 4 -1 8 2)) should be (list 8 4 2) or some other ordering of those three numbers.