Comp 200 hw04

Due in class 01.Mar.14 (Mon)

(-1pts for not stapling!)
  1. (5 pts) This problem involves using the family-tree teachpack to write some functions.
      Suppose we know how to write the following function: 
    1. ;; (known-generations a-tree): 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 'unknown)    =   ; What should this be?
      Your task is to write the new function, 
      ;; (know-generations? a-tree gens): FamTree, number --> boolean
;; Do we know the entire family tree for "gens" generations back?
;;
      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.

    2. 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 lecture.
  2. (2 pts) What numbers do the following binary numerals represent? Express your answer in decimal numerals (or, if you prefer, in Roman numerals). 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).
    lecture notes

  3. (3 pts)
    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. [Nothing to do on this point -- just think about it:]
      Observe that 24 numbers have 4 or fewer bits ("binary digits"); it makes sense to guess that 220 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 2n.)
    4. What proportion of these numerals have a 1 in the one's place?
    5. Of the 24 = sixteen numerals (zero through fifteen), what proportion have a 1 in the four's place (that is, the 3rd column on the right)?
    6. Of all the 20-bit numerals 0...220-1, how many have a 1 in the 128's place (the 7th column on the right, since 27=128).
    To think about, for fun, when spring break gets boring: What is one-half, as a binary numeral? one-eighth? one-third??
  4. (6 pts) Suppose you have a personal computer which runs at 100MHz -- that is, it computes 100 million instructions per second¹. If you have an algorithm which solves a problem of size n in f (n) instructions, how long does it take to compute problems for various functions f and various input-sizes n?
    f
    log10(n) n n log10(n) n² n³ 2n n!
    n 10²              
    10³              
    106              
    109              
    Give your answer with only two significant figures (that is, the first non-zero digit and the next one.) Answer in time units that are meaningful to you -- e.g. "2.0 days" is better than "170,000 seconds". For fractions of a second ("s") or many many years ("yr"), it is standard to use metric prefixes (here are annotated, distilled, and silly references).

    Alternately, you may do problem 7.4 in the text, if you include rows for N and N².

    You may also use drScheme and some helper functions for unit conversions, if you like. For the last few columns, some values may exceed your calculator; you can ignore any numbers larger than 10100 (``one googol''). Note that in scheme, (expt 2 10) = 1024 (2 to the 10th power). log is built-in, but it is the natural log (base e); we can define log-base-10 though: 

    (define (log10 x)
  (/ (log x) (log 10)))

(log10 100) = 2
(log10 100000) = 5

    Compute the 2100 entry by hand². How many times larger is the 21000 entry? (Is 2100 more than one trillionth of one percent of 21000?)

    For related fun, try this tour of 10+23m down to 10-15m.

  5. (4 pts) Harel, problem 6.4 (Binary search, worst cases). Observe that part (a) has several possible answer; part (b) is asking you how many answers part (a) had! Note: where he asks "describe an input list which ...", it should read "describe a name-to-search-for which ...".
    You can imagine always using the Houston white pages (which indeed has ~ 1million entries).

    Hint for (b): Instead of a phonebook with million (~ 220) names, first think about 15 = 24-1; Of the 15 possible names-to-search-for, how many of them are worst-cases? (If it helps, for each of the 15 names, see how many comparisons each one requires; then you can see how many are worst cases, and if there is a pattern to their arrangments.) (Perhaps think in terms of decision trees, or in terms of playing hi-lo from 1..15 and the binary representations [0001]2...[1111]2. Each guess involves learning whether the next digit is 0 or 1, and a solution is found when all the remaining digits are all 0.)

  6. (extra credit: 4 pts) Harel, problem 6.3 (analyze Pwr).
    You only need to look at only one of Pwr1,Pwr2, and only one of Pwr3,Pwr4. (The members of each pair are similar -- the first is iterative and the second is recursive.) Before computing the answer, run an example by hand -- say 35. (For Pwr3,Pwr4 keep in mind how 5 is written in binary numerals; this provides an insight as to how the function works.)

¹ This is an oversimplification; there turn out to be quite a few subtleties in correlating a computer's clock speed (e.g. 400MHz) with how many instructions per second it computes. Moreover, different families of computers (e.g. Pentiums, PowerMacs, Sparcstations, ...) have different instructions, making exact comparisons between these families more difficult. However, the idea of one clock cycle being one instruction is a handy first approximation. (back)

² Your answer can include powers of 2 or 10, but should be in centuries (or larger), since it's not intuitive to me how (say) 2^90 seconds relates to centuries.

Note that for any number m, 2m ~ 10(m/3.322). Why, you ask? Remember that it takes m digits to write 2m in base 2. How many binary digits are needed for every decimal digit? That is the same as asking how many factors of two are needed to make a single factor of 10. By definition of log, the answer is log2(10) ~ 3.322 -- that is, in binary, 10 requires a smidgen more than 3 binary digits after the leading 1.

If you like, to get a rough approximation of the factorial function, you can use Stirling's formula: n! = (n/e)n sqrt(2 pi n) (1 + 1/(12n) + 1/(288n²) + O(1/n³)).
[Note the use of big-Oh to let us use an equal-sign, instead of approximately-equal. You can ignore all the small terms (1/12n + 1/288n² + O(1/n³)).] (back)