LAS, Subset Sum and Knapsack

Go to:
> Material
> Lecture Recap

Material

• Slides: pre-class (w.o. solutions)
• Slides: with solutions & annotations
• Code:
  • partitionProblem - problem statement, Java CodeExpert template & test-cases
    • Copy the contents of the Main, custom.in and custom.out files into the corresponding files of the ”Welcome” exercise. You can run the tests by using the play button (not the flask).
  • solution

Lecture Recap

This week we introduced three new DP problems and tried to put them into buckets based on their structure.

DP “Archetypes”

First, we divided the problems so far into three families based on their structure:

• Sequential Decision: Building an optimal solution in a single sequence (e.g., Longest Ascending Subsequence), either demanding contiguous solutions or allowing discontiguous ones.
• Sequence Alignment: Comparing two sequences element-by-element (e.g., LCS, Edit Distance).
• Bounded Resource: Selecting an optimal subset of items under a constraint (e.g., Knapsack, Subset Sum).

LAS, Subset Sum, Knapsack

We saw three new DP problems and analyzed them under this lense:

• Longest Ascending Subsequence (LAS): We saw how this problem can be optimized from an $O(n^2)$ to an $O(n \log n)$ solution.
• Subset Sum & 0/1 Knapsack: These “Bounded Resource” problems have pseudo-polynomial runtimes (like $O(nb)$ or $O(nW)$) because they depend on the value of the input, not just its size.
• Knapsack FPTAS: Since Knapsack is NP-complete, we saw a Fully Polynomial Time Approximation Scheme (FPTAS) to find a $(1-\epsilon)$-approximate solution in polynomial time.

Finally, we solved the Partition problem and practiced how to reduce the problem to a simple subset sum, where we cleverly extract our solution. You can try your own implementation using the code and test-cases above on CodeExpert.

Like I already mentioned last week, DP takes quite some practice to get familiar with. I would recommend:

• seeing many types of problems,
• drawing the analogies (like our archetypes!),
• and practicing implementations (CodeExpert, LeetCode).

To practice DP, I can recommend the following list of LeetCode problems. If you find some time on your hands, I would already start early and for each problem briefly think it through on paper (like we did in class) and test the solution on LeetCode (you can sign up for a free account).