Comp 210 Exam #1 (alt) 1998 Fall

Name: This is a closed-book, closed-computer, three hour exam. This should be plenty enough time. Make sure to read each problem carefully. If you need to make any reasonable assumption to do a problem, just state that in the margin. Please refrain from discussing the exam until after the due-date.

Except as indicated, you may (only) use the following built-in Scheme functions: symbol? eq? boolean? not empty? cons? cons first rest list number? zero? positive? negative? add1 sub1 + - * / = < > ≤ ≥ and the special forms lambda define cond if define-struct and or.

Include contracts for all functions you write.

Time started:

Time finished: Pledge:

Problem 1 15
Problem 2 20
Problem 3 25
Problem 4 20
Problem 5 20
Total  100

1. (15 pts) In the kingdom of Tuhundredtenia, citizens whose income is less than $210 are taxed 2% of their income. Those is income is more than that are taxed 2% of that first $210, and 10% of the rest of their income. Consider the a function tax: number → number which given an income, computes the tax due. (A.) Show three example input/outputs for tax, and (B.) write the function. Naturally, changing any of the above the constants should require changing only one number in your solution.

2. (20 pts) Templates In class, we constructed family trees for ancestors. For this problem, we will construct family trees for descendants. A descendant tree consists of the name of an individual and trees for up to two children.

<dtree> := (nochild name) |
           (onechild name only) |
           (twochild name first second)

where name is a symbol and only, first, and second are dtrees.

(a) Give the define-structure statements that can be used to implement this data type in Scheme. List the constructors, predicates, and selectors created by these definestructures.

(b) Use your constructors to build an instance of a descendant tree that consists of a person named Joe who has a first born son Grant and second born daughter named Beth. (Neither Beth nor Grant have any children).

(c) Give the program template for a function tree-proc that takes as input a descendant

tree t.

(d) Based on the template, write the function any-only-children, which takes a descendent tree and returns whether or not anybody in the descendent tree is an only child.

3. (30pts)

(a) Write a data description for a <List-of-Doors> (where <Door>s will be defined below).

(b) Write a template for a <List-of-Doors>-handling function, assuming you will have a <Door>-handling function.

(c) There are three types of <Door>s, depending on what’s on the other side: Either a room (which has a name, but nothing else), or a hallway (which has a name and a <List-of-Doors>), or the outside (which has no further information). Write a reasonable data description for a <Door>, along with any accompanying

define-structs.

(d) Write a template for a <Door>-handling function; remember to write in any appropriate recursive calls.

(e) Write the function can-escape?, which takes a <Door> and indicates whether it is possible to reach the outside. (Include the contract for each function you write.)

4. (20 pts) Recall that a NatNum is either

• zero, or

• (add1 NatNum).

(a) Write the template for a function which handles two NatNums.^{1}

(b) An egalitarian computer virus, wanting to get rid of all inequality,^{2} has destroyed all computer implementations of the functions <, ≤, ≥, >, −, abs. In fact, the only surviving numerical functions are add1, sub1, zero?, positive?. Save the day by writing monus: NatNum,NatNum → NatNum, which returns its first argument minus its second argument (and returning 0 if its first argument is smaller than its second, since there aren’t any negative natural numbers).

1If your template is written such that the order in which you list the cases is essential to covering all cases, make a comment to this effect.

2Presumably somebody who felt that Tuhundredtenia’s tax code didn’t fairly account for cost-of-living.

5. (20pts) Write the function max, which takes a non-empty list of numbers, and returns the largest number in the list. Use an accumulator, and do not use local. Show the (recursive) calls to your function(s) that occur in the hand-evaluation of (max (list 7

5 9 2)).

Be sure to include a contract and description for all functions you write. (You don’t need to write any data description for this problem, though you are welcome to.)