Lecture 33

Lecture 33: Limitations of Algorithm Power: Problem Reductions
Date: Monday, April 15, 2019

Agenda

Announcements
- Problem Set 6: [PDF] due the day we get back from break (more on this in a minute)
- There will be no new lab this week as you wrap up Problem Set 6: [PDF] and continue work on the Academic Showcase Project: [HTML] [PDF]
- Lab 10: Greedy Algorithms and Backtracking is due at your final lab meeting, right after we get back from Easter break
- That last lab will be all pencil and paper
- One more short quiz to take place on our last class meeting day: doing a heapsport
- Only "online" office hours Tuesday in the morning, no office hours Wednesday
About course evaluations
- they're important!
- Everyone gets 15 quiz bonus points if we get 95% or better response rate
Final exam details
- Wednesday, May 1, 8:30-10:30 AM, but I will plan to be here early for anyone who wants to start and have some extra time
- You will be provided with all needed summation and log formulas, and you will be permitted up to three double-sided sheets of handwritten notes as a reference
- Exam is cumulative but there is a bit more of an emphasis on topics since Exam 2: backtracking and limitations of algorithm power
- Reviewing all labs and problem sets would be a good way to prepare
- Also: some practice problems (handout coming)
Problem Set 6: [PDF] tips and hints
Counting sort: a sort better than possible?
Problem reduction

Terminology