We’ll continue with our notes on divide-and-conquer (maybe even conquer them!) and perhaps do some live coding.
- Here again is a sample solution to the d-and-c notes.
- QuickSelect is an awesome and practical algorithm. It turns out, surprisingly, that we can also make a deterministic linear-time selection algorithm. If we get time, we may work through code for linear-time DeterministicSelect in class. (Here’s the Jupyter Notebook for that code.)
- Before class next time, read Section 6.1 and complete the pre-reading quiz due Tue at 10PM.
- There is a tutorial quiz this week (the week after mid-term break).
- Don’t forget to read sections 5.3 and 5.4 plus the Master Theorem entry on Wikipedia. They’re not on the pre-class quiz, but they are tremendously important (and easy for us to assess!).