CHAPTER 10
Algorithm Design Techniques
10.1 First, we show that if N evenly divides P, then each of j(i−1)P + 1 through jiP must be placed as the ith job on
some processor. Suppose otherwise. Then in the supposed optimal ordering, we must be able to find some
jobs jx and jy such that jx is the tth job on some processor and jy is the t + 1th job on some processor but tx > ty.
10.2 Sort the jobs by their profits in descending order. Then for each job place it in the last open spot that meets its
10.3
10.4 One method is to generate code that can be evaluated by a stack machine. The two operations are push (the
one node tree corresponding to) a symbol onto a stack and combine, which pops two trees off the stack,
merges them, and pushes the result back on. For the example in the text, the stack instructions are push(s),
10.6 Maintain two queues, Q1 and Q2. Q1 will store single-node trees in sorted order, and Q2 will store multinode
10.10 To implement first fit, we keep track of bins bi, which have more room than any of the lower numbered bins.
A theoretically easy way to do this is to maintain a splay tree ordered by empty space. To insert w, we find
To implement best fit, we need to keep track of the amount of empty space in each bin. As before, a
splay tree can keep track of this. To insert an item of size w, perform an insert of w. If there is a bin that can
10.11 Next fit: 12 bins (.42, .25, .27), (.07, .72), (.86, .09), (.44, .50), (.68), (.73), (.31), (.78, .17), (.79), (.37), (.73,
Best fit: 10 bins (.42, .25, .27), (.07, .72, .09), (.86), (.44, .50), (.68, .31), (.73, .23), (.78, .17), (.79), (.37, .30
Best fit decreasing: 10 bins (.86, .09), (.79, .17), (.78), (.73, .27), (.73, .25), (.72, .23), (.68, .31), (.50, .44),
10.13 We prove the second case, leaving the first and third (which give the same results as Theorem 10.6) to the
reader. Observe that
( ) log
m
m p p
T N a b i
=
10.15 Divide the unit square into N − 1 square grids each with side
11N−
. Since there are N points, some grid
10.16 The results of the previous exercise imply that the width of the strip is
(1 )ON
. Because the width of the
10.18 The recurrence works out to
10.19 The recurrence for median–of-median–of-seven partitioning is
10.22 We derive the values of s and δ, following the style in the original paper [17]. Let Rt,,X be the rank of element
t in some sample X. If a sample S of elements is chosen randomly from S, and |S| = s, |S | = N, then we’ve
already seen that
We choose v1 and v2 so that
The probability that k is not between v1 and v2 is
These mean and variance equations imply
This gives equation (A):
12
logd s s N==
(A)
The low order term is minimized when
Combining Equations (A) and (B), we see that
10.23 First, we calculate 12*43. In this case, XL = 1, XR = 2, YL = 4, YR = 3, D1 = −1, D2 = −1, XLYL = 4, XRYR = 6,
D1D2 = 1, D3 = 11, and the result is 516.
10.25 The algebra is easy to verify. The problem with this method is that if X and Y are positive N bit numbers,
10.29 1150 scalar multiplications are used if the order of evaluation is
10.30 (a) Let the chain be a 1 1 matrix, a 1 A matrix, and an A B matrix. Multiplication by using the first two
10.32 The optimal binary search tree is the same one that would be obtained by a greedy strategy: I is at the root
10.35 A recursive procedure is clearly called for; if there is an intermediate vertex, stopOver on the path
from s to t , then we want to print out the path from s to stopOver and then stopOver to t . We don’t
want to print out stopOver twice, however, so the method does not print out the first or last vertex
on the path and reserves that for the driver.
// Print the path between s and t, except do not print
10.39 If the modulus is a power of two, then the least significant bit of the “random” number oscillates. Thus flip
10.40 (a) 25 32 mod 341, 210 1 mod 341. Since 322 1 mod 341, this proves that 341 is not prime. We can also
(b) If A = 2, then although 2560 1 mod 561, 2280 1 mod 561 proves that 561 is not prime. If A = 3, then 3561
10.43 To find all point sets, we backtrack even if found = = true, and print out information when line 2 is executed.
10.44
10.47 We place circles in order. Suppose we are trying to place circle j of radius rj. If some circle i of radius ri is
10.48 Construct a minimum spanning tree T of G, pick any vertex in the graph, and then find a path in T that goes
through every edge exactly once in each direction. (This is done by a depth-first search; see Exercise 9.31.)
If there were a tour of cost K, then by removing one edge on the tour, we would have a minimum
10.49 If there are two players, then the problem is easy, so assume k > 1. If the players are numbered 1 through N,
then divide them into two groups: 1 through N/2 and N/2 + 1 though N. On the ith day, for 1 i N/2, player
10.50 Divide the players into two groups of size
2N
and N/2, respectively, and recursively arrange the
10.53 (a) Use dynamic programming. Let Sk = the best setting of words wk, wk + 1, . . . wN, Uk = the ugliness of this
setting, and lk = for this setting, (a link to) the word that starts the second line.
(b) The running time is quadratic in the case where the number of words that can fit on a line is consistently
10.54 An obvious O(N2) solution to construct a graph with vertices 1, 2, . . . , N and place an edge (v,w) in G iff av <
aw. This graph must be acyclic, thus its longest path can be found in time linear in the number of edges; the
10.55 This is a classic program using dynamic programming. Let the matrix M[i][j] be the integer matrix that
contains the length of the longest common subsequence between the first i letters of A and the first j letters of
string lcs(string w1, string w2)
vector<vector<int>> M(n+1);
for (i = 0; i< = n; i++ )
// Now the trace back code
i = n;
j = m;
while (i > 0 && j > 0)
10.57 (a) A dynamic programming solution resolves part (a). Let FITS (i, s) be 1 if a subset of the first i items sums
10.58 (a) Let the minimum number of coins required to give x cents in change be COIN (x); COIN (0) = 0. Then
10.59 (a) Place eight queens randomly on the board, making sure that no two are on the same row or column. This
10.60 (a) Since the knight leaves every square once, it makes B2 moves. If the squares are alternately colored black
10.61 (a) If the graph has a cycle, then the recursion does not always make progress toward a base case, and thus an
10.62 (a) A simple dynamic programming algorithm, in which we scan in row order suffices. Each square
