4 ms·

Dynamic programming practice problems

87 points by seshagiric 17y ago

jules 17y ago
No longest common subsequence? Try that and then make it use O(n) memory instead of the O(n^2) of the simple dynamic programming algorithm.
- baddox 17y ago
  Maybe that and rod-cutting were left out because their solutions are in all the books. How do you get it to use O(n) space? I remember the simple solution was to build a matrix bottom-up, the matrix of course being of size n^2. Do you get constant space just by throwing away non-optimal subproblems and adding a predecessor field to each node (a node being an individual letter)?
  - kmak 17y ago
    Typically the way that optimization is you only need the subproblem solution from the previous row, so the rows before that you can ignore (and thrown away) by keeping only 2n entries. This assumes you don't need to reconstruct the path though.
  - jules 17y ago
    Yes, something like that. With the standard algorithm you compute a matix where each entry (i,j) in the matrix gets computed from entries (i-1,j),(i,j-1),(i-1,j-1). If you compute the matrix row-by-row then you only need to store two rows, because the next row only depends on the current row. You can reduce the cost from storing two rows (2n entries) to one row (n entries) by rewriting it in-place. You're right that you'd store the solution string in a linked list, because they have O(1) non-destructive append. Or maybe there's another smarter and faster scheme than a linked list? Edit: oh, you could just use an array for each column, and append the letter in-place. Or does this use more space because the prefixes are not shared among the different columns?
ecommando 17y ago
Good God Man. Get a microphone that costs more than $2, or edit your audio after your record it. There's WAY too much static. Also, give Mr. Roboto a valium so he loosens up. ;-)
- tl 17y ago
  I'm not sure why this is being downvoted. The flash that the article links to explaining the integer knapsack problem sounds horrible.
  - Qz 17y ago
    Maybe the downvotes are for the second comment.
kudzoo 17y ago
Those problems were recorded by Brian Dean, he's now a prof at Clemson University http://www.cs.clemson.edu/~bcdean/ http://www.cs.clemson.edu/~bcdean/ He's a fantastic teacher and actually made good use of his tablet pc to help with teaching. If he didn't have time to finish a proof in class, he would email us a flash movie recording of the full proof and he also graded our homeworks in the same way. We'd get back a flash movie containing our typeset submission and he'd comment on each solution and sketch out any improvements or fixes. It was really fun to get feedback like that.
- seshagiric 17y ago
  Thanks for pointing it out.

87 points by seshagiric 17y ago

jules 17y ago

No longest common subsequence? Try that and then make it use O(n) memory instead of the O(n^2) of the simple dynamic programming algorithm.

baddox 17y ago
Maybe that and rod-cutting were left out because their solutions are in all the books. How do you get it to use O(n) space? I remember the simple solution was to build a matrix bottom-up, the matrix of course being of size n^2. Do you get constant space just by throwing away non-optimal subproblems and adding a predecessor field to each node (a node being an individual letter)?
- kmak 17y ago
  Typically the way that optimization is you only need the subproblem solution from the previous row, so the rows before that you can ignore (and thrown away) by keeping only 2n entries. This assumes you don't need to reconstruct the path though.
- jules 17y ago
  Yes, something like that. With the standard algorithm you compute a matix where each entry (i,j) in the matrix gets computed from entries (i-1,j),(i,j-1),(i-1,j-1). If you compute the matrix row-by-row then you only need to store two rows, because the next row only depends on the current row. You can reduce the cost from storing two rows (2n entries) to one row (n entries) by rewriting it in-place. You're right that you'd store the solution string in a linked list, because they have O(1) non-destructive append. Or maybe there's another smarter and faster scheme than a linked list? Edit: oh, you could just use an array for each column, and append the letter in-place. Or does this use more space because the prefixes are not shared among the different columns?

ecommando 17y ago

Good God Man. Get a microphone that costs more than $2, or edit your audio after your record it. There's WAY too much static. Also, give Mr. Roboto a valium so he loosens up. ;-)

tl 17y ago
I'm not sure why this is being downvoted. The flash that the article links to explaining the integer knapsack problem sounds horrible.
- Qz 17y ago
  Maybe the downvotes are for the second comment.

kudzoo 17y ago

Those problems were recorded by Brian Dean, he's now a prof at Clemson University http://www.cs.clemson.edu/~bcdean/ http://www.cs.clemson.edu/~bcdean/ He's a fantastic teacher and actually made good use of his tablet pc to help with teaching. If he didn't have time to finish a proof in class, he would email us a flash movie recording of the full proof and he also graded our homeworks in the same way. We'd get back a flash movie containing our typeset submission and he'd comment on each solution and sketch out any improvements or fixes. It was really fun to get feedback like that.

seshagiric 17y ago
Thanks for pointing it out.