CS161 Class Schedule for Winter Quarter '15-'16
|
Monday
|
Wednesday
|
|
January 4
|
January 6
|
|
Administrivia. Introduction: models of computation, algorithms. Insertion sort, mergesort and their analysis. Reading: Chapters 1, 2. |
O-notation, growth of functions. Divide and conquer, recurrences. Reading: Chapters 3, 4. |
|
January 11
|
January 13
|
|
More on recurrences, the master theorem. Probabilistic analysis, randomized algorithms. Reading: Chapters 4, 5. |
Quicksort and randomized quicksort. Reading: Chapter 7. Homework 1 out. |
|
January 18
|
January 20
|
|
[No class – Martin Luther King day holiday] |
Selection: medians, order statistics. Reading: Chapter 9. Homework 1 due. Homework 2 out. |
|
January 25
|
January 27 |
|
Sorting: heapsort, priority queues. Reading: Chapter 6. |
Sorting: lower bounds, counting sort, radix sort. Reading: Chapter 8. Homework 2 due. Homework 3 out. |
|
February 1
|
February 3
|
|
Data structures: hashing, collision resolution, chaining, universal hashing, open addressing. Reading: Chapter 11. |
Data structures: binary search trees, tree walks, relation to quicksort. Reading: Chapter 12. Homework 3 due. Homework 4 out. |
|
February 8
|
February 10
|
Data structures: red-black trees, rotations, insertion, deletion. Reading: Chapter 13. |
Dynamic programming: optimal binary search trees, longest common subsequence. Reading: Chapter 15. Homework 4 due. Homework 5 out. [Guest Lecture: Tim Roughgarden] Lecture 11 Slides |
|
February 15
|
February 17
|
|
[No class – President day holiday] |
Augmenting data structures: dynamic order statistics, interval trees. Amortized analysis: the accounting and potential methods. Reading: Chapter 15, 17. Homework 5 due. Programming project out. |
|
February 22
|
February 24
|
|
Midterm examination, in class, closed book. |
Introduction to graph algorithms: representation, breadth first search, depth first search, topological sort. Reading: Chapter 22. Homework 6 out. |
|
February 29
|
March 2
|
|
Graph algorithms: minimum spanning tree algorithms, Prim's algorithm, Kruskal's algorithm. Reading: Chapter 22, 23. |
Graph algorithms: Single-source shortest paths, Dijkstra's algorithm, Bellman-Ford Algorithm, difference constraints. Reading: Chapter 24. Homework 6 due. |
|
March 7
|
March 9
|
|
Graph algorithms: all-pairs shortest paths, matrix multiplication, Floyd-Warshall algorithm. Reading: Chapter 25. |
Class summary. Programming project due. All course work is due by this date. |