*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
three problems.
- (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

`v`in an odd cycle_{i},v_{i+1}`v`of_{1},...,v_{k}`G`. Some edges will be directed from`v`to_{i}`v`and some from_{i+1}`v`to_{i+1}`v`. If the edge was from_{i}`v`to_{i}`v`, there must also be a path from_{i+1}`v`to_{i+1}`v`(why?). Consider the cases when this path is of even length and when it is of odd length._{i} - 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
`Q`contains a Hamiltonian cycle._{k} - Use your result to prove that an
`k`-bit Grey code exists for all`k`.

- Prove (by induction) that any hypercube
- 5#4 Due Friday, October 31: (West 2.1.8) Prove that the following
are equivalent:
`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 2.1.5, induction.

- 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)