Shai Simonson         CSC 201

    Discrete Math for Computer Scientists

    Assignment 3

    Due:  Thursday, November 16
                          1.  Problems in the book: 
                            Note that there is more than one correct recurrence for Section 8.1 number 14,
                            and in general there may be more than one recurrence with the same closed form solution.
                                                    Section 8.1:   8, 14 (Use "at least one zero" in place of "two consecutive zeros"),  20.
                                                    Section 8.2:  4, 8, 28, 30
    2.  Consider the variation of the Towers of Hanoi Problem where you have four pegs instead of three.  For simplicity you may assume that n is a power of two. 
        Sloppy Joe designs this solution:
     
      void  Move n disks from From to To, using Using1 and Using2:
          if n equals 1, then print "move a disk from From to To," otherwise do the three recursive steps:
        Move n/2 disks from From to Using1, using To and Using2;
        Move n/2 disks from From to To, using Using1 and Using2; 
        Move n/2 disks from Using1 to To, using From and Using2;

      a. Explain why Sloppy Joe’s solution never moves any disk to Using2.
      b. Show explicitly by tracing the algorithm that Sloppy Joe's algorithm makes illegal moves.
          c. Fruity Freddie suggests fixing Sloppy's problem changing the second line:
        Move n/2 disks from From to To, using Using1  and Using2;    to
        Move n/2 disks from From to To, using Using2  and Using1;
      Explain why the algorithm still does not work in general.  //  Hint:  The second step is why Sloppy Joe is wrong. 

      d. Code the algorithms in C++ or Java (or any language you like) and report what happens for n = 4, and n = 8.
      e. Even though neither solution above works, set up a recurrence equation for the number of moves it takes to run the algorithms.
      f.  Solve this recurrence equation by repeated substitution.
     
    3.  Fix Joe and Freddie’s failures.  There is no way to solve the Towers of Hanoi on 4 pegs with divide and conquer, because the Using pegs are not in general free once you move the top half of a pile on them.  However, one can take advantage of 4 pegs using subtract and conquer.
      a. Construct a correct solution to the Towers of Hanoi problem with four pegs, that is faster than the standard solution with three pegs, using recurrence by subtraction.  Hint:  Recursively move n - 3 disks from Start to Using1 using Using2 and Finish, then using the normal 3 peg Towers of Hanoi method move 3 disks from Start to Finish using Using2.  Finally, recursively move n-3 disks from Using1 to Finish using Start and Using2. Explain how this solves the problem.
      b. Code your solution in any language and show the result for n = 4 and n = 8.
      c. Construct a recurrence equation for your solution and solve it.  You will need three different base cases for 0, 1, and 2 disks, respectively.  The closed form solution of your recurrence equation will depend on the value of n mod 3.  
Note: You can change the 3 in n-3 to another number and experiment to determine which gives you the best results.  You can even subtract a number that is a non-constant function of n.  Indeed, there is a conjecture that the best one can do for 4 pegs is to subtract x from n, where x is the largest integer such that the x-th triangle number is less than n.  For example, if n = 50, then x is 9, because 1 + 2 +...+ 9 = 45 < 50, but 1 + 2 + ... + 10 > 50.
     
    4.  For the 3-peg version, make a picture of the Towers of Hanoi graph for n = 4.  Recall that this graph is composed of three copies of the Hanoi graph for 3 disks.
     
    5.  In the original three peg Towers of Hanoi problem, add the constraint that no direct moves between the From peg to the To peg are allowed.
    This can be solved with the following algorithm:

    ConstrainedHanoi(n, From, To, Using)
    {
        if (n =1)  {move disk from From to Using;  move a disk from Using to To;}
            else  {
          ConstrainedHanoi(n-1, From, To, Using);
    move disk from From to Using;
    ConstrainedHanoi(n-1, To, From, Using);
    move disk from Using to To;
    ConstrainedHanoi(n-1, From, To, Using);   }
    }

      a.  Prove by induction, that following this new rule, will take you through every legal configuration of the game.  Hint: Use the graph representation.
      b.  Write a recurrence equation for the smallest number of moves it takes to solve the problem under the new constraint.
      c.  Solve the equation.
     
      For problems 6 and 7, recall that the n-bit Gray codes can be defined inductively from the n-1 bit Gray codes, by putting a zero in front of each n-1 bit code, followed by the n-1 bit codes in reverse order with a 1 in front of each.  Recall that each successive Gray code differs from the previous one by a single bit.

    6.  Make a table of the 2n elements of the Gray code for some n, by writing them in order starting from 0n, one underneath the other.  For example, when n = 3
          000
    001
    011
    010
    110
    111
    101
    100

          a.  Prove by induction that the first n-bit Gray code is n zeros and that the last n-bit Gray code is 1 followed by n-1 zeros. 

          b.  Using the second part of (a), prove by induction that any two consecutive Gray codes differ either by the last (rightmost) bit, or by the bit to the left of the rightmost 1. 
                That is, the recursively defined Gray codes correspond exactly to the codes of the Elephant Puzzle.

      c.  Look at the columns of your Gray codes and conjecture a theorem regarding the longest consecutive sequence of 1's in the ith column from the right, as i ranges from 1 to n-1. 

      d.  Using the second part of (a) again, prove your theorem in (c) by induction.
     
    7.  Converting Gray codes.  (Difficult - Optional Extra Credit)
        
      An algorithm that takes an n-bit binary number m = b1b2...bn and outputs the mth element of a binary Gray code, works like this:
      We construct the n-bit binary Gray code g1g2...gn from left to right.
      1.  g1 = b1
      2.  For i = 2 to n
              if bi-1 equals 0  then gi = bi
              else gi = the complement of bi.

      For example, 0000001 would be 0000001, 1111111 would be 1000000, and 1101011 would be 1011110.  

      a.  Prove by induction on n (the number of bits in m) that this method works.

           Proof Outline and Hints: 

      The base case is when n = 1.  Check that the algorithm does the right thing for 0 and for 1.

      For general n, there are two cases to consider:   when m starts with 0 and when it starts with 1. 

      Case 1:  When m starts with 0. 
              Let m = 0y consist of n bits, and let x be the code that the algorithm computes from y.  
              By induction, since y has n-1 bits, then x is the correct (y-th) Gray code for n -1 bits.
              Prove that the n-bit code computed by the algorithm on 0y equals 0x. 
              Prove that if the yth Gray code with n-1 bits is x, then the mth Gray code with n bits is 0x.

       Case 2:  When m starts with 1. 
              Let m = 1y  consist of n bits. Let 1x or 0x be the code computed by the algorithm on y.

              Case 2a:  1x
             
      By induction, since y has n-1 bits, then 1x is the correct (yth) Gray code for n-1 bits.
              Prove that the n-bit code computed by the algorithm on 1y equals 10x.
              Prove that if the mth Gray code with n -1 bits is 1x, then the m + 2n Gray code with n bits is 10x.

              Case 2b:  0x
              By induction, since y has n-1 bits, then 0x is the correct (yth) Gray code for n-1 bits.
              Prove that the n-bit code computed by the algorithm on 1y equals 11x.
              Prove that if the mth Gray code with n -1 bits is 0x, then the m + 2n Gray code with n bits is 11x.

      b.  Describe an algorithm that takes an element of a Gray code, and computes which one it is in the ordered list.
           (This is the inverse of the algorithm described above).

      8.  Consider the fast-exponentiation algorithm for computing an where a and n are integers. 
      If n = 1, then return a
      If n is even then compute an/2 recursively, and square it. 
                Otherwise, compute an-1 recursively and multiply the result by a.

      a.  How many multiplications does this method use when n is a power of two?  Write a recurrence equation and solve it.
      b.  How many multiplications when n is one less than a power of two?  Write a recurrence and solve it.
      c.  What exactly determines the number of multiplications for general n. Be as specific as possible. Hint: Write n in binary, and use parts (a) and (b) for data.
     
          9.  Time Complexity of Graph Matching

                A particular graph-matching algorithm on n nodes, works by doing n2 steps, and then solving a new matching problem on a graph with one vertex less.
        With one node, the algorithm takes one step.

        a. Construct a linear non-homogeneous recurrence equation and solve it by substitution, to show that the number of steps it takes to run the algorithm on a graph with n nodes is equal to the sum of the first n perfect squares.

        b. In class we proved directly in two different ways that the sum of the first n perfect squares is n(n+1)(2n+1)/6.  Derive this closed formula a third way, by solving the linear non-homogeneous recurrence equation from part (a) using the fancier techniques we developed in class.
               
        c. Show that the time complexity of this algorithm is O(n3) and Ω(n3).
       
    10.  Except for the base cases, the following recurrence is identical to a famous recurrence that you have seen many times.

      a.  Write a recurrence relation to compute the number of binary strings with n digits that do not have two consecutive 1’s. Explain why your equation is correct.

            b.  Solve this recurrence equation. 
        (Note:  We solved this recurrence in class with different base cases, and the solution appears in an induction proof in assignment 2. )

            c.   Determine what percentage of 8-bit binary strings do not contain two consecutive 1’s.
     
    11.  Time Complexity of Matrix Multiplication

    The standard way to multiply two n by n matrices takes n3 scalar multiplications, n for each of the n2 entries.
    However, Strassen’s algorithm shows how to recursively multiply two n by n matrices by multiplying 7 pairs of n/2 by n/2 matrices,
    and then doing n2 operations to combine them.  Assume T(1) = 1.

    a.  Write the recurrence equation for this algorithm, where T(n) is the time it takes to multiply a pair of n by n matrices.

    b.  Solve it explicitly and show you get the same Big-theta as predicted by the Master Theorem. 
    Hint: Recall that algn = nlga,  which can be proved by taking loga of both sides and reducing to lgn = lga (logan).

    c.  What would be the complexity of Strassen's algorithm had he used 8 sub-problems of size n/2?

    12. Write and solve the recurrence equations for the time complexity of the following recursive algorithms.
    Explain why your equations are correct.
                   
          a.  To search for a value in a sorted list, compare it to the middle value, and search the right half of the list if it is larger,
                  and the left half if it is smaller.  You  may assume n is a power of two.

      b.  The maximum of a list of numbers is the larger of the maximum of the first half and the maximum of the second half. 
          You  may assume n is a power of two.

      c.  To sort a list of numbers, divide the list into four equal parts.  Sort each part.  Merge these sorted four lists into two
      sorted lists, and then merge the two into one.  You  may assume n is a power of four.
     
    13.  Parenthesized Expressions

      a.  A sequence of n+1 matrices A1A2…An+1 can be multiplied together in many different ways dependent
      on the way n pairs of parentheses are inserted.  Notice that the matrices stay ordered 1 through n.
      For example:  for n+1 = 3,  there are two ways to multiply the matrices ((A1*A2)*A3) and (A1*(A2*A3)). 
      Write a list of the different ways to parenthesize a sequence of n+1 matrices for n+1 = 2, 3, and 4.

      b.  Write a recurrence equation for the number of ways to insert k pairs of parenthesis.  Do not solve it. 
      (Hint: Concentrate on where the last multiplication occurs).

      c.  A balanced arrangement of parenthesis is defined inductively as follows:
        The empty string is a balanced arrangement of parentheses. 
        If x is balanced arrangement of parentheses, then so is (x)
        If u and v are each a balanced arrangement of parentheses, then so is uv.
      Write a list of strings that represent a balanced arrangement of n pairs of parentheses for n=1, 2, and 3.

          d.  Describe a 1-1 correspondence between the strings that are balanced arrangements of n pairs of parentheses,
      and the number of ways to multiply a sequence of n+1 matrices.  Hint:  Associate the multiplication signs of the matrices with the open parens of the balanced parentheses.
     
    14.  The following recurrence cannot be solved using the master theorem, which only works for polynomials.
          Solve it directly by substitution, and calculate its order of growth.
    T(n) = 4T(n/2) + (n lgn)2 and T(1) = 1.
    back