Computer Science 3300
Fall 2015
Section 001
Programming Assignment 7

Table of contents

1. Longest increasing sublists
2. An algorithm to compute longest increasing subsequences
3. The assignment
4. Compiling, linking and running
5. Suggestions and additional requirements
6. Submitting your work

Longest increasing sublists

---

Suppose that s is a list of values. A sublist 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 sublists of s. Notice that the members of a sublist are not required to contigous in the original list.

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

There can be more than one longest increasing sublist 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 sublists, and we are only interested in finding one of them.

An algorithm to compute longest increasing subsequences

---

Naive approaches to finding longest increasing sublists 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 sublist of length k is an increasing sublist 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 sublist 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 sublist of length 3.)

Our algorithm does a scan of s, looking at longer and longer prefixes of s, until it has looked at the entire list. For each prefix of s, the algorithm computes a best increasing sublist 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 sublist.

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

The assignment

---

Claude is a mountain climber. He has a book of mountains; each mountain has a name and an elevation (an integer). He wants to climb some of the mountains listed in the book, with the following requirements.

1. He wants to climb mountains in increasing order of elevation.

2. He wants to climb mountains in the same order in which they are listed in the book (which is not necessarily in increasing order by elevation).

3. He wants to climb as many mountains as possible, subject to requirements (1) and (2).

Input format

The input has one line for each entry in the book, in the same order as the book. Each line contains a mountain name and an elevation. The mountain name is a string that does not contain any spaces and the the elevation is an integer. For example, the input might be as follows.

Eiger            3970
Everest          8848
Denali           5500
Fuji             3776
GangkharPuensum  7570
K2               8611
Kilamanjaro      5895
Matterhorn       4478
Olympus          2917
Tocopuri         5808
Tupungato        6570
Whitney          4421

Note. The input ends at the end of the file.

• You can test for end-of-file in your program using feof(stdin), which is true if there has been a previous attempt to read beyond the end of the file. Be careful to test this after trying to read something.

• The recommended way to send information to the program is to redirect the standard input to a file. If you choose to type the information yourself, type a control-D at the end. That causes the terminal to send an end-of-file signal to the program.

Output format

List the mountains to climb, in order, giving each in a format similar to the input. For example, the output might be as follows.

Fuji             3776
Matterhorn       4478
Tocopuri         5808
Tupungato        6570

Compiling, linking and running

---

Call your program lis.cpp. A Makefile is provided for you. You can use the following commands with it.

make lis

Just compile lis.cpp, if necessary, to create executable file lis.

make test

Do make lis then run it.

make debug

Do make lis then run it via the gdb debugger.

make clean

Remove all machine-generated files.

Suggestions and additional requirements

---

1. As always, follow the coding standards. Do not forget about them. Use the template for each file. Call your program lis.cpp.

2. Store the mountain names and elevations in an array of structures. While solving the longest increasing sublist problem, store the indices of the mountains in that array, not the elevations. You can get the elevations by looking in the array.

3. Store an array of bis lists. Initially, make all of the lists NULL. Also store the length of the longest bis sequence that is currently stored. (It will initially be 0.)

4. Follow the longest increasing sublist algorithm above. But store each bis as a linked list backwards, so that the number that you are interested in (the last member of the forward sequence) is at the beginning of the backward list. Also, remember to store the mountain indices, not the elevations, in these lists. When you are comparing values, compare the elevations, not the indices.

   Using the above example input, after looking at the first four mountains,

   Eiger            3970
   Everest          8848
   Denali           5500
   Fuji             3776
   

   the best sequence of length 2, written in forward notation and using mountain names, is [Eiger, Denali]. You replace each mountain by its index in the input(say, numbering from 0), so the forward list becomes [0, 3]. Since you store the bis backwards, you will see [3, 0] in your array of bis lists.

5. You do not need to copy a bis list to extend it. Just add the new value to the beginning of the linked list, and use memory sharing. Remember that the lists are stored backwards, so adding a value to the end of the forward list is the same as adding it to the beginning of the backward list.

6. Go through mountain indices in order. To find out where to modify the array of bis's, search backwards from the length of the longest bis sequence. Be careful to remember that the mountain that you are considering might be the lowest one seen so far.

7. When you are done, show the mountains in the longest bis list in reverse order.

Submitting your work

---

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

  ~abrahamsonk/3300/bin/submit 7 lis.cpp

Command

  ~abrahamsonk/3300/bin/submit 7

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.