Shai Simonson         CS 201

    Discrete Math for Computer Scientists

    Assignment 3

    Due:  Before Thanksgiving.

        1. Problems in the book:  7.1 - 12, 24, 36      7.2 -  4, 8, 28, 30, 36
     
    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:
     
      In order to move n disks from From to To, using Using1 and Using2:
      If n equals 1, then 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. Explain why Sloppy's algorithm will make illegal moves.
      c. Fruity Freddie suggests 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.
      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.
      a.  Construct a correct solution to the Towers of Hanoi problem with four pegs, that is faster than the standard solution with three pegs.
      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.
     
    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.
      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.
     
    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.
      a.  Conjecture a theorem regarding the longest consecutive sequence of 1's in the ith column of your chart.
      b.  Prove your theorem by induction.
     
    7.  Converting Gray codes.
      An algorithm that takes a binary number n and outputs the nth element of a Gray code, works like this:
      Moving left to right across the bits of n, we construct the Gray code from left to right.
      1.  Copy down the leftmost bit of n. 
      2.  For each remaining bit of n,
              if the bit is 0,
              then copy the bit to its right over to the Gray code. 
              if the bit is 1, then copy the complement of the bit to its right over to the Gray code.

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

      a.  Prove by induction that this method works. Hint:  Consider two cases: when n starts with 0 and when n starts with 1.
      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 algorithm for computing an where a and n are integers.  If n = 0, then return 1.  If n is even then compute an/2 recursively, and square it. 
    Otherwise, compute an-1
    recursively and multiply the result by a.  Use recurrence equations to solve the following problems.
      a.  How many multiplications does this method use when n is a power of two?
      b.  How many multiplications when n is one less than a power of two?
      c.  What exactly determines the number of multiplications for general n. Be as specific as possible. Hint: Write n in binary.
     
    9.  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.
      a.  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. Derive the formula for the sum of the first n perfect squares by constructing an appropriate linear non-homogeneous recurrence equation
      and solving it.
      c.  Show that the time complexity of this algorithm is O(n3).
       
    10.  Write a recurrence relation to compute the number of binary strings with n digits that do not have two consecutive 1’s. 
    Hint: consider extending the string by one character.
        Solve the recurrence equation by comparing it with the solution to a similar one we did in last assignment.
        Determine what percentage of 8-bit binary strings do not contain two consecutive 1’s.
     
    11.  Strassen’s algorithm shows how to 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. 
    Write the recurrence equation for this algorithm, and calculate the complexity of Strassen’s algorithm,
    by solving the recurrence by repeated substitution.
     

    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.
      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.
      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.
     
    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. 
      For example:  for n+1 = 3,  there are two ways to insert the parentheses: ((A1A2)A3) and (A1(A2A3)). 
      Write a recurrence equation for the number o
      f ways to insert k pairs of parenthesis.  Do not solve it.  (Hint: Concentrate on where the last multiplication occurs).
      b.  Write a list of the different ways to parenthesize a sequence of n+1 matrices for n+1=2,3,4.
      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,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.
     
    14.  The following recurrence cannot be solved using the master theorem which we will study next week.  Solve it directly by substitution,
    and calculate its order of growth.
    T(n) = 4T(n/2) + (nlogn)2 and T(1) = 1.
    back
     

    shai@stonehill.edu

    http://www.stonehill.edu/compsci/shai.htm