Today we’ll spend a bit of time reviewing our proof of correctness from last time. Afterwards, we’ll start on our divide and conquer unit with this worksheet on QuickSelect.
Announcements for today:
- You have a tutorial quiz today.
- Assignment 3 will be released after tutorials, as usual, but unusually, this assignment is only for practice (because the normal deadline would have been the night before the midterm exam, which didn’t strike us as desirable). We strongly recommend you work through it as part of your exam preparation and put as much effort into it as you would an actual assignment.
- Assignment 1 grades have been released on Gradescope. If you wish to submit a regrade request, please read our policy on regrade requests first. (In particular: read the sample solution before you dispute your grade!)
- Your reading quiz on divide and conquer is due Thursday night. (Yes, this is after we will have started on the unit in class; the alternative was having a reading quiz and assignment due at the same time!)
Here are today’s clicker questions and the slides reviewing the proof of correctness of our greedy clustering algorithm.