15110 Fall 2012 [Touretzky/Kaynar]

Programming Assignment 10 - due Tuesday, November 6

Note: You are responsible for protecting your solutions to these problems from being seen by other students either physically (e.g., by looking over your shoulder) or electronically. (More information can be found in the instructions for Programming Assignment 2.)

Setup: We will be using the same image representation (an array of arrays of pixels) as in Lab 8. Load the file pa10.rb, which contains helper functions you will need for this assignment. The function empty_image(size) returns a square array of white pixels. The function make_square!(image,size) draws a square of the specified size in the image array, and also plots the array. Since this is a destructive function, calling it twice on the same image array (with different size values) will plot one square on top of another. The example below produces the 12×12 image shown at right:



im = empty_image(12)
make_square!(im,10)
make_square!(im,6)






1. (3 pts Write a recursive function nested_squares1!(image,size) that draws a square of the specified size in the array image, and then calls itself recursively to draw a square 2 units smaller. Remember that you will need to check for the base case of the recursion. You can test your function by writing nested_squares1!(empty_image(12),12). The result should look like the image at right, although the colors will be different.
   

   

2. (2 pts) In the previous exercise, each recursive call draws the smaller square after the larger square. so the smaller squares appear "on top of" the larger ones. Write a function nested_squares2!(image,size) that draws the smaller square before the larger square, so the larger squares come out on top. The result should look like the example at right.
   

3. (3 pts) Consider the list x = [412, [268, 2000]], which we can draw as the binary tree below. The root node is the list x itself; the left child is x[0], which is 412, and the right child is x[1], which is the list [268, 2000]. That list is itself a binary tree with children 268 and 2000. Binary trees are recursive data structures.
   
   

   Suppose we want to write a function that takes a binary tree like this as input and plots it using the image data structure we've been experimenting with in this assignment. We can use a simple mathematical relationship to lay out the tree, as shown below:

   
   

   Each node of the tree will be drawn in a box defined by start and finish values. Since our image is 7 pixels wide, initially start=0 and finish=6. When we draw a node in a box, we always draw it at the midpoint, mid = (start+finish)/2.

   
   

   The root of the tree is at depth 0, and it is drawn at position mid = (0+6)/2 = 3. Tbis root is a nonterminal node, so it has two children, and each gets its own box on the level below. The left child's box runs from start to mid-1, and the right child's box runs from mid+1 to finish. So we see that at depth 1 we have a box occupying spaces 0-2 and a second box occupying spaces 4-6. We can recursively decompose these boxes too. For the left box at depth 1, mid=1 and the two boxes at depth 2 are at positions 0 and 2. For the right box at depth 1, mid=5 and the child boxes at depth 2 are at 4 and 6.

   Now that we know how our tree should be layed out, we can write a recursive function to draw the tree. The tree [412, [268, 2000]] should appear as the image at right. The code below will do the drawing, once you've completed the missing pieces marked by "...". Rather than typing it in by hand, you can copy it from the file draw_tree.rb. Notice that draw_tree_helper contains a puts statement to help you debug your recursive calls.

   
   def draw_tree(tree)
     width = 7           # works for trees up to depth 2
     image = empty_image(width)
     depth = 0
     start = 0
     finish = width-1
     draw_tree_helper(tree,image,depth,start,finish)
     plot(image,20)
   end
   
   def draw_tree_helper(tree,image,depth,start,finish)
     puts "tree=#{tree.inspect} depth=#{depth} start=#{start} finish=#{finish}"
     mid = (start + finish) / 2
     # draw the current node
     image[depth][mid] = [255,0,0]
     if tree.kind_of?(Array) then
       # recursively draw the children:  FILL IN THE "..." PART
       draw_tree_helper(tree[0], ...)
       draw_tree_helper(tree[1], ...)
     end
   end
   

   Test your draw_tree function on the following examples:

   draw_tree("eureka")
   draw_tree(["do", ["re","mi"]])
   draw_tree([["do","re"], "mi"])
   draw_tree([["fee","fie"], ["foe","fum"]])
   

4. (2 pts) Our initial version of draw_tree worked only up to depth 2, because the image size was fixed at 7 pixels. Let's eliminate this restriction by using the tree_depth function you wrote in Exam 2 to calculate the width of the image. If a tree is of depth N, the image should be \(2^{N+1}-1\) pixels wide. You can include the definition of tree_depth in your draw_tree.rb file. Modify your draw_tree function as described above, and test it on binary trees of greater depths, such as [1, [[2,3],4]].

Submission

You should have a pa10 directory, containing:

1. nested_squares1.rb
2. nested_squares2.rb
3. draw_tree.rb

Zip up your directory and upload it using the autolab system. (The autolab system will accept submissions beginning on Friday until the deadline Tuesday night.)