Unit 3: Pseudopolynomial Algorithms

This is an archived version of this module from Summer 2025.
Click here for the current iteration.

This unit covers

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

Material

• slides

• lecture notes

• Video 3-1 (2025-05-13, 13:58): Pseudopolynomial algorithms
  
• Video 3-2 (2025-05-13, 11:55): Knapsack
  
• Video 3-3 (2025-05-13, 8:08): Strong NP-hardness
  

---

Unit 2  ⋅  Syllabus  ⋅  Unit 4