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

Read Sections 9-15 in the H.T.D.P. book.

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.

  1. (25 pts total) Programs on Lists

    First, write down a data definition for lists of numbers, and examples of lists of numbers, and a single template for a list-of-number processing function. Then, develop the following programs that consume a list of real numbers:

    1. (5 pts) A function sum that returns the sum of all the numbers in the list.

    2. (5 pts) A function any-negative? that returns true if and only if ("iff") there is some negative number in the list.

    3. (5 pts) A function all-nonnegative?, which returns true iff every number in the list is zero or positive.
      Hint: use the function you just wrote. This might be even easier than modifying the template.

    4. (10 pts) A function count-multiples that returns the number of multiples of a given number in the list. Hint: use the built-in function modulo (or equivalently, remainder).

      ; (only) one example of calling count-multiples:

(count-multiples 3 (cons 6 (cons 1901 (cons 7 (cons 2001 empty)))))

2    ; Since 6 and 2001 are multiples 3, but nothing else in the list is.

  2. (20 pts) Telephone Directory

    Once a year, the local telephone company publishes a directory. For our purposes, the directory is a list of entries. An entry consists of a symbol, called the key, and a phone number, represented as a number. A key-data pair such as an entry is called a "tuple" is CS-ese. The directory is often called an "association list" or a "dictionary".

    Note: when talking about types of data, this class is precise. Thus be aware that, for this problem, directory and entry are technical terms, each used exactly where intended.

    1. (5 pts) Write out the data definitions, examples, and template pertaining to this simple online phone directory. You should have one data definition for entries, and a second data definition for directories.

    2. ( 5 pts) Write a program lookup that consumes a symbol and a phone directory and should examine the list for a key that matches the symbol given as input. If it finds a matching key, it returns the matching entry. If no matching entry is found, it returns false.

    3. (10 pts) What, exactly, is the type of data returned by lookup? Write a quick data definition for it.

      Write lookup-elvis, which takes in a directory, and returns either Elvis's number in the directory, or 'not-found if Elvis isn't listed).
      Hint: use lookup. Note that once you do so, the more pertinent data template is the type returned by lookup, instead of the template for directories, in this case.

    Be sure to create a reasonable set of test data and enter it in the definitions window of DrScheme.

    For more help (sort of) look up "assoc" in the help desk. No, you cannot use the built-in assoc function!

Note for 2b: The fact that the second part of an entry is a number was irrelevant to lookup; we could actually allow any type of data to be associated with a key -- a symbol, a structure, or even another list (perhaps, you have a "meta-directory", where each person has their own personal directory ... or even their own list of directories!). (Slow down, breathe, and re-read that; it takes a moment to think it through.)
To ponder (no response required): Why did we ask to return the entire key/datum entry -- wouldn't it be more convenient to just return the associated datum? (What would be problematic about this?)

(45 pts total)

 

 

Last Revised Sunday, 21-Nov-2004 14:11:01 CST

©2004 Stephen Wong and Dung Nguyen