Exercises

 

1. (*) A derangement is a permutation p of such that no item is in its proper position, i.e. for all .   Write an efficient backtracking program with pruning that constructs all the derangements of n items.
2. (*) Multisets are allowed to have repeated elements. A multiset of n items may thus have fewer than n! distinct permutations. For example, has only six different permutations: , , , , , and .   Design and implement an efficient algorithm for constructing all permutations of a multiset.
3. (*) Design and implement an algorithm for testing whether two graphs are isomorphic to each other. The graph isomorphism problem is discussed in Section . With proper pruning, graphs on hundreds of vertices can be tested reliably.
4. (**) Design and implement an algorithm for solving the subgraph isomorphism problem. Given graphs G and H, does there exist a subgraph H' of H such that G is isomorphic to H'. How does your program perform on such special cases of subgraph isomorphism as Hamiltonian cycle, clique, independent set, and graph isomorphism.
5. (*) Design and implement an algorithm for solving the set cover problem, discussed in Section . Use it to solve special-case vertex cover problems as well as general set cover problems.
6. (**) In the turnpike reconstruction problem, you are given n(n-1)/2 distances in sorted order. The problem is to find the positions of the points on the line that give rise to these distances. For example, the distances can be determined by placing the second point 1 unit from the first, the third point 3 from the second, and the fourth point 2 from the third. Design and implement an efficient algorithm to report all solutions to the turnpike reconstruction problem. Exploit additive constraints when possible to minimize search. With proper pruning, problems with hundreds of points can be solved reliably.