Homework #3
(10 points)

Fibonacci and Etch-a-Sketch

Due Date

Monday, March 9 (both sections).

Reading: Chapter 5.

Your Mission: Two programming projects. Be sure to hand in a hardcopy printout of the two programs to your TA. This way, your TA can try your code, and also has a copy to write comments on.
  1. The Fibonacci Sequence (2 points)

    One day in the 13th century, Leonardo Fibonacci decided to challenge the brains of 1007 students. "I will destroy my arch-nemesis Painless Computing Penelope once and for all!" he cackled. This is a true story, and he's famous for this. He continued, "This recursive programming problem will make your mind melt and your fingers tremble!"

    In the Fibonacci sequence of integers, the first two terms are 0 and 1 (the base case), and every additional term is the sum of the previous two terms (the recursive case). Therefore, it looks like this:

    0, 1, 1, 2, 3, 5, 8...

    You are to write a recursive functions, fib, that takes one integer parameter, n, and returns the n-th Fibonacci number. For example, fib(0) should return 0, and fib(4) should return 3.

    That's not too bad, says Penelope. She says the function to do this is really quite short, and not too terrible to write. Just remember that in the general case, the n-th Fibonacci number can be found by simply adding together the (n-1)-th and the (n-2)-th Fibonacci numbers, which are each found with a recursive call. Therefore, your function should have two recursive calls in it. It must not use the "for" or "while" statements -- no explicit loops.

    "Ha ha ha ha ha ha!" retorts Leonardo. Prove him wrong by writing a loop that repeatedly calls your function in order to output the first 12 terms of the Fibonacci sequence.

  2. High Tech Etch-a-Sketch(TM) (8 points)

    We would like you to design a high-tech Etch-a-Sketch! Instead of drawing pictures using a couple of silly knobs, we would like to draw pictures using commands that you type in. Each command starts with an action verb. For example, we would like to say things like: Thus, we would like the following verbs to function:
    1. Draw a "unit-sized" (defined below) figure.
      • We should be able to specify a color including red, blue, green, and black. If no color is specified, you should draw the shape the same color as the previous shape. Initially, the color should be black.
      • We should have the option of drawing a square, circle, line, or one other shape of your choice. The shapes should be centered on the current pen location.
      • In the case of lines, we should be able to specify a direction including up, down, left, and right. Note that drawing a line has the effect of moving the pen, but drawing other shapes does not.
    2. Make the "unit" (defined below) smaller or large by a factor of two. This command should not draw anything, but its effect will be noticed the next time something is drawn!
    3. Move the pen (without drawing anything)...
      • ...in a given direction: left, right, up or down by a "unit" (defined below).
      • ...to a specific location indicated by two single digit integers in the format listed above. The first integer indicates the x-coordinate of the point and the second integer indicates the y-coordinate. Please check to make sure that the pen remains within the window -- if not, do not move it.
    4. Quit the program: The user has finished drawing the picture and would like to leave the program.

    User errors: If the user types a command that does not start with one of these verbs or does not provide the right sequence of words after the verb, an error message should be printed informing the user this was an illegal entry.

    Unit of distance: Initially, for your program the unit should be one inch. Thus, if you give the command "Draw a red square" to the program, a one-inch red square will appear on the graphics window at the location of the pen. You can then modify the size of what you draw (and how far you move the pen) using the "Make" command. "Make smaller" should halve the size of the unit while "Make larger" should double it. Doing the latter immediately after the former would leave the size unchanged.

    Design with decomposition in mind. In order to make your programming task easier, you must write functions with the following prototypes, as well as a few other functions:

    IthWord returns word i from a given string. Note that this function will probably also be useful for a future homework assignment. Also note: although you may be aware that strings are actually represented as arrays, at this stage we would like to work with them more abstractly. Therefore, use the functions, IthChar (p. 321) and SubString (p. 323).

    DrawCircle may not use DrawArc!

    If you write these functions first and then test them out to make sure that each works correctly, you will have a much easier time assembling your program.

    Make a separate function to handle each verb. For example, there must be a Draw function, separate from DrawSquare, DrawCircle, etc.

    Note: There are several other functions that we are expecting, but we will let you figure those out on your own!

    To make it easier for you, you can make the following assumptions:

    A couple of caveats and some advice:

    As always, any embellishments or extensions will be greeted by with great joy by the TAs, as well as potential extra credit. For example, you might want to generate error messages in case the user wants to draw something outside the graphics window.


The deliverables for this assignment are the two programs electronically submitted and the two printouts containing the source code for your two programs delivered to your TA.


email: evs at cs dot columbia dot edu (Thanks to Andrew Kosoresow for creating the Etch-a-Sketch problem.)