MCS-236 Homework 5

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.
  1. (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.
  2. Solve the last problem with another pairs of strings (other than 0101 and 1010).
  3. 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_i,v_i+1 in an odd cycle v₁,...,v_k of G. Some edges will be directed from v_i to v_i+1 and some from v_i+1 to v_i. If the edge was from v_i to v_i+1, there must also be a path from v_i+1 to v_i (why?). Consider the cases when this path is of even length and when it is of odd length.

• 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_k 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 are equivalent:
  1. G is a forest.
  2. Every induced subgraph of G has a vertex of degree at most 1.
  3. Every connected subgraph of G is an induced subgraph.
  4. The number of components in G is the number of vertices minus the number of edges.
  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.

  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)