Comp 200 Homework 3:
Drawing, Trees, and Binary Numerals

Due in class on Wed 20 Feb 2002

1. Generalize pentagon done in class, to polygon.

   ;; (polygon: n size env): number number snapshot --> snapshot
   ;; Draw a regular n-sided polygon (each side length n) on the snapshot "env",
   ;; and return the new snapshot.
   ;;
   (define (polygon n size before)
      ...)
   

   Be sure to first write smaller (helper) functions, as suggested in the notes, for drawing an individual side. Don't forget your high school geometry!!! How many degrees are there in every angle of an equilateral triangle? a square? a regular pentagon? a regular hexagon? a regular dodecagon? Derive a formula for this based on having the number of sides as input. As we CS people would say, "abstract" over the number of sides.
2. Review the koch curve function from class Now, try making up a different fractal curve. Decide what your "attempt 1" curve might look like on paper. Modify your code to do this, and see what attempts 2,3,... look like. You might want to modify your "attempt 1" curve so that it looks cooler when higher-level attempts are made. Write a function that produces this curve. You might get some ideas from this fractal site.
3. For these functions, you'll need to copy in the FamTree definitions. Here are some sample FamTrees to test your functions on. You can use the Simpsons tree from class as well.
   1. Remembering the definition of a FamTree from class, write a function

      ;; contains-name?: symbol FamTree --> boolean
      ;; Does the name "name" occur in FamTree ft?
      ;; if yes, return true; if no, return false
      (define (contains-name? name ft)
         (if (unknown? ft)
             ...
             ..(child-name ft)..(child-ma ft)..(child-pa ft)..)))
      

   2. Optional, EXTRA CREDIT problem:
      Now, write a function

      ;; some-name-twice?: FamTree --> boolean
      ;; Does ft contain a duplicated name, ANYWHERE in the tree?
      ;; if yes, return true; if no, return false
      (define (some-name-twice? ft)
         (if (unknown? ft)
             ...
             ..(child-name ft)..(child-ma ft)..(child-pa ft)..)))
      

4. More FamTrees . . .
   Suppose we know how to write the following function:

   ;; known-generations: FamTree --> number
   ;; How many generations of ancestors are entirely known?
   ;; That is, for how many generations is the family tree
   ;; totally devoid of unknowns?
   
   ; Examples, using the place-holders barts-tree, etc, as given in class:
   ;
   (known-generations marges-tree) = 1 ; Marge is known, but her father isn't.
   (known-generations  barts-tree) = 2 ; Self and all parents known, but not all grandparents.
   (known-generations (make-unknown))    =   ; What should this be?
   

   Your task is to write the new function,

   ;; know-generations?: FamTree number --> boolean
   ;; Do we know the entire family tree for "gens" generations back?
   ;;
   (define (know-generations? ft gens)
      . . . )
   

   Use known-generations as a helper function -- your code should be a one-liner! Be sure to include test cases.

   We say that we have reduced the problem know-generations? to the problem known-generations, meaning that writing the former is easier (at least, we've proven that it can't be particularly harder) than writing the latter.

   You knew this problem couldn't be too easy: Now, go ahead and write known-generations yourself. Note that it's a counterpart to height: FamTree --> number , which we discussed in class.

5. Write the function timesHalved, which takes a number n and returns how many times n could be halved before it gets smaller than or equal to one. (Think, how many times you could bet half your wealth and (sadly) lose, until you had no more than a dollar?) Test your function on several test cases, including 1,048,576. (By the way, this will give the same answer as nod (Number of Doublings) discussed in class, except that we approach the problem by dividing towards 1, rather than multiplying towards n.)
6. What numbers do the following binary numerals represent? Express your answer in decimal numerals (or, if you prefer, in Roman numerals).
   • 11
   • 110
   • 1100
   • 11001
   • 11001100
   Note in retrospect, what happens when you append a 0 to a numeral (and that appending a 1 is the same as appending a 0, and then adding 1). If you need help, check out the lecture notes.

7. More Binary Numerals . . .
   1. Express the numbers zero through fifteen in binary numerals. Include leading 0s, so they are all four digits long (you'll see more patterns jumping out this way).
   2. While we're at it, express sixteen, seventeen, eighteen in binary, as well. (Just to confirm the patterns you've been guessing at.)
   3. Observe that 2⁴ numbers have 4 or fewer bits ("binary digits"); it makes sense to guess that 2²⁰ would have 20 or fewer bits.
      You can see a pattern: There are twice as many 4-bit numerals as there are 3-bit numerals: First take all the 3-bit numerals preceded by a leading 0, and then take them again preceded by a 1.
      Every time you allow another digit, you double the number of possible numerals. (This is another way of saying that number-of-binary-digits(n) is the counterpart (inverse) to 2ⁿ.)
   1. What proportion of these numerals have a 1 in the one's place?
   2. Of the 2⁴ = sixteen numerals (zero through fifteen), what proportion have a 1 in the four's place (that is, the 3rd column on the right)?
   3. Of all the 20-bit numerals 0...2²⁰-1, how many have a 1 in the 128's place (the 7th column on the right, since 2⁷=128).
   4. To think about, for fun, that is to say, you don't have to turn anything in for this one! What is one-half, as a binary numeral? one-eighth? one-third??