Description
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 i
th smallest
element) always, some-times, or never? Explain your answer.
1
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 maximize 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 function) 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
