# CSG 107: Problem Set 6

Due: Wednesday, March 11, 2009 at 5:00 pm.

#### Purpose:

The goal of this problem set is to help you recognize when generative recursion and accumulators may be helpful and to use them when they are. Note: not all problems in this set use generative recursion or accumulators!

As always, you must follow the design recipe. You must annotate each function with the design strategy that you used:

• domain knowledge (algebra, physics, watching traffic lights)
• function composition: a function that contains a conditional is not designed via function composition; expressions such as (f w (g x y) z) is about all you may use then;
• structural design, on the 6th argument
• structural design, on the 4th and 6th argument (if you choose this option, also document which of the three situations you are working with)
• generative design
• abstraction over structural recursion
• abstraction over generative design
If you use a design "with accumulators", be sure to explain the connection between the local recursion argument, the accumulator, and the initial argument; otherwise you can't get credit. You may also use a design "with existing abstractions" if you use one of the functions from page 313.

#### Finger Exercises from Lecture 6:

These are like the drill problems: you should do them, but they will not be graded. I may do this after future lectures as well.
1. In bailouts.ss, rewrite bailout-abstract2 using fold instead of map.
2. Design a function total-cost-abstract. Do this twice, once using explicit recursion (like bailout-abstract) and once using fold.
3. Design the function select-lt that we used in quicksort. Again, do this twice: once using the structure strategy and once using fold.
4. How does the function findroot in findroot.ss differ from the one in figure 78? Observe that the algorithm is subtly different. Why does this version still work?

#### Drill:

HtDP: 26.2.1, 26.3 (all), 27.2.3-5, 28.2 (all)

#### Required Problems:

Note: You must use DrScheme's HtDP Intermediate Student Language with Lambda.

1. Design a function find-root2 similar to find-root from class, except that it has a slightly different contract:
```;; find-root2 : (Number -> Number) Number Number[>0] -> Number
;; (find-root f lo delta)
;; assumes: f monotone, f(lo) <= 0 <= f(lo+delta)
;; returns: z such that there is a root of f in [z, z+TOLERANCE)
```
2. Continue the DiffExp problem from last week by writing a function
```value-of : DiffExp -> Number
```
that finds the value of a DiffExp. For example:
```(value-of (make-diffexp
(make-diffexp 2 4)
(make-diffexp 3 5)))

= (- (value-of (make-diffexp 2 4))
(value-of (make-diffexp 3 5)))

= (- (- (value-of 2) (value-of 4))
(- (value-of 3) (value-of 5)))

= (- (- 2 4)
(- 3 5))

= (- -2
-2)

= 0
```
To make it easier to write your test cases, you may use your function decode from last week. However in ISL, there is no way to give a list structure directly to Scheme and get its value.
3. Extend your solution to the pitcher-pouring problem from last week as follows:

Design a function

```solution : State (State -> Boolean) -> Listof(Move) | false
(solution state winning-state?) returns a list of moves that
transforms the given state into a winning state, or false if there is none.
```
Remember that Move is the data representation of moves, which you designed last week.

Hint: the states of the pitchers correspond to the nodes of a graph, and the moves correspond to the edges. This graph is probably too big to construct, but you can still easily write something corresponding to the neighbors function.

For examples of this problem where there is a solution, verify that the sequence your program finds really is a solution by testing it using your function simulate from last week.