| Part 1 (Seg 12) | |
|---|---|
| Class 1: 02/01/25 |
Intro to divide-and-conquer.
Finding min and max with less than 2n-2 comparisons. |
| Class 2: 06/01/25 |
Finding min and max using 3n/2 comparisons.
Review of asymptotic notation. Merge Sort and its analysis using recursion tree method. Master theorem. |
| Class 3: 09/01/25 |
Recap of master theorem and caveats.
The stock buy-and-sell problem using divide-and-conquer. Brief history of integer multiplication. |
| Class 4: 13/01/25 |
Karatsuba's algorithm for integer multiplication.
Lower bound of Omega(n log n) for sorting using comparisons. |
| Class 5: 16/01/25 | Selection algorithm assuming algorithms that can find an exact/approximate median. |
| Class 6: 20/01/25 |
Selection algorithm using median of medians.
Recurrences of the form T(n)=T(an)+T(bn)+O(n). Randomized selection. |
| Class 7: 23/01/25 |
Quick Sort Practice problems |
| Class 8: 27/01/25 |
Linear time sorting: Count sort and radix sort
Discussion of practice problems |
| Class 9: 30/01/25 | |
| Part 2 (Seg 34) |
|---|
| Part 3 (Seg 56) |
|---|