Note that there is more than one correct recurrence for Section 8.1 number 14,Section 8.1: 8, 14 (Use "at least one zero" in place of "two consecutive zeros"), 20.
and in general there may be more than one recurrence with the same closed form solution.
ConstrainedHanoi(n-1, From, To, Using);}
move disk from From to Using;
ConstrainedHanoi(n-1, To, From, Using);
move disk from Using to To;
ConstrainedHanoi(n-1, From, To, Using); }
000
001
011
010
110
111
101
100
For example, 0000001 would be 0000001, 1111111 would
be 1000000, and 1101011 would be 1011110.
a. Prove by induction on n (the
number of bits in m) that this method works.
Proof Outline and Hints:
The base case is when n = 1. Check that the algorithm does the right thing for 0 and for 1.
For general n, there are two cases to
consider: when m starts with 0 and when it
starts with 1.
Case 1: When m starts with 0.
Let m =
0y consist of n bits, and
let x be the code that the algorithm computes
from y.
By induction, since
y has n-1 bits, then x is the
correct (y-th) Gray code for n -1 bits.
Prove that the n-bit
code computed by the algorithm on 0y equals 0x.
Prove that if the
yth Gray code with n-1 bits is
x, then the mth Gray code with n
bits is 0x.
Case 2: When m starts with
1.
Let m = 1y
consist of n bits. Let 1x or 0x be
the code computed by the algorithm on y.
Case 2a:
1x
By induction,
since y has n-1 bits,
then 1x is the correct (yth)
Gray code for n-1 bits.
Prove that the n-bit
code computed by the algorithm on 1y equals 10x.
Prove that if the mth
Gray code with n -1 bits is 1x, then the m
+ 2n Gray code with n bits
is 10x.
Case 2b:
0x
By induction, since
y has n-1 bits, then
0x is the correct (yth) Gray code for
n-1 bits.
Prove that the n-bit
code computed by the algorithm on 1y equals 11x.
Prove that if the mth
Gray code with n -1 bits is 0x, then
the m + 2n Gray
code with n bits is 11x.
b. Describe an algorithm that takes an
element of a Gray code, and computes which one it is in
the ordered list.
(This is the inverse of the
algorithm described above).
T(n) = 4T(n/2) + (n lgn)2 and T(1) = 1.