| Date | Topics | ||
|---|---|---|---|
| 1 | Tuesday | 01/17/06 | No Lecture. |
| 2 | Thursday | 01/19/06 | Review of basic sorting algorithms: insertion sort, quick sort, merge sort and heap sort. |
| 3 | Tuesday | 01/24/06 | Worst case analysis of sorting algorithms. |
| 4 | Thursday | 01/26/06 | Average case analysis of insertion sort. |
| 5 | Tuesday | 01/31/06 | Average case analysis of quick sort. |
| 6 | Thursday | 02/02/06 | Pancake flipping problem. In-class assignment on the same. |
| 7 | Tuesday | 02/07/06 | Lower bounds on sorting. |
| 8 | Thursday | 02/09/06 | Lower bounds on sorting. |
| 9 | Tuesday | 02/14/06 | Counting Sort. |
| 10 | Thursday | 02/16/06 | Selection and Median Finding. |
| 11 | Tuesday | 02/21/06 | Analysis of recurrence relation for median finding. |
| 12 | Thursday | 02/23/06 | Heap Construction. |
| 13 | Tuesday | 02/28/06 | Sums of geometric series and analysis of heap construction. Brute-force algorithms for convex hull and closest pair of points. Read chapters 3 and 4 for next lecture. |
| 14 | Thursday | 03/02/06 | Closest pair of points (section 4.6) |
| 15 | Tuesday | 03/07/06 | Convex Hull (section 4.6) |
| 16 | Thursday | 03/09/06 | Skip Lists. Discussion about projects. |
| 17 | Tuesday | 03/21/06 | Elementary graph algorithms: depth first search, breadth first search, minimum spanning tree. |
| 18 | Thursday | 03/23/06 | Graph algorithms (leftovers from the last lecture). |
| 19 | Tuesday | 03/28/06 | Topological sort and finding strongly connected components. |
| 20 | Thursday | 03/30/06 | Finding permutations and subsets |