Computer Science 2530
Spring 2017
Programming Assignment 7

Table of Contents

1. Purpose of this assignment
2. Longest increasing sublists
3. An algorithm to compute longest increasing sublists
4. Storing lists backwards
5. The assignment
6. Compiling, linking and running
7. Suggestions and additional requirements
8. Memory sharing and reference counts
9. Things to watch out for
10. Submitting your work
11. Asking questions

Purpose of This Assignment

---

This assignment involves linked lists with memory sharing. It also requires you to develop your program with less hand holding. You will need to draw pictures and think things out.

Because you have more flexibility in the design of this program, you are not required to follow the design precisely. But use it as advice.

An algorithm is described here, and you are required to use that algorithm. Do not invent a new algorithm. It is fairly simple but is probably not one that you would intuitively find.

It is crucial that you follow guidelines. Stay out of the swamp.

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 contiguous in the original list. ("Contiguous" means without gaps.)

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 a 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 Sublists

---

Naive approaches to finding longest increasing sublists do not work. In order to get an algorithm that works for every list, we employ a powerful algorithm design technique called dynamic programming.

Best increasing sublists

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]. A best increasing sublist of s of length 2 is [3, 4].

An example illustrating the algorithm

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. It stores them all so that, when the length of the prefix is increased by adding one value, updating the information is easy.

Let's illustrate with list [3, 5, 4, 8, 2, 9, 6]. Term bis abbreviates best increasing sublist.

Observe that, each time the prefix length is increased by one

1. Sometimes, one of the existing bis's needs to be changed. But you never need to change more than one bis.

Sometimes, none of the existing bis's needs to be changed. In that case, a new bis is added to the end, increasing the maximum bis length.

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.

Determining how to do an update to the bis array

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. Try to find the longest currently stored bis B that ends on a value that is less than x, if there is one, and let be its length. For example, we are adding 4, and the currently stored bis's are

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

   The longest stored bis that ends on a value that is less than 4 is [3], of length 1. So B = [3] and is 1.

   
   

   If none of the stored bis's end on a value that is less than x, then B = [ ] and = 0.

   
   

2. Create a new list Q by adding x to the end of B. Store list Q as the new bis of length +1. If we already had a bis of length +1, list Q replaces it. If we did not already have one, then list Q is added as a new bis of length +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. That bis is a longest increasing sublist.

The algorithm does not need to store the prefix explicitly. All the algorithm needs at a given step is the new value x that is being added to the prefix. So it just does a loop, looking at each value in the original sequence.

Storing Lists Backwards

The algorithm actually stores all of the bis's backwards. There is a big advantage to doing that. When lists are stored in forward order, you update a list by adding a value to the end of a list. That is expensive. When bis's are stored backwards, you update a list by adding a value to its beginning. That is cheap.

Let's use bbis to mean a backwards bis. Here is the preceding example, [3, 5, 4, 8, 2, 9, 6], using bbis's.

The Assignment

---

Claude is a mountain climber. He has a book of mountains; each mountain has a name (a string) 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).

Notice that constraints 1 and 2 indicate that the list of mountains to climb must be ordered simulataneously by two different orderings.

Input format and source

The input is required to come from the standard input.

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 is no more than 50 characters long. 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. But remember that the program reads from the standard input. Do not make it read from a fixed file. I recommend that you redirect the standard input to a file. If you want to type in an input, type control-D for end-of-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.

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

Line up the names and the elevations in columns.

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

---

Read the following. Follow these guidelines.

You will need to work out how to break your program into sensible functions. Do not jump into coding. Work out the design first. What functions will you write? Keep them short and simple. Keep their jobs focused.

Memory Sharing and Reference Counts

---

Do not proceed to this part until your program is working. Make a copy of your program, so that, if you spoil it in this part, you still have a working copy.

You do not need to copy a bbis list to extend it. Just add the new value to the beginning of the linked list, using cons, or a constructor that plays the same role.

You find that you are using memory sharing. Memory sharing makes it tricky to know when you no longer need a list cell so that you can delete it.

To know when to delete a cell, store a reference count in each list cell. The reference count tells how many pointers are pointing to the list cell. Each time you create a pointer to a list cell, add 1 to that cell's reference count. Each time a pointer to a list cell is lost, for any reason, subtract 1 from that cell's reference count.

If the reference count becomes 0, you can delete the cell. (But remember that a cell contains a pointer to another cell, and that pointer is about to disappear. So deleting one cell involves decreasing the reference count on another cell, if the 'next' pointer is not NULL.)

  struct ListCell;

Things to Watch Out for

---

1. Call your program lis.cpp.

2. Choose a sensible design, with sensible functions that are short, simple and well motivated. Do not regress to the way you wrote programs before taking this course.

   You will lose points for poor designs.

3. Test your program on more than one input. In the past, many students have turned in programs that did not produce correct results. Be sure to choose one input that is in ascending order by elevation, so that the longest increasing sublist is the entire list.

4. Contracts are extremely important for this assignment. They explain your choice of functions. When I grade your program, I will read each function's contract to see what you intend for that function to do.

   In the past, students have lost a lot of points because of poor or missing contracts. If I cannot figure out what a given function is trying to do, I will not give you a good grade for that function.

   Make sure that each function does just what its contract says it does, no less and no more. Make sure that all requirements on the parameters are noted in the contract.

5. Also document defined types clearly.

6. This program is supposed to read its input from the standard input. Do not submit an assignment that reads from a file. (I am always perplexed when a student submits a program that reads from a fixed file that only exists on his or her computer.)

7. As always, follow the coding standards. Do not forget about them. Use the template.

8. Do not duplicate sections of code unnecessarily. Instead, make a function holding the code and call it twice.

9. Choose sensible names for types, functions and variables.

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/2530/bin/submit 7 lis.cpp

Command

  ~abrahamsonk/2530/bin/submit 7

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

Late Submissions

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

Asking questions

---

To ask a question about your program, first submit it, but use assignment name q7. For example, use command

  ~abrahamsonk/2530/bin/submit q7 lis.cpp