Trouble Understanding Dynammic Programming: Best Increasing Sublist
So for one of my assignments we've been told to find the BIS based of the users std input. The link to the assignment (along with the algorithm for BIS) can be found here - http://www.cs.ecu.edu/~karl/2530/fall16/Assn/Assn7/assn7.html.
I'm having trouble understanding the algorithm itself and would like some assistance understanding how it works in relation to the example input (also shown in the link) that the user enters. Thanks for any help in advance!
I'm having trouble understanding the algorithm itself and would like some assistance understanding how it works in relation to the example input (also shown in the link) that the user enters. Thanks for any help in advance!
closed account (9j2Cko23)
The site says : 404 Not found
The requested URL /~karl/2530/fall16/Assn/Assn7/assn7.html. was not found on this server.
The requested URL /~karl/2530/fall16/Assn/Assn7/assn7.html. was not found on this server.
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.
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.
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.
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. 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.
Phase 1. Definitions.
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.)
An example of how the algorithm employs the definitions
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]
k bis of length k
1 [3]
[3, 5]
k bis of length k
1 [3]
2 [3, 5]
[3, 5, 4]
k bis of length k
1 [3]
2 [3, 4]
[3, 5, 4, 8]
k bis of length k
1 [3]
2 [3, 4]
3 [3, 4, 8]
[3, 5, 4, 8, 2]
k bis of length k
1 [2]
2 [3, 4]
3 [3, 4, 8]
[3, 5, 4, 8, 2, 9]
k bis of length k
1 [2]
2 [3, 4]
3 [3, 4, 8]
4 [3, 4, 8, 9]
[3, 5, 4, 8, 2, 9, 6]
k bis of length k
1 [2]
2 [3, 4]
3 [3, 4, 6]
4 [3, 4, 8, 9]
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.
Phase 2: Determining how to do updates
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 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 last bis that ends on a value that is less than 4 is [3], of length 1. So L = [3] and is 1.
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 +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 +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 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.
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.
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. 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
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.
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.
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. 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.
Phase 1. Definitions.
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.)
An example of how the algorithm employs the definitions
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]
k bis of length k
1 [3]
[3, 5]
k bis of length k
1 [3]
2 [3, 5]
[3, 5, 4]
k bis of length k
1 [3]
2 [3, 4]
[3, 5, 4, 8]
k bis of length k
1 [3]
2 [3, 4]
3 [3, 4, 8]
[3, 5, 4, 8, 2]
k bis of length k
1 [2]
2 [3, 4]
3 [3, 4, 8]
[3, 5, 4, 8, 2, 9]
k bis of length k
1 [2]
2 [3, 4]
3 [3, 4, 8]
4 [3, 4, 8, 9]
[3, 5, 4, 8, 2, 9, 6]
k bis of length k
1 [2]
2 [3, 4]
3 [3, 4, 6]
4 [3, 4, 8, 9]
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.
Phase 2: Determining how to do updates
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 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 last bis that ends on a value that is less than 4 is [3], of length 1. So L = [3] and is 1.
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 +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 +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 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.
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.
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. 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
closed account (9j2Cko23)
The deadline is November 21th. It is even past the late submission. Even if you do it, your submission will be rejected and you will get a zero for sure.
closed account (9j2Cko23)
How do we help you with the assignment? Or someone will do the work for you perhaps?
op im also in Abrahamsons class did he really extend it, i didnt receive an email.
My program worked about 90% i had trouble with the first 2 mountains.
What are you having trouble with?
My program worked about 90% i had trouble with the first 2 mountains.
What are you having trouble with?
Yeah someone requested at the end of the last class to extend it. I pretty much don't understand the algorithm we're supposed to use to find the BIS, I've been getting pretty frustrated trying to figure it out lol.
do you have any code you could post? For the BIS you need to have an array of linked lists and you compare the elevations of the mountains BUT store their index in the linked list array.
Your supposed to compare the elevations and have a longestBIS that updates every time your list is extended. You find the index of the list to extend and do the insertion.
I was also frustrated bro lol i spent all last week, the weekend plus monday, tuesday working on it and mine didnt even work 100% (turned it in Tuesday night), im nose deep in the swamp.
Your supposed to compare the elevations and have a longestBIS that updates every time your list is extended. You find the index of the list to extend and do the insertion.
I was also frustrated bro lol i spent all last week, the weekend plus monday, tuesday working on it and mine didnt even work 100% (turned it in Tuesday night), im nose deep in the swamp.
@ace6208 Yes i had two, one for maxNumMountains and maxCharNum.
I emailed him and he told me to have those 2 as constant globals.
I emailed him and he told me to have those 2 as constant globals.
Have you seen the code for the assignment on ideone? Is yours pretty similar to that lol? https://ideone.com/yUPuAk
yea kinda of, did u test it and see if it works on the test file he gave us? You do get the position and insert it, that is how he explained it to me during office hours so it looks good
Wait did u find this shit online wtf???
Are u sure ur willing to risk it for that sweet sweet -50. And it was due monday so i assume u already turned it right
Wait did u find this shit online wtf???
Are u sure ur willing to risk it for that sweet sweet -50. And it was due monday so i assume u already turned it right
Topic archived. No new replies allowed.