Assigned: | Monday, March 28 |
Due: | Friday, April 8, 11:59pm |
This assignment involves linked lists with memory sharing. It also requires you to develop your program with less hand-holding.
The algorithm is simple but is not one that you would intuitively find.
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 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.
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.
Prefix | Bis's | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
[3] |
|
||||||||||
[3, 5] |
|
||||||||||
[3, 5, 4] |
|
||||||||||
[3, 5, 4, 8] |
|
||||||||||
[3, 5, 4, 8, 2] |
|
||||||||||
[3, 5, 4, 8, 2, 9] |
|
||||||||||
[3, 5, 4, 8, 2, 9, 6] |
|
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].
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].
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].
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.
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.
He wants to climb mountains in increasing order of elevation.
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).
He wants to climb as many mountains as possible, subject to requirements (1) and (2).
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.
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
Call your program lis.cpp. A Makefile is provided for you. You can use the following commands with it.
Read the following, then work out how to break it into sensible functions.
Suggestions and requirements |
---|
1. Storing the book of mountainsStore 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 and names by looking in the array. |
2. Computing Longest Increasing SublistsStore 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.) 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 3776the 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. |
3. Memory Sharing and Reference CountsYou do not need to copy a bis list to extend it. Just add the new value to the beginning of the (backwards) 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. Memory sharing makes it tricky to know when you no longer need a list cell so that you can delete it. To do that, 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. When you create a new list cell, set its reference count to 1. Then you don't need to add 1 to a reference count when you create the first pointer to a cell. |
4. Deleting list cellsWhen you subtract 1 from a cell's reference count, check if the reference count becomes 0. If so, delete the cell. Keep in mind that a list cell contains a pointer to another list cell. So when you delete cell c, you also need to subtract 1 from the reference count of c's next pointer. You will want to have a destructor for list
cells that takes the next pointer into account. Here is
a suggestion for the destructor.
Put a test at the point where you delete a cell (in dropref) so that you can turn off deletion. You can use a global variable to control deletion. For example, write if(deleting) { delete cell; }If you think your reference count management is causing troubles, try turning off deleting. |
5. Handling Each MountainGo through mountain indices in order in the array that represents the book. 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. I strongly recommend a separate function to find the position of the list that needs to be extended. Pay attention to the list of length 0 at index 0. |
6. Show the SolutionWhen you are done, show the mountains in the longest bis list in reverse order. |
Test your program on more than one input. In the past, many students have turned in programs that did not produce correct results.
Contracts are extremely important for this assignment. They explain your choice of functions. In the past, students have lost a lot of points because of poor or missing contracts.
Make sure that each function does just what its contract says it does, no less and no more.
This program is supposed to read its input from the standard input. Do not submit an assignment that reads from a file.
As always, follow the coding standards. Do not forget about them. Use the template for each file. Call your program lis.cpp.
Do not duplicate sections of code unnecessarily. Make a function.
Choose sensible names for types, functions and variables.
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
After submitting, you should receive confirmation that the
submission was successful. If you do not receive confirmation,
assume that the submission did not work.
Command
~abrahamsonk/3300/bin/submit 7
will show you what you have submitted for
assignment 7.
You can do repeated submissions. New submissions will replace old ones.
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.