The Algorithm Design Manual: Chapter 7

7-1. A derangement is a permutation p of {1, . . . , n} such that no item is in its proper position, i.e. pi ̸= i for all 1 ≤ i ≤ n. Write an efficient backtracking program with pruning that constructs all the derangements of n items.

Solution

 

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.

Solution

7-8. Design and implement an algorithm for solving the maximum satisfiability prob- lem discussed in Section 14.10 (page 472).

Solution

 

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

7-16. An anagram is a rearrangement of the letters in a given string into a sequence of dictionary words, like Steven Skiena into Vainest Knees. Propose an algorithm to construct all the anagrams of a given string.
Solution See 7-4.

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?

Solution One basic idea is to use two events with equal probability eight times and count one of these events and use this as our number. E.g. we take 0, 1 from rng04 and encode it as zero and take 2, 3 from rng04 and encode it as one. Now zero and one happen with equal probability. We now generate enough numbers and count the ones which will be the number in rng07.
How many calls do we need? Let’s first analyze our encoded variable.

That is, we need \lim_{n \rightarrow \infty} sum_{k=0}^{n} (\frac{1}{5})^k (k + 1) = \frac{25}{16} calls. Therefore we need \frac{25}{16} \cdot 8 = 12.5 calls for our rng07.

SPOJ: 1728. Common Permutation

Given two strings of lowercase letters, a and b, print the longest string x of lowercase letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b.

Problem: Sphere Online Judge (SPOJ) – Problem CPRMT

Solution: That’s short and nice problem. You have to find all letters which are in both strings. I’d actually like to see some other implementations of this. I bet there are some languages which handle this in a smart way.