Teaching 211 F '06 Assignments The Hand In The Recipes The World Set 1 Set 2 Set 3 Set 4 Set 5 Set 6 Set 7 Set 8 Set 9 Set 10 Set 11 Set 12 Set 13 Set 14

### Problem Set 9

Due date: 11/06 @ 6pm

Programming Language: Intermediate Student Language

Problem 0 [5%]:

Find one interesting article from the weeks news on the use of software/computers in society. Summarize the article in your own words with a single 200-word paragraph, as a pair, one playing writer, the other playing editor. Add both the article and the summary in with the rest of your problem set.

The goal of this problem set is to practice the creation and the use of abstractions.

HtDP Problems:

19.1.5, 20.2.4 (also see 20.2.2)

Problem A1:

Here is a data definition for the most important set of numbers:

``````
;; A N (Natural number) is one of:
;; -- 0
```
```
Use `zero?` as the predicate for recognizing 0 and `positive?` for the second branch; `sub1` is the selector.

Design the function `count`, which consumes a Natural number `n` and creates `(list n-1 ... 0).`

Design the function `tens`, which consumes a natural number `N` and creates `(list (* 10 n-1) ... 0).`

Abstract over the two functions according to the recipe.

Use the abstraction to define the function `squares`, which consumes a natural number and produces the list of squares down to 0.

Suggestion: if you still believe that the design recipe doesn't empower you to solve problems whose data definitions you have never seen before, natural numbers are covered in the book, but the relevant sections have not been assigned.

Problem A2:

Develop data definitions for binary trees of symbols and binary trees of numbers. Numbers and symbols should occur at the leaf positions only. Create two instances of each. Abstract over the data definitions.

Design the function `height`, which consumes any binary tree and computes its height, that is, how far it is from the root (the given tree) to farthest leaf.

A leafy binary tree is a binary tree with `'leaf` at its leafs.

Design a function that consumes a natural number `n` and creates all leafy binary trees of height `n`.

Hint:
Design a function that consumes a natural number `n` and creates all leafy binary trees of height equal or less than `n`? -- Warning: this is not about abstraction; it's just a reminder that regular (and complex) programs are around the corner.

 last updated on Thu Nov 30 11:55:15 EST 2006 generated with PLT Scheme