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:

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.


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