Date: Wed, 08 Jan 1997 20:46:43 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 322 Assignment 1 Solution Set Friday, January 12, 1996



next up previous
Next: About this document

CSE 322 Assignment 1 Solution Set Friday, January 12, 1996

  1. Prove that for all n > 0. (#27 p. 27)

    We can prove this by induction on n:

    Basis: The statement is true for n = 1 because .

    Inductive hypothesis: Assume that the statement is true for n=k:

    Inductive step: From this we need to show it is true for n=k+1:

    By induction, the statement is true for all .

  2. Using the tree on p. 27:(#27 p. 27)
    1. The depth of the tree is 4. (The depth of the root is 0.)
    2. The ancestors of are ,,, and . (Every node is an ancestor of itself.)
    3. The minimal common ancestor of and is and of and is .
    4. The subtree generated by is the following:

    5. The frontier of the tree is .
    1. The rank of in the enumeration ordering of is

      This is because if we look at the strings of length 2n, the first strings in the enumeration are those that begin with . Of the strings that begin with , is the first and is the last of these. This gives us the following:

      The rank of is . The number of strings of length 2n that begin with is just the number of ways of writing the last n letters as a string in the alphabet. There are such ending strings. Combining these observations gives us:

    2. The rank of in the enumeration ordering of is

      In the enumeration ordering, the strings that come before are exactly the strings over whose length is less than n. Therefore,

      For any i, the number of strings of length i is . Thus the number of strings of length less than n is the sum of all these, so:





next up previous
Next: About this document



James Fix
Mon Jan 29 18:05:51 PST 1996