Varied due dates.
Extra credit problems are due before the last day of classes. I don't
specify how much extra credit you'll get. You can always submit any
problem marked (+) in West for extra credit.
- 5#1 Due Thursday, October 24: Clearly show your work by explaining
how the graph at the top of page 61 can be adjusted to solve these
- (West 1.4.26) Arrange seven 0's and
seven 1's cyclically so that the 14 strings of four consecutive bits
are all the 4-digit binary strings other than 0101 and 1010.
- Solve the last problem with another pairs of strings (other than
0101 and 1010).
- Prove that this was the only other pair (besides 0101 and 1010)
that you could have removed to solve the same problem.
- 5#2 Due Friday, October 25: (West 1.4.29) Suppose G is
a graph and D is an orientation of G that is
strongly connected. Prove that if G has an odd cycle, then
D has an odd cycle.
Hint: Consider each pair vi,vi+1 in
an odd cycle v1,...,vk of
G. Some edges will be directed from vi to
vi+1 and some from vi+1 to
vi. If the edge was from vi to
vi+1, there must also be a path from
vi+1 to vi (why?).
Consider the cases when this path is of even length and when it is of
- 5#3 Due Tuesday, October 29: A Hamiltonian cycle in a graph is a
cycle which contains all the vertices (but not necessarily all the
edges) in the graph. Unlike Eulerian tours, there is no known
efficient algorithm to detect whether a graph has a Hamiltonian cycle.
(See page 286 of West for a longer introduction.)
A Grey code, like a de Bruijn sequence, is a way to cycle through all
the k-bit binary strings. Each string can be obtained from
the previous by changing one bit. For example, here's a
3-bit Grey code:
000 -> 010 -> 011 -> 111 -> 110 -> 100 -> 101 -> 001 --
Some background: Grey codes are useful in control design because they avoid race
conditions. If a counter counted normally, going 000, 001, 010,
..., there is an opportunity for a race condition. If both
bit changes going from 001 to 010 don't happen at exactly the
same time, then 011 or 000 might appear in between for a brief moment.
- Prove (by induction) that any hypercube Qk
contains a Hamiltonian cycle.
- Use your result to prove that an k-bit Grey code
exists for all k.
- 5#4 Due Friday, October 31: (West 2.1.8) Prove that the following
This problem is a bit harder than most, not because
any portion of the proof is hard, but because it involves a few
small proofs. You could, for instance, prove 1 => 2, 2 => 3, 3 => 4,
4 => 2, and 2 => 1. I recommend you try to prove a few implications,
and once you've done some, see what implications a classmate has shown.
- G is a forest.
- Every induced subgraph of G has a vertex of degree at most 1.
- Every connected subgraph of G is an induced subgraph.
- The number of components in G is the number of vertices
minus the number of edges.
Facts and techniques that might help: Definition 2.1.1 and the first
sentence of example 2.1.2, Lemma 2.1.3, Theorem 2.1.4, Corollary
- 5#5 Attend at least one talk given by Steve Smale, preferably two.
Write 3-4 sentences about the talk you attended.
- 5#6 Due Monday, November 4: Draw the tree with each of the
following Prufer codes: (71244441), (123456), (654321)