Today we’ll finish up our worksheet on divide and conquer and talk about a cool variant of the QuickSelect algorithm with better theoretical performance guarantees. We also have a handout on the Master Theorem.
Announcements for today:
- Assignment 3 is up on the course webpage. This one is just practice for the midterm exam and won’t be for submission. We’ll release solutions on Sunday morning.
- Tutorials today will be about proofs on 320 exams. The proof questions we ask on exams tend to be structured a bit differently from the ones we ask on assignments (though they obviously deal with the same kinds of concepts). Tutorials today will work through some examples.
- Your first reading quiz on dynamic programming is due on Sunday night.
Here are today’s clicker questions, along with PDF versions of today’s Jupyter notebooks on how to select the pivot, and Steve Wolfman’s more elaborate and complete notebook on the actual algorithm. UBC Blogs does not allow upload of .ipynb files, so the actual notebooks can be downloaded on Piazza.