Assignment #4

Theme: Backtracking and Gray codes

Assigned:October 27, 2015.

Due:November 6, 2015. Reminder: homework should be handed in at the beginning of class and should be in latex (or tex).

• From the backtracking handout: Problem 4.

• From the backtracking handout: Problem 10. Turn in a program listing and the output of your program.

• How many moves are required to solve the Chinese Rings Puzzle if there are $n$ rings? I.e., what is the rank of $11 \cdots 1$ in the BRGC? Express your answer as simply as possible (no summations).

• What is the first number in the 10 billion odd number dictionary with Winkler's rules (spaces don't count; i.e., are compressed)? What is the last number with my rules?

• Prove the existence of a Gray path for the set of all binary strings of length $n$ with no $00$ substring. How many such strings are there? Why didn't I ask for a Gray cycle? Are there any values of $n$ for which Gray cycles exist? HINT: The non-existence of Gray cycles often boils down to a parity problem in the underlying bipartite graph.