Search-TADM2E
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?
