 Due date: 9/24 @ at the beginning of class
The goal of this problem set is to practice structural programming
using structures, lists, Sexpressions, recursive data definitions.
Some problems demand accumulatorstyle programming. One of the problems
is about proofbyinduction, but as you know by now, this is closely
related to structural programming.
The problems cover material from HtDP, specifically parts I, II, III, and
VI. To be reasonable effective in Racket, you also want to read part IV.
HtDP is migrating to a second edition; the
draft is online.
Use the Racket programming language and the DrRacket programming
environment to solve the problems (#lang racket). The appendix of part II
in your Redex textbook is a nutshell introduction to DrRacket.
If you encounter errors you don't understand, you may wish to switch to
the HtDP Intermediate Student programming language. See the DrRacket
Language menu.
WARNING: This problem set is laborintensive for those of you who
have little or no practice with structural programming. Start early.
Do not for one moment believe, however, that this problem set is
difficult because it requires you to solve the problems in a new
language. If you have this impression, solve the problem in your favorite
language and show me your solution.
Problem 1:
Develop a data representation for a mobile. Wikipedia describes
a moible as follows:
A mobile is a type of kinetic sculpture constructed to take advantage of
the principle of equilibrium. It consists of a number of rods, from which
weighted objects or further rods hang. The objects hanging from the rods
balance each other, so that the rods remain more or less horizontal. Each
rod hangs from only one string, which gives it freedom to rotate about the
string.
We use this rigorous, structured description. A Mobile
 a weight
 a combination of two Mobiles and a weight.
The weight in the first case represents an "atomic" sculpture. You may
represent a weight as a plain number, say the number of "kg" that the
sculpture weighs. The weight in the second case is a pointwise
approximation of the beam that connects the two Mobiles.
Design the following functions:

weights#, which consumes a mobile and counts the number of
weights it contains;

totalweight, which consumes a mobile and determines its total
weight;

averageweight, which consumes a mobile and determines the
average weight of all the atomic sculptures it contains;

depth, which consumes a mobile and determines the maximal number
of links from the top of the mobile to one of its atomic sculptures;

balanced?, which consumes a mobile and determines whether or not
it is balanced. A mobile is balanced if the weight of the mobile on one
end is equal to the weight of the mobile on the other end. The weight of a
mobile naturally includes the beams.
Problem 2:
Recall the data definition for Sexpressions over symbols. An
Sexpression is one of:
 the empty list or '() for short;
 (cons Symbol Sexpression)
 (cons Sexpression Sexpression)
For this problem, we ignore what this data represents. In general, though,
Sexpressions are useful to represent the abstract syntax of any form of
program (Java, Scheme, XML, etc).
Design the following functions:
 count, which counts the number of symbols in an Sexpression;
 flatten, which produces the list of all symbols in an
Sexpression (duplicates allowed)
 substitute, which replaces some old symbol with a
new symbol in the given Sexpression.
Problem 3:
Design the function silly. The function consumes a Mobile (see
Problem 1). It produces a Mobile, by adding to each sculpture S
(remember that it is represented by its weight) the depth of S in
the Mobile.
Problem 4:
Design the function free. It consumes an Sexpression of the
following shape.
An XY is one of:
 a Symbol
 (list 'function Symbol XY)
 (list XY XY)
It produces an Sexpression of this shape:
An AB is one of:
 a Number
 a Symbol
 (list 'function Symbol AB)
 (list AB AB)
For each symbol introduced by the first clause in an XY
Sexpression, free replaces it with the number of
'function symbols between it and the closest
'function node that lists the same symbol. If there is no such
node, the symbol is transferred to the output.
For example, when given
'(function y
((function x
(x y))
(x y)))
free produces
'(function y
((function x
(0 1))
(x 0)))
Problem 5:
Here is a rigorous definition of the set of shapes from the
first quiz. A Shape is one of:

a rectangle whose sides are parallel to the two axes, specified as the
collection of four numbers: xmin, xmax, ymin, and
ymax subject to the constraint that xmin < xmax
and ymin < ymax.

a combination of two shapes.
Nothing else is a shape.
Prove that

all elements of Shape contain an even number of numbers;

the number of rectangles in a Shape is always larger than the
number of combinations;

the area covered by all rectangles in a Shape is smaller than
the "general" area of a shape. The "general" area of a shape S is
(max { xmax  xmax in all rectangles in S}  min { xmin  xmin in all rectangles in S})
*
(max { ymax  ymax in all rectangles in S}  min { ymin  ymin in all rectangles in S})

