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

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

- In bailouts.ss, rewrite bailout-abstract2 using
`fold`instead of`map`. - Design a function
`total-cost-abstract`. Do this twice, once using explicit recursion (like`bailout-abstract`) and once using`fold`. - Design the function
`select-lt`that we used in`quicksort`. Again, do this twice: once using the structure strategy and once using`fold`. - 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?

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

- 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)

- 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. -
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.

Last modified: Tue Feb 24 12:24:10 2009