| Assigned: | Tuesday, November 8 |
| Due: | Monday, November 21, 11:59pm |
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.
The algorithm is simple but is probably not one that you would intuitively find.
It is crucial that you follow guidelines to stay out of the swamp.
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.
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 powerful algorithm design technique called dynamic programming.
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. (We will see that most of the computation has already been done, and only a small update needs to be made.)
Let's illustrate with list [3, 5, 4, 8, 2, 9, 6]. Term bis abbreviates 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:
if a change to an existing bis is made, only one of the bis's needs to be changed, or
all current bis's 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].
Try to find the last currently stored bis L that ends on a value that
is less than x, if there is one, and let
| 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] and
There is not always any suitable list L. If no suitable 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].
Now suppose that L is found in step 1.
Notice that, if there is a length
Create a new list Q by adding x to the end of L.
Store list Q as the new bis of length
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.
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.
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).
Notice that constraints 1 and 2 indicate that the list of mountains to climb must be ordered simulataneously by two different orderings.
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. 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. Follow these guidelines. You will need to work out how to break your program 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, not the elevations. For example, refer to mountain mountains[2] as 2. You can get the elevations and names by looking in the array. |
2. Computing Longest Increasing SublistsKeep one array of linked lists to store the bis's. Initially, make all of the lists NULL. Also keep the length of the longest bis sequence that is currently stored. (It will initially be 0. Notice that an empty list (NULL) is stored at index 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 list) 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. You would do well to write a function, lowerElevation(i, j), that returns true if mountains[i] has a lower elevation than mountains[j]. 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 is stored as [2,0] since
|
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. Be sure to initialize the reference count. You will want a function, incref(c), that adds 1 to the reference count of cell c, and a function decref(c) that subtracts 1 from c's reference count. Be very sure to increase the reference count of a cell when you create a pointer to it. You will want a cons function for adding a value to the beginning of a list. That function stores a pointer to a list cell. Don't forget to increase that cell's reference count. This will require some discipline. |
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. Create a global flag (a boolean variable) that is used to control deletion. Put a test at the point where you delete a cell (in decref) so that you can turn off deletion. ' For example, write
if(deleting)
{
delete cell;
}
If you think your reference count management is causing
troubles, try turning off deletion.
|
5. Handling Each MountainI strongly recommend a separate function to find the length of the bis that needs to be extended. Be careful to remember that the mountain that you are considering might be the lowest one seen so far. |
6. Show the SolutionWrite a function that shows the mountains in the longest bis. Remember that the list is backwards. You need to show the mountains in increasing order of elevation (and in forward order according to the book). |
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. 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.
Also document defined types clearly.
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.)
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. Instead, make a function holding the code and call it twice.
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/2530/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/2530/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 24 hours after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.