CSci 1301: Problem Set 6

Due: Friday, November 15 at 11:59pm by e-mail

You are required to write signatures and descriptions for all functions, and also descriptions of all your structures. Additionally, functions, except the world problems, must be tested using check-expect. Write your tests before you write a function (but feel free to add more after it's been writen).

The quality of your tests will be graded. Make sure to have enough test cases to demonstrate that the function is correct. I may take points off for a lack of testing (in addition to those taken off for incorrect behavior) if your function doesn't work on particular expected data and there is no test for it. It's much better to leave a test that fails (perhaps in comments) that shows that the function doesn't work on given data and you don't know how to fix it.

Problem 1: Written exercises

Written exercises can be submitted electronically or on paper, in one of the following ways:

All exercises for this part are given in the section Intermezzo: BSL

  1. Exercises 106 (question 3 only), 107 (questions 1,2 only), 108 (question 3 only), 109 (question 3 only), 110 (all quiestions, justify your answers) (8 points)
  2. Exercise 112 (questions 2,3 only) (4 points)
  3. Exercise 115, 117 (note: evaluation of some expressions may lead to an error) (8 points)

Problem 2: Finish the balloon problem (10 points)

Your task is to finish the balloon exercise that we did in class. Specifically:

  1. Finish the problem by adding a random balloon at the bottom of the canvas, at a random x coordinate, of a random size (i.e. the scaling factor) between 0.5 and 1.5, and of a color randomly chosen among several colors of your choice (with equal probability). A new balloon apears on every clock tick. Implement your solution and test it.
  2. Change your solution by adding an additional feature (you may change your solution to the previous question; comment out the old code, but don't delete it. You can add features such as: adding a new balloon less than on every clock tick (you can make it deterministic, such as adding one on every 2nd clock tick, or probabilistic, such as adding a balloon with a probability 1/2). You can add "wind" that makes balloons shift horizontally, in addition to vertically. You can have a balloon pop at random, or when it hits a tree branch.
    Especially interesting solutions may get an extra credit.
    Clearly document the features that you are adding. Make sure that your functions have good names and signatures and descriptions.

Problem 3: Extended exercise (15 points)

Exercises 178, 179, 180 in section 13.1

Problem 4: Create your own problem (6 points)

Come up with your own problem that is solvable using recursion and then solve it. Start with a description of what you are trying to do (it's ok if it is informal at first), write it down in comments. Make sure to write check-expect (and check-error, if needed) tests, then the function signature and description, and then the implementation. If any of your initial ideas changed during this process, write down what changed and why.

The problem may or may not deal with lists. It's ok to use recursion in helper functions.

Implementations of Towers of Hanoi will not be considered (it's a classical recursion problem, and many implementations are avaiable in just about any language).

The most interesting problems may get extra credit. Clearly indicate which features of your solution you consider interesting (for instance, it may be a very useful function, or it may be different from uses of recursion that we've covered in class).

CSci 1301 course web site.