Section 14.5
3. It is tempting to say something like “nondeterministically select V i as first
vertex, V j as second vertex, etc.” but this is not correct. While
nondeterminism implies a choice, the choice on each move is from a limited
number of options. Since the i in V i is arbitrarily large, we cannot do this. A
better way is to
(1) Create a list of numbers 1, 2,…, n in unary notation. The length of the
list is O(n 2 ), so this can be done in O(n 2 ) time.
(2) Scan the list and nondeterministically select one number. If a number
is selected, add it to the permutation and remove it from the list.
(3) Repeat step (2) n times.
Therefore, the whole process can be done in O(n 3 ) time.
Section 14.6
5. Take the HAMPATH graph and complete it. Weight existing edges with 0 and
new edges with 1. Apply the TSP algorithm with k = 0. If there is a solution,
then there exists a Hamiltonian path.
3. It is tempting to say something like “nondeterministically select V i as first
vertex, V j as second vertex, etc.” but this is not correct. While
nondeterminism implies a choice, the choice on each move is from a limited
number of options. Since the i in V i is arbitrarily large, we cannot do this. A
better way is to
(1) Create a list of numbers 1, 2,…, n in unary notation. The length of the
list is O(n 2 ), so this can be done in O(n 2 ) time.
(2) Scan the list and nondeterministically select one number. If a number
is selected, add it to the permutation and remove it from the list.
(3) Repeat step (2) n times.
Therefore, the whole process can be done in O(n 3 ) time.
Section 14.6
5. Take the HAMPATH graph and complete it. Weight existing edges with 0 and
new edges with 1. Apply the TSP algorithm with k = 0. If there is a solution,
then there exists a Hamiltonian path.