**Available Solutions for the following Chapter 10 exercises:**

10.1 Show that the greedy algorithm to minimize the mean completion time for

multiprocessor job scheduling works. - Get solution

frequency: colon (100), space (605), newline (100), comma (705), 0 (431),

1 (242), 2 (176), 3 (59), 4 (185), 5 (250), 6 (174), 7 (199), 8 (205), 9 (217).

Construct the Huffman code. . - Get solution

10.4 Part of the encoded file must be a header indicating the Huffman code. Give

a method for constructing the header of size at most O(N) (in addition to the

symbols), where N is the number of symbols.. - Get solution

10.5 Complete the proof that Huffman’s algorithm generates an optimal prefix code.. - Get solution

10.6 Show that if the symbols are sorted by frequency, Huffman’s algorithm can be implemented in linear time. . - Get solution

10.10 Explain how to implement first fit and best fit in O(N logN) time.. - Get solution

10.11 Show the operation of all the bin-packing strategies discussed in Section 10.1.3 on the input 0.42, 0.25, 0.27, 0.07, 0.72, 0.86, 0.09, 0.44, 0.50, 0.68, 0.73, 0.31,0.78, 0.17, 0.79, 0.37, 0.73, 0.23, 0.30. . - Get solution

10.13 Prove Theorem 10.7. . - Get solution

10.14 Prove Theorem 10.8.. - Get solution

10.15 N points are placed in a unit square. Show that the distance between the closest pair is O(N−1/2). . - Get solution

10.16 Argue that for the closest-points algorithm, the average number of points in the strip is O(√ N). (Hint: Use the result of the previous exercise.). - Get solution

10.18 What is the asymptotic running time of quickselect, using a median-of-medianof-three partitioning strategy? . - Get solution

10.19 Show that quickselect with median-of-median-of-seven partitioning is linear.Why is median-of-median-of-seven partitioning not used in the proof? . - Get solution

10.22 Complete the analysis of the sampling algorithm described at the end of Section 10.2.3, and explain how the values of δ and s are chosen. . - Get solution

10.23 Show how the recursive multiplication algorithm computes XY, where X = 1234 and Y = 4321. Include all recursive computations.. - Get solution

10.24 Show how to multiply two complex numbers X = a + bi and Y = c + di using

only three multiplications. . - Get solution

10.25 a. Show that

XLYR + XRYL = (XL + XR)(YL + YR) − XLYL − XRYR

b. This gives an O(N1.59) algorithm to multiply N-bit numbers. Compare this

method to the solution in the text. . - Get solution

10.27 Why is it important that Strassen’s algorithm does not use commutativity in the

multiplication of 2 × 2 matrices? . - Get solution

10.28 Two 70×70 matrices can be multiplied using 143,640 multiplications. Show how

this can be used to improve the bound given by Strassen’s algorithm. . - Get solution

10.29 What is the optimal way to compute A1A2A3A4A5A6, where the dimensions of

the matrices are A1 : 10 × 20, A2 : 20 × 1, A3 : 1 × 40, A4 : 40 × 5, A5 : 5 × 30,

A6: 30 × 15? . - Get solution

10.30 Show that none of the following greedy algorithms for chained matrix multiplication

work. At each step

a. Compute the cheapest multiplication.

b. Compute the most expensive multiplication.

c. Compute the multiplication between the two matrices Mi and Mi+1, such that

the number of columns in Mi is minimized (breaking ties by one of the rules

above). . - Get solution

10.32 Show the optimal binary search tree for the following words, where the frequency

of occurrence is in parentheses: a (0.18), and (0.19), I (0.23), it (0.21), or (0.19). - Get solution

10.35 Write a routine to reconstruct the shortest paths from the algorithm in Section 10.3.4. . - Get solution

b. Show how the randomized primality test works for N = 561 with several choices of A. . - Get solution

{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 17 }. Find the two point sets.. - Get solution

10.43 Extend the reconstruction algorithm to find all homometric point sets given a distance set. . - Get solution

4 + 4√ 2. . - Get solution

cu,v + cv,w ≥ cu,w. Show how to compute a traveling salesman tour of cost at most twice optimal. (Hint: Construct a minimum spanning tree.). - Get solution

10.49 You are a tournament director and need to arrange a round robin tournament among N = 2k players. In this tournament, everyone plays exactly one game each day; after N − 1 days, a match has occurred between every pair of players. Give a recursive algorithm to do this. . - Get solution

10.50 a. Prove that in a round robin tournament it is always possible to arrange the players in an order pi1 , pi2 , . . . , piN such that for all 1 ≤ j < N, pij has won the match against pij+1 .

b. Give an O(N logN) algorithm to find one such arrangement. Your algorithm

may serve as a proof for part (a). . - Get solution

j−1

k=i

|bk − b| = (j − i)|b − b|, where b is the average size of a blank on this line.

This is true of the last line only if b < b, otherwise the last line is not ugly at all.

b. Give the time and space complexities for your algorithm (as a function of the number of words, N).

c. Consider the special case where we are using a fixed-width font, and assume the optimal value of b is 1 (space). In this case, no shrinking of blanks is allowed, since the next smallest blank space would be 0. Give a linear-time algorithm to generate the least ugly setting for this case. . - Get solution

and B = p,r,o,g,r,a,m,m,i,n,g, then the longest common subsequence is a,m,i and has length 3. Give an algorithm to solve the longest common subsequence problem. Your algorithm should run in O(MN) time. . - Get solution

a. Give an algorithm that solves the knapsack problem in O(NK) time.

b. Why does this not show that P = NP? . - Get solution

10.58 You are given a currency system with coins of (decreasing) value c1, c2, . . . , cN cents.

a. Give an algorithm that computes the minimum number of coins required to give K cents in change.

b. Give an algorithm that computes the number of different ways to give K cents in change. . - Get solution

10.59 Consider the problem of placing eight queens on an (eight-by-eight) chess board.

Two queens are said to attack each other if they are on the same row, column, or

(not necessarily main) diagonal.

a. Give a randomized algorithm to place eight nonattacking queens on the board.

b. Give a backtracking algorithm to solve the same problem.

c. Implement both algorithms and compare the running time. . - Get solution

a. Why does this algorithm not work for general graphs?

b. Prove that this algorithm terminates for acyclic graphs.

c. What is the worst-case running time of the algorithm? . - Get solution

10.62 Let A be an N-by-N matrix of zeros and ones. A submatrix S of A is any group of contiguous entries that forms a square.

a. Design an O(N2) algorithm that determines the size of the largest submatrix of ones in A. For instance, in the matrix that follows, the largest submatrix is a

4-by-4 square.

10111000

00010100

00111000

00111010

00111111

01011110

01011110

00011110

b. Repeat part (a) if S is allowed to be a rectangle instead of a square. Largest is measured by area.

10.67 Othello played on a 6-by-6 board is a forced win for black. Prove this by writing

a program. What is the final score if play on both sides is optimal? . - Get solution