Unit 3: Pseudopolynomial Algorithms

This unit covers

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

Material

• slides

• lecture notes

• Video 3-1 (2025-05-13): Pseudopolynomial algorithms

• Video 3-2 (2025-05-13): Knapsack

• Video 3-3 (2025-05-13): Strong NP-hardness

---

Unit 2  ⋅  Syllabus  ⋅  Unit 4