Problem 1 (15pts)
Do problem 13-4 (a) and (b) on page 333 in CLRS. Justify your answer.
Problem 2 (10pts)
Consider the code for Randomized-Selection on page 216 in CLRS. Support someone carelessly implemented the code, but omitted the “-1” on line 8, that it typing q instead of q - 1.
Does the corrupted code still work (that is, correctly find the ith smallest element) always, some-times, or never? Explain your answer.
Problem 3 (25pts)
Coins of various values are placed on the cells of an n × m chess board. Let the upper left corner cell be (1, 1) and the lower right cell be (n, m); cell (i, j) has coins valued at cij . A robot starts at cell (1, 1) and can move only to the right or down on the board.
1. Give a dynamic programming algorithm expressed recursively without memoization to determine the path the robot should follow to maxi-mize the total value of the coins collected as the robot wanders on the board from cell (1, 1) to cell (n, m). Analyze the time required and give corresponding pseudocode.
2. Give the algorithm iteratively with memoization. Analyze the time required and give corresponding pseudocode
Problem 4 (25pts)
We are given a sequence of n numbers, a1, a2, ··· , an and want to find the longest increasing subsequence (LIS); that is, we want to find indices i1 < i2 < ··· < im such that aij < aij +1 and m is as large as possible. For example, given the sequence 5, 2, 8, 6, 3, 6, 9, 7 we have an increasing subsequence 2, 3, 6, 9 and there is no longer increasing subsequence.
1. Give a recursive dynamic programming recurrence (just give the func-tion) for the LIS of a sequence a1, a2, ··· , an. (Hint : Let Li be the length of the LIS in a1, a2, ··· , ai , let Ai be index of the smallest possible largest element in that increasing subsequence, and let Bi be
index of the second-largest element in that increasing subsequence. Express Li recursively. You may assume a dummy element a0 = −∞)
2. Give the algorithm iteratively with memoization. Analyze the time required and give corresponding pseudocode.
2
