Due Friday Feb 4.  
All problems of chapter 10 are good practice problems.

Turn in the following.  I will add a few problem on Tuesday.

1.  Problem 6 of chapter 8.

2.  Problem 4 of chapter 10.

3.  In class we considered the problem of establishing vertex disjoint
    paths from input x to output x+b mod 2^k in a N=2^k node butterfly
    for all x and a fixed integer b.  Let us call this the b-shift
    problem.  In this exercise you are to give an inductive proof
    based on the recursive structure of the buttefly that the problem
    can be solved.

    An N input butterfly is made up of two N/2 input butterflies
    together with some additional wiring.  Assume inductively that the
    b-shift problem can be solved for the N/2 input butterflies (for
    all b).  Show that to solve the b-shift problem on the N input
    butterfly it suffices to solve the problem (possibly for some
    other values of b -- which?) on the N/2 input butterflies.  Then
    the result should follow from the inductive hypothesis.  It might
    be useful to consider a "global" number (address) for each node of
    the N input butterfly, and also "local" numbers (address) for each
    node relative to the N/2 input butterfly to which they belong.

    Work out the following example: Suppose b=5 for the N/2 case.
    What problem does this generate for the smaller butterflies?
    Check your answer by drawing it out for N=8.  Do not submit this part.

4.  Problem 2 of notes on the Multibutterfly.

5.  Problem 4 of notes on the Multibutterfly.  Also evaluate d for
    alpha=1/10, beta=2 and probability = 99%.

------