Lecture 34

Lecture 34: Limitations of Algorithms: Problem Reduction
Date: Monday, April 27, 2026

Agenda

Announcements
- Academic Showcase Project wrapping up soon
  - session Friday 1:45-2:45 in RB 340 (no regular morning class)
  - submissions Monday
- Problem Set 6: [PDF] continues for another week, remember the deadline is firm
- lab as usual tomorrow
- almost to the RSVP deadline for the dinner/party next Monday - be there!
- Sample solutions for the final exam practice questions are posted outside my office for when you want to check your work
- Please complete course evals
  - you can help me and the rest of the CS faculty improve this course
  - offer: quarter point adjustment in grading thresholds if we get to 95% participation rate by the time the evals close
- All work submitted to date is graded and all grades are in Canvas: make sure it all looks accurate
Problem Set 5: [PDF] quick recap
Limitations of Algorithms
- lower bounds
  - adversary arguments (just a quick mention)
  - problem reduction

Terminology