Due by Wednesday 27/1, 1pm in CSE office.  
The answers will be put up on Wednesday evening by 5pm.
We will have quiz 1 on on Thursday Jan 28, in usual lecture hours, in
class and in the room opposite.

1.  Problem 5 of chapter 10.  Show a dilation 2, load 2 embedding.

All problems on chapter 10 are practice problems.

2.  Consider that the deBruijn graph is directed, with each node x
    having a directed connection to s(x) and s(x) exor 1.  Draw the
    graph on 1,2,3 dimensions.

3.  Let G=(V,E) be a directed graph.  The line graph L(G) of G, has
    the vertex set E, and a directed edge from e to f if in G the edges e,f
    form a directed path.  Note that e,f might be self loops and the
    directed paths need not be simple.

    Show that the line graph of the deBruijn graph dB_k (directed, as
    defined above) on k dimensions is the deBruijn graph dB_{k+1} on k+1
    dimensions.  You are not expected to give a formal proof, but only
    answer the following question: Suppose e=(x,y) is an edge in dB_k, as
    discussed above, it becomes a vertex v in the line graph.  What is
    the relationship between x,y and v?

    (Practice problem, do not submit: Suppose we want to find a 2^k
    bit cyclic sequence that contains every k bit sequence exactly
    once.  Express this as a problem of finding a Hamiltonian circuit
    on a suitable graph as well as an Eulerian circuit on a suitable
    graph.)

4.  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 for each node of the N
    input butterfly, and also "local" numbers 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.

------