Computer Science 3200
Fall 2015
Section 001
Programming Assignment 4

Table of contents

1. Longest increasing subsequences
2. An algorithm to compute longest increasing subsequences
3. The assignment
4. Methods and a development plan
5. Additional requirements
6. Submitting your work

Longest increasing subsequences

---

Suppose that s is a list of values. A subsequence of s is a list that you can obtain by removing zero or more values from s. You cannot reorder values. For example, if s is [3, 5, 4, 8, 2, 9, 6] then [3, 5], [4, 2, 9] and [3, 4, 8, 9] are all subsequences of s. Notice that the values in a subsequence are not required to be contiguous in the original list.

An increasing subsequence of s is a subsequence of s that is in strictly ascending order. A longest increasing subsequence of s is an increasing subsequence of s that has the greatest length among all increasing subsequences of s. For example, if s is [3, 5, 4, 8, 2, 9, 6] then the longest increasing subsequence of s is [3, 4, 8, 9].

There can be more than one longest increasing subsequence of a list. For example, [3, 5, 8, 9] is also a longest increasing subsequence of [3, 5, 4, 8, 2, 9, 6]. They are considered equally good longest increasing subsequences, and we are only interested in finding one of them.

An algorithm to compute longest increasing subsequences

---

Naive approaches to finding longest increasing subsequences do not work. You can try them, but you will find that there are some lists on which they give the wrong answer. In order to get an algorithm that works for every list, we employ a general technique called dynamic programming.

For an integer k and list s, say that a best increasing subsequence of length k is an increasing subsequence of s having length k that ends on the smallest possible value. For example, if s is [3, 5, 4, 8, 2, 9, 6] then a best increasing subsequence of s of length 1 is [2], of length 2 is [3, 4], and of length 3 is [3, 4, 6]. (List [3,5,6] is also a best increasing subsequence of length 3.)

Our algorithm performs a scan of s, looking at longer and longer prefixes of s, until it has looked at the entire sequence. For each prefix of s, our algorithm computes a best increasing subsequence of each length from 1 to the longest achievable length. Let's illustrate with list [3, 5, 4, 8, 2, 9, 6]. We use bis to abbreviate best increasing subsequence.

Observe that, each time the prefix length is increased by one, only one of the bis's needs to be changed, or all are left the same and one new one is added at the end. Also notice that the last values in the bis's strictly increase as the length k increases. For example, in the last row of the table, for prefix [3, 5, 4, 8, 2, 9, 6], the last members of the bis's are 2, 4, 6, 9, in that order. That must always be the case.

It is easy to find out what needs to be done. When adding new value x to the end of the current prefix of s, do the following. We illustrate for adding 4 to prefix [3, 5] to get new prefix [3, 5, 4].

1. Find the last currently stored bis L that ends on a value that is less than x, if there is one. For example, we are adding 4, and the currently stored bis's are

   k	bis of length k
   1	[3]
   2	[3, 5]

   The last bis that ends on a value that is less than 4 is [3], of length 1. So L = [3].
   
   

2. If no such bis is found, then x must be less than the last values in all of the current bis's. Replace the length 1 bis by [x].

   
   

3. Suppose that L is found in step 1. Notice that, if there is a length k+1 bis stored, then it must end on either x or a value that is larger than x, since we selected the last sequence whose last member is less than x.

   Create a new list Q by adding x to the end of L. Store list Q as the new bis of length k+1. If we already had a bis of length k+1, list Q replaces it. If we did not already have one, then list Q is added as a new bis of length k+1.

   
   

The algorithm goes through all of the prefixes until it has reached the entire list. Then it selects the bis of the longest length from the collection of stored bis's. It is a longest increasing subsequence.

The assignment

---

Your program should read (1) and integer n, followed by (2) a sequence of n positive integers from the standard input. The integers can be on one line, but are not required to be on one line. It should write a longest increasing subsequence of that sequence on the standard output, one integer per line.

For example, on input

7 3 5 4 8 2 9 6

3
4
8
9

Methods and a development plan

---

Break your program up into static methods as follows.

1. Use the linked list class provided. Read the class to see what it provides.

2. Your main function should read the first integer n and create an array of n+1 Lists. Also create a variable longest that holds the length of the longest best-increasing-subsequence that you have found so far. (What should longest be before you have looked at any values in the input sequence?)

   If your array of lists is called best, then, for k = 1, …, longest, best[k] will hold the reversal of a best increasing subsequence of length k of that part of the input sequence that you have read. Make best[0] hold an empty list (null).

   You store lists in reverse order so that the last value in the sequence that you are remembering is the first value in its reversal.

3. Method findBis(best, longest, v) takes the array of lists, best, the value of variable longest, and a value v that is a newly read value. It searches from longest back toward 1 until it finds a list best[k] that begins with a value that is less than v. (Since the lists are stored in reverse order, this represents an increasing subsequence that ends on a value that is less than v.) If such a value of k is found, findBis returns that k. If there is no such k (because best[1] starts with a value that is ≥ k) then findBis should return 0.

4. Method updateBis(best, longest, v) takes care of updating the best array when new value v has been read from the input sequence. It uses findBis to find a value k. It sets best[k+1] = List.cons(v, best[k]), so that it adds v to the beginning of the shorter sequence, as was done in the example above.

   Make updateBis return the new value for longest. If k < longest, then the length of the longest bis does not change. If k = longest, then a new longest sequence has been addded to the array.

5. Method computeBis(best, n, s) should take the array best, the number n that was the first number in the input, and an open Scanner object s. It should successively read n integers from s and perform an update of the best array (using updateBis). After all n values have been read, it returns the reversal of the longest list in best. (Where is the longest list?)

6. Method showBis(x) should write the values in list x, one per line.

7. The main method should create a scanner to read from the standard input. It should read n and create the best array. Then it computes the final best array (using computeBis) and shows it (using showBis).

Additional requirements

---

Call your program lis.java.

As always, follow the coding standards. Do not forget about them. Use the template as a starting point.

Submitting your work

---

To turn in your work, log into the Linux system, change your directory for the one for assignment 4, and use the following command.

  ~abrahamsonk/3200/bin/submit 4 lis.java

Command

  ~abrahamsonk/3200/bin/submit 4

You can do repeated submissions. New submissions will replace old ones.

Late submissions

Late submissions will be accepted for one day after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.