Lecture 34

Lecture 34: Limitations of Algorithms
Date: Monday, April 22, 2024

Agenda

Announcements
- Problem Set 7: [PDF] due Wednesday
- Lab 10: Backtracking wrap up before Wednesday's lab
- Please come by to get any other missing labs taken care of
Please complete course evals
- bonus opportunity for sufficient participation rate: one point across the board on all final average cutoffs if we get over 90% on the lecture evals (not lab)
Final exam info
- Wednesday 5/1, 4-6 PM
- guide and practice questions out
- review time Tuesday 4/30? Morning of 5/1?
Quiz 3 redo, quick recap
Problem Set 6: [PDF] quick recap
Limitations of Algorithms
- lower bounds
  - finishing up decision tree examples
  - adversary arguments
  - problem reduction

Terminology