Computer Science 385
Design and Analysis of Algorithms
Spring 2026, Siena University
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
- adversary argument
- problem reduction/transformation
- pairing problem
- Euclidean minimum spanning tree problem