CMSC-641 Algorithms: Special Problem-Fredman (fall 99)

CMSC-641 Algorithms Special Problem-Fredman (fall 99)

Problem: Fredman's Algorithm

This problem deals with Fredman's Algorithm for computing the length of any longest increasing subsequence (see handout). We shall use the abbreviations ISS (increasing subsequnce) and LISS (longest increasing subsequence). For each i, let r_i and s_i be the values of r and s, respectively, during the ith iteration of the main loop.

(a) Is it always true that, when Fredman's Algorithm terminates, the work array W holds a LISS of K[1..n]? Prove your answer.

(b) Prove that Fredman's Algorithm satisfies each of the following three loop invariants:
W is tightly packed; W is increasing; and for every 1 <= j <= r_i,
W[j] = min {last( \sigma ) : \sigma is an ISS of K[1..i] of length j.}
Hint: Use induction.

(d) Explain how to implement Lines 5 and 9 efficiently, and analyze their time complexities.

(e) What is the worst-cast running time of Fredman's Algorithm? Express your answer in terms of n and L, where L is the output of the algorithm. Justify your answer.

(f) What is the worst-case running time of Fredman's Algorithm? Express your answer in terms of n only.
Hint: What value of L maximizes your answer to Part (e)? Justify your answer.

(g) Can you modify Fredman's Algorithm so that it also computes a description of a LISS in addition to its length? If so, give pseudocode for your modifications and for any needed separate recovery algorithms. Keep your modifications to Fredman's Algorithm as simple as possible.