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

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 c_{ij} . A robot starts at cell (1, 1) and can move only to the right or down on the board.

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

- 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, a_{1}, a_{2}, ··· , a_{n} and want to find the longest increasing subsequence (LIS); that is, we want to find indices i_{1} < i_{2} < ··· < i_{m} such that a_{i}_{j} < a_{i}_{j} _{+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.

- Give a recursive dynamic programming recurrence (just give the func-tion) for the LIS of a sequence a
_{1}, a_{2}, ··· , a_{n}. (Hint : Let L_{i}be the length of the LIS in a_{1}, a_{2}, ··· , a_{i}, let A_{i}be index of the smallest possible largest element in that increasing subsequence, and let B_{i}be

index of the second-largest element in that increasing subsequence. Express L_{i} recursively. You may assume a dummy element a_{0} = −∞)

- Give the algorithm iteratively with memoization. Analyze the time required and give corresponding pseudocode.