# Combinatorial Search and Heuristic Methods

BackTracking

7-1. A derangement is a permutation $p$ of $\{1,\ldots,n\}$ such that no item is in its proper position, i.e. $p_i \neq i$ for all $1 \leq i \leq n$. derangement Write an efficient backtracking program with pruning that constructs all the derangements of $n$ items.}

7-2. Multisets are allowed to have repeated elements. A multiset of $n$ items may thus have fewer than $n!$ distinct permutations. For example, $\{1,1,2,2\}$ has only six different permutations: $\{1,1,2,2\}$, $\{1,2,1,2\}$, $\{1,2,2,1\}$, $\{2,1,1,2\}$, $\{2,1,2,1\}$, and $\{2,2,1,1\}$. multiset Design and implement an efficient algorithm for constructing all permutations of a multiset.

7-3. Design and implement an algorithm for testing whether two graphs are isomorphic to each other. The graph isomorphism problem is discussed in graph-isomorphism. With proper pruning, graphs on hundreds of vertices can be tested reliably.

7-4. Anagrams are rearrangements of the letters of a word or phrase into a different word or phrase. Sometimes the results are quite striking. For example, MANY VOTED BUSH RETIRED is an anagram of TUESDAY NOVEMBER THIRD, which correctly predicted the result of the 1992 U.S. presidential election. Design and implement an algorithm for finding anagrams using combinatorial search and a dictionary.

7-5. 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?

7-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 $n$ points on the line that give rise to these distances. For example, the distances $\{1,2,3,4,5,6\}$ 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 the search. With proper pruning, problems with hundreds of points can be solved reliably. turnpike reconstruction problem

Combinatorial Optimization For each of the problems below, either (1) implement a combinatorial search program to solve it optimally for small instance, and/or (2) design and implement a simulated annealing heuristic to get reasonable solutions. How well does your program perform in practice?

7-7. Design and implement an algorithm for solving the bandwidth minimization problem discussed in bandwidth.

7-8. Design and implement an algorithm for solving the maximum satisfiability problem discussed in satisfiability.

7-9. Design and implement an algorithm for solving the maximum clique problem discussed in clique.

7-10. Design and implement an algorithm for solving the minimum vertex coloring problem discussed in vertex-coloring.

7-11. Design and implement an algorithm for solving the minimum edge coloring problem discussed in edge-coloring.

7-12. Design and implement an algorithm for solving the minimum feedback vertex set problem discussed in feedback-set.

7-13. Design and implement an algorithm for solving the set cover problem discussed in set-cover.

Interview Problems

7-14. Write a function to find all permutations of the letters in a particular string.

7-15. Implement an efficient algorithm for listing all $k$-element subsets of $n$ items.

7-16. An anagram is a rearrangement of the letters in a given string into Vainest Knees. Propose an algorithm to construct all the anagrams of a given string.

7-17. Telephone keypads have letters on each numerical key. Write a program that generates all possible words resulting from translating a given digit sequence (e.g., 145345) into letters.

7-18. You start with an empty room and a group of $n$ people waiting outside. At each step, you may either admit one person into the room, or let one out. Can you arrange a sequence of $2^n$ steps, so that every possible combination of people is achieved exactly once?

7-19. Use a random number generator (rng04) that generates numbers from $\{0,1,2,3,4\}$ with equal probability to write a random number generator that generates numbers from 0 to 7 (rng07) with equal probability. What are expected number of calls to rng04 per call of rng07?