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 
 ;; -- (add1 N)

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 2006generated with PLT Scheme