One form of the knapsack problem is as follows: We are given a set of integersA = a1

Show that the greedy algorithm to minimize the mean completion time for multiprocessor job scheduling works.

The input is a set of jobs j1, j2, ... , jN, each of which takes one time unit to complete. Each job ji earns di dollars if it is completed by the time limit ti, but no money if completed after the time limit. a. Give an O(N2) greedy algorithm to solve the problem. b. Modify your algorithm to obtain an O(N logN) time bound. (Hint: The time bound is due entirely to sorting the jobs by money. The rest of the algorithm can be implemented, using the disjoint set data structure, in o(N logN).)

A file contains only colons, spaces, newlines, commas, and digits in the following 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.

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.

Complete the proof that Huffmans algorithm generates an optimal prefix code.

Show that if the symbols are sorted by frequency, Huffmans algorithm can be implemented in linear time.

Write a program to implement file compression (and uncompression) using Huffmans algorithm.

Show that any online bin-packing algorithm can be forced to use at least 3 2 the optimal number of bins, by considering the following sequence of items: N items of size 1 6 2 , N items of size 1 3 + , N items of size 1 2 +

Give a simple analysis to show the performance bound for first fit decreasing bin packing when a. The smallest item size is larger than 1 3 . b. The smallest item size is larger than 1 4 . c. The smallest item size is smaller than 2 11 .

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

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.

Write a program that compares the performance (both in time and number of bins used) of the various bin-packing heuristics.

Prove Theorem 10.7.

Prove Theorem 10.8.

N points are placed in a unit square. Show that the distance between the closest pair is O(N1/2).

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.)

Write a program to implement the closest-pair algorithm.

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

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?

Implement the quickselect algorithm in Chapter 7, quickselect using medianof-median-of-five partitioning, and the sampling algorithm at the end of Section 10.2.3. Compare the running times.

Much of the information used to compute the median-of-median-of-five is thrown away. Show how the number of comparisons can be reduced by more careful use of the information.

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

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

Show how to multiply two complex numbers X = a + bi and Y = c + di using only three multiplications.

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.

a. Show how to multiply two numbers by solving five problems that are roughly one-third of the original size. b. Generalize this problem to obtain an O(N1+ ) algorithm for any constant >0. c. Is the algorithm in part (b) better than O(N logN)?

Why is it important that Strassens algorithm does not use commutativity in the multiplication of 2 2 matrices?

Two 7070 matrices can be multiplied using 143,640 multiplications. Show how this can be used to improve the bound given by Strassens algorithm

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?

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)

Write a program to compute the best ordering of matrix multiplication. Include the routine to print out the actual ordering.

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).

Extend the optimal binary search tree algorithm to allow for unsuccessful searches. In this case, qj, for 1 j < N, is the probability that a search is performed for any word W satisfying wj < W < wj+1. q0 is the probability of performing a search for W < w1, and qN is the probability of performing a search for W > wN. Notice that N i=1 pi + N j=0 qj = 1.

Suppose Ci,i = 0 and that otherwise Ci,j = Wi,j + min i<kj (Ci,k1 + Ck,j) Suppose that W satisfies the quadrangle inequality, namely, for all i i  j j  , Wi,j + Wi  ,j  Wi  ,j + Wi,j  Suppose further, that W is monotone: If i i  and j j  , then Wi,j Wi  ,j  . a. Prove that C satisfies the quadrangle inequality. b. Let Ri,j be the largest k that achieves the minimum Ci,k1 + Ck,j. (That is, in case of ties, choose the largest k.) Prove that Ri,j Ri,j+1 Ri+1,j+1 c. Show that R is nondecreasing along each row and column. d. Use this to show that all entries in C can be computed in O(N2) time. e. Which of the dynamic programming algorithms can be solved in O(N2) using these techniques?

Write a routine to reconstruct the shortest paths from the algorithm in Section 10.3.4.

Write a routine to reconstruct the shortest paths from the algorithm in Section 10.3.4. CoinSide flip( ) 2 { 3 if( ( random( ) % 2 ) == 0 ) 4 return HEADS; 5 else 6 return TAILS; 7 } Figure 10.75 Questionable coin flipper Write a method and give an analysis of the running time to compute the binomial coefficients as follows: a. recursively b. using dynamic programming

Write the routines to perform insertion, deletion, and searching in skip lists.

Give a formal proof that the expected time for the skip list operations is O(logN).

Figure 10.75 shows a routine to flip a coin, assuming that random returns an integer (which is prevalent in many systems). What is the expected performance of the skip list algorithms if the random number generator uses a modulus of the form M = 2B (which is unfortunately prevalent on many systems)?

a. Use the exponentiation algorithm to prove that 2340 1 (mod 341). b. Show how the randomized primality test works for N = 561 with several choices of A

Implement the turnpike reconstruction algorithm.

Two point sets are homometric if they yield the same distance set and are not rotations of each other. The following distance set gives two distinct point sets: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 17 }. Find the two point sets.

Extend the reconstruction algorithm to find all homometric point sets given a distance set.

Show the result of pruning of the tree in Figure 10.76

5 a. Does the code in Figure 10.74 implement pruning or pruning? b. Implement the complementary routine.

Write the remaining procedures for tic-tac-toe.

The one-dimensional circle packing problem is as follows: You have N circles of radii r1,r2, ... ,rN. These circles are packed in a box such that each circle is tangent to the bottom of the box and are arranged in the original order. The problem is to find the width of the minimum-sized box. Figure 10.77 shows an example with circles of radii 2, 1, 2 respectively. The minimum-sized box has width 4 + 4 2.

Suppose that the edges in an undirected graph G satisfy the triangle inequality: 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.)

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

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).

We are given a set P = p1, p2, ... , pN of N points in a plane. A Voronoi diagram is a partition of the plane into N regions Ri such that all points in Ri are closer to pi than any other point in P. Figure 10.78 shows a sample Voronoi diagram for seven (nicely arranged) points. Give an O(N logN) algorithm to construct the Voronoi diagram.

A convex polygon is a polygon with the property that any line segment whose endpoints are on the polygon lies entirely within the polygon. The convex hull problem consists of finding the smallest (area) convex polygon that encloses a set of points in the plane. Figure 10.79 shows the convex hull for a set of 40 points. Give an O(N logN) algorithm to find the convex hull

Consider the problem of right-justifying a paragraph. The paragraph contains a sequence of words w1, w2, ... , wN of length a1, a2, ... , aN, which we wish to break into lines of length L. Words are separated by blanks whose ideal length is b (millimeters), but blanks can stretch or shrink as necessary (but must be >0), so that a line wiwi+1 ... wj has length exactly L. However, for each blank b we charge |b b| ugliness points. The exception to this is the last line, for which we charge only if b < b (in other words, we charge only for shrinking), since the last line does not need to be justified. Thus, if bi is the length of the blank between ai and ai+1, then the ugliness of setting any line (but the last) wiwi+1 ... wj for j > i is j1 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 a. Give a dynamic programming algorithm to find the least ugly setting of w1, w2, ... , wN into lines of length L. (Hint: For i = N, N 1, ... , 1, compute the best way to set wi, wi+1, ... , wN.) 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

The longest increasing subsequence problem is as follows: Given numbers a1, a2, ... , aN, find the maximum value of k such that ai1 < ai2 < < aik , and i1 < i2 < < ik. As an example, if the input is 3, 1, 4, 1, 5, 9, 2, 6, 5, the maximum increasing subsequence has length four (1, 4, 5, 9 among others). Give an O(N2) algorithm to solve the longest increasing subsequence problem.

he longest common subsequence problem is as follows: Given two sequences A = a1, a2, ... , aM, and B = b1, b2, ... , bN, find the length, k, of the longest sequence C = c1,c2, ... ,ck such that C is a subsequence (not necessarily continguous) of both A and B. As an example, if A = d,y,n,a,m,i,c 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.

The pattern-matching problem is as follows: Given a string S of text, and a pattern P, find the first occurrence of P in S. Approximate pattern matching allows k mismatches of three types: 1. A character can be in S that is not in P. 2. A character can be in P that is not in S. 3. P and S can differ in a position. As an example, if we are searching for the pattern textbook with at most three mismatches in the string data structures txtborpk, we find a match (insert an e, change an r to an o, delete a p). Give an O(MN) algorithm to solve the approximate string matching problem, where M = |P| and N = |S|.

One form of the knapsack problem is as follows: We are given a set of integers A = a1, a2, ... , aN and an integer K. Is there a subset of A whose sum is exactly K? a. Give an algorithm that solves the knapsack problem in O(NK) time. b. Why does this not show that P = NP?

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.

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.

In the game of chess, a knight in row R and column C may move to row 1 R B and column 1 C B (where B is the size of the board) provided that either |R R | = 2 and |C C | = 1 or |R R | = 1 and |C C | = 2 A knights tour is a sequence of moves that visits all squares exactly once before returning to the starting point. a. If B is odd, show that a knights tour cannot exist. b. Give a backtracking algorithm to find a knights tour.

Consider the recursive algorithm in Figure 10.80 for finding the shortest weighted path in an acyclic graph, from s to t. Distance shortest( s, t ) { Distance dt, tmp; if( s == t ) return 0; dt = ; for each Vertex v adjacent to s { tmp = shortest(v, t ); if( cs,v + tmp < dt) dt = cs,v + tmp; } return dt;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?

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.

Even if the computer has a move that gives an immediate win, it may not make it if it detects another move that is also guaranteed to win. Some early chess programs were problematic in that they would get into a repetition of position when a forced win was detected, thereby allowing the opponent to claim a draw. In tic-tac-toe, this is not a problem, because the program eventually will win. Modify the tic-tactoe algorithm so that when a winning position is found, the move that leads to the shortest win is always taken. You can do this by adding 9-depth to COMP_WIN so that the quickest win gives the highest value.

Write a program to play 5-by-5 tic-tac-toe, where 4 in a row wins. Can you search to terminal nodes?

The game of Boggle consists of a grid of letters and a word list. The object is to find words in the grid that are subject to the constraint that two adjacent letters must be adjacent in the grid, and each item in the grid can be used, at most, once per word. Write a program to play Boggle

Write a program to play MAXIT. The board is represented as an N-by-N grid of numbers randomly placed at the start of the game. One position is designated as the initial current position. Two players alternate turns. At each turn, a player must select a grid element in the current row or column. The value of the selected position is added to the players score, and that position becomes the current position and cannot be selected again. Players alternate until all grid elements in the current row and column are already selected, at which point the game ends and the player with the higher score wins.

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?