Unit 3: Pseudopolynomial Algorithms

This unit covers

• Pseudopolynomial algorithms
• The DP algorithm for Knapsack
• Strong NP-hardness

Material

• slides

• lecture notes

• Knapsack DP

• Further Pseudopolynomial DP Algorithms

• Video 3-1 · transcript (2026-10-22, 14:42): Pseudopolynomial algorithms
  
• Video 3-2 · transcript (2026-10-22, 7:07): Knapsack
  
• Video 3-3 · transcript (2026-10-26, 32:09): Knapsack DP solution
  
• Video 3-4 · transcript (2026-10-26, 24:10): Strong NP hardness
  

---

Unit 2  ⋅  Syllabus  ⋅  Unit 4