Assignment 2: Simple Recursions

Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks, and Grading Guidelines. Above all, keep your work neat and honest.

1. (2pts) A Speaking Cash Register:

   The cash registers at the Rice Epicurean Market talk to you. A register's controller receives a number greater than 0 and then builds a list with the following five elements:

   1. the dollar amount;
   2. the symbol 'dollar if the dollar amount is 1 and 'dollars otherwise;
   3. the symbol 'and
   4. the cent amount; and
   5. the symbol 'cent if the cent amount is 1 and 'cents otherwise.
   For example, if the amount is $1.03, then the controller receives 103 and the result is

   (cons 1 (cons 'dollar (cons 'and (cons 3 (cons 'cents empty)))))
   

   You are to define the controller as a Scheme program. You may use our solution to Problem 2 of the first homework set.

   Hints: Recall that Scheme provides the functions quotient and remainder.
   
   

2. (2pts) Exercise 11.0.5. Include a program template.
   
   
3. (3pts) A (binary) table is a sequence of pairs. Each pair combines a name with some value. The name is often called a key, the value a datum.

   Develop the program lookup. The program takes an symbol, which is called the search-key, and a table. It returns the first pair whose key is equal to the search-key. If it can't find such an pair, it returns false.

   Note: Schemers often call such a table an A-list, short for association list.
   
   

4. (3pts) Derive the template for programs that input MnMs. Here is the data description for an MnM:

   A MnM is either empty, or (cons #f (cons n mnm)) where n is a number and mnm is an MnM, or (cons #t (cons m mnm)) where m is a number and mnm is an MnM.

   
   
   

5. (Extra Credit: 2pts) Exercise 12.1.6.