COMP 210, Spring 2001
Homework 8 : Generative Recursion
Due Oct.24 (wed), at start of class.

Your solution file: Make sure a copy of your solution is on your owlnet account in your sub-folder comp210/hw08.ss, so that if necessary the labby can open and run your program.

You are NOT required to show the template for your programs (woo-hoo!). However, your functions should still follow the template, as appropriate. And of course, each function should still have a contract and purpose, and reasonable test cases.

Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks (in particular: staple and provide questions), and the Grading Guidelines.

1. (7pts) Bottom-up Mergesort
   Ex. 26.1.2 mergesort, but done in a slightly different manner from lecture/lab (bottom-up, rather than top-down). Give an argument of termination for the function which calls merge-all-neighbors.
   You can of course use merge as in the lecture notes. (Note that map can help with at least one of your functions.) (Do, though, write this sorting algorithm as described; in particular, don't revert to the standard list template and come up with something equivalent to insertion sort -- we've already written that one!)

2. (6pts) Area under a Curve (adaptive trapezoids)
   Ex. 27.3.6, step 3 only. To help yourself understand the problem, draw pictures. Do not give an argument of termination (To ponder: can you think of a situation where this algorithm doesn't terminate? Can you fix the algorithm to it does always terminate, while still preserving the advantages of this approach?)

   Restating/clarifying the approach: To compute the area under a curve between [a,b], we find two estimates: (i) the trapezoid from a to b (rather: it's area), and (ii) a more refined estimate: (the trapezoid from a to mid) + (the trapezoid from mid to b). ^(*) If these two estimates are similar (where "similar" is specified in the problem), then assume the function is relatively linear and return (ii) as your estimate. Otherwise, recur on each half.

   Test cases The following are the sorts of test cases I'd expect you to come up with as usual, but for ease-of-grading I will specify a couple here. Use a TOLERANCE of 0.000001, for these tests.
   1. the constant function 7, from 4 to 9. (What is the exact answer?)
   2. square, from 4 to 9. (If you have had calculus: What is the exact answer?)
   3. Make up and test two more different functions, for which you can also compute the exact answer.
   4. Show that for some functions, your function is highly sensitive to the interval: changing them slightly might give a large difference your function's answer. (Does the actual area-under-curve change much?)
      (You can try a sawtooth curve like lambda x . x - floor(x), or you can be creative and think of your own functions which cause problems for this algorithm.)

   5. The book's step 2 mentions an alternate way of estimating the area under a curve: divide the interval [a,b] into many trapezoids of fixed width (a width of TOLERANCE, presumably), and just add those areas.

      Discuss (~1 concise paragraph): What are the strengths and weaknesses of the adaptive approach, compared to the fixed-interval approach? What are functions that do poorly and well in each case? Which do you recommend a friend use? (Optional: what other approaches might you make?)
      Of course: in both prose and code, grading is based on conciseness and clarity (which includes grammar and spelling), in addition to content/correctness.

   For fun: use this function and last week's derivative and measure whether the fundamental theorem of calculus really holds: integral( f', a, b) =? f(b) - f(a).

3. (7pts) Drawing curves
   Do one of the following two. In either case, give an argument of termination.

   1. Ex. 27.1.5, Bezier Curve.
      Instead of drawing the curve, have your function bezier return a list of posns (approximations to the bezier curve, including both endpoints. Don't include unnecessary duplicates!)

      Copy/paste draw-polyline and helpers, and write draw-bezier (using bezier as a helper, 'course). For your own debugging, you might want to have this function also draw the enclosing triangle.

      Test cases To help the labbies, also include the following test case which will have the same answer for everybody: call (bezier p1 p2 p3) (as defined in the book), and temporarily coarsen your idea of "close" so that you return a list of five posns (too-close about 62 or 63 worked for me). If your function won't return exactly five posns, try for four or six instead.

      Extra credit (2pts): The three initial points used above are called "control points"; the idea of Bezier's algorithm is to use the existing control points to make (more) new control points. Write bezier* which takes in not just three initial points, but a list of (any) control points.
      Hint: consider the list of five points you returned in the above example. This is also a (new) list of five control points. In the old version, how did those five points evolve towards a smooth curve? ⁽⁺⁾ Use good judgement when specifying contracts, etc.

   2. Ex. 27.1.4, Ferdinand The Fractal Fern. Note that the trig functions sin, etc., take their arguments in radians.

   For either of these two exercises, keep your threshold of "small" as a separate function/constant, so you can easily play with this threshold to see what effect it has on the drawing. When first writing and debugging your function, you'll find it helpful to have a large (coarse) threshold.