CS161 Class Schedule for Winter Quarter '01-'02
|
Tuesday
|
Thursday
|
|
Assignments in CLR (1st edition)
|
Assignments in CLRS (2nd edition)
|
|
April 2
|
April 4
|
| Administrivia. Introduction: models of computation, O-notation. Reading: Section 1.1, Chapter 2. Section 1.1, Chapter 3. | Insertion sort and mergesort, divide and conquer, recurrences. Reading: Sections 1.2-3, Section 4.1. Section 1.2, Chapter 2, Section 4.1. |
|
April 9
|
April 11
|
| Quicksort, Strassens' algorithm, more on summation and recurrences. Reading: Section 8.1-2, 31.2. Sections 4.2-3. (Chapter 3 should be read as needed during the quarter). Section 7.1-2, 28.2, Sections 4.2-3. | Randomized algorithms: randomized quicksort, probability. Reading: Sections 6.1-3, 8.3-4. (Chapter 5 should be read as needed during the quarter.) Chapter 5, Sections 7.3-4. |
|
April 16
|
April 18
|
| Sorting: median order statistics. Reading: Chapter 10. Chapter 9. | Sorting: heapsort, priority queues, set manipulation. Reading: Chapter 7. Chapter 6. |
|
April 23
|
April 25
|
| Sorting: lower bounds, counting sort, radix sort. Reading: Chapter 9. Chapter 8. | Data structures: hashing, collision resolution, chaining, universal hashing, open addressing. Reading: Chapter 12. Chapter 11. |
|
April 30
|
May 2
|
| Data structures: binary search trees, tree walks, relation to quicksort. Reading: Chapter 13. Chapter 12. | Data structures: red-black trees, rotations, insertion, deletion. Reading: Chapter 14. Chapter 13. |
|
May 7
|
May 9
|
| Midterm examination, in class, closed book. | Augmenting data structures: dynamic order statistics, interval trees. Programming problem handed out. Reading: Chapter 15. Chapter 14. |
|
May 14
|
May 16
|
| Dynamic programming: optimal binary search trees, longest common subsequence. Reading: Chapter 16. Chapter 15. | Greedy algorithms: activity selection. Introduction to graph algorithms: representation, breadth first search. Reading: Section 17.1-3, 23.1-2. Section 16.1-3, 22.1-2. |
|
May 21
|
May 23
|
| Greedy algorithms: Minimum spanning tree algorithms, Prim's algorithm, Kruskal's algorithm. Reading: Chapter 24. Chapter 23. | Greedy algorithms: depth first search, topological sort. Reading: Chapter 23.3-4. Chapter 22.3-4. |
|
May 28
|
May 30
|
| Graph algorithms: Single-source shortest paths, Dijkstra's algorithm, Bellman-Ford Algorithm, difference constraints. Reading Chapter 25. Chapter 24. | Graph algorithms: all-pairs shortest paths, matrix multiplication, Floyd-Warshall algorithm. Reading: Chapter 26. Chapter 25. |
|
June 4
|
June 6
|
| Flow networks; the Ford-Fulkerson algorithm; Bipartite matching. Reading: Chapter 27. Chapter 26. Programming problem due. All homeworks due by this date. |
Special end-of-class lecture. Reading: None. Course evaluation. |