| Wed, Jan 18 | Introduction; Merge-sort; algorithm analysis | Course
org. handout; Chapters 1 and 2 |
| Mon, Jan 23 | CLASS CANCELLED | NO CLASS -- will be re-scheduled |
| Wed, Jan 25 | Growth of functions; asymptotic analysis, summations | Chapter 3, Appendix A |
| Mon, Jan 30 | Divide & conquer; recurrence relations; Master theorem |
Chapter 4, Appendix A
HW1 out |
| Wed, Feb 1 | Quicksort: algorithm and correctness; basic probability. | Chapter 7, Appendix C |
| TBA (Re-scheduled class) | Randomized algorithms; Generating a random permutation | Chapter 5 |
| Mon, Feb 6 | Randomized Quicksort |
Chapter 7
HW1 in by 5 pm, Mon, Feb 6 |
| Wed, Feb 8 | Randomized Selection |
Chapter 9
HW2 out |
| Mon, Feb 13 | Dynamic programming: LCS | Chapter 15 |
| Wed, Feb 15 | Graphs; graph representation; all-pairs shortest paths |
Chapter 22, Appendix B.4, B.5
HW2 in by 5 pm, Thu, Feb 16 |
| Mon, Feb 20 | Floyd Warshall; matrix multiplication APSP |
Chapter 25
|
| Wed, Feb 22 | TEST 1 |
|
| Mon, Feb 27 | Dynamic programming and greedy strategies | Chapter 16 |
| Wed, Mar 1 | Greedy paradigm; minimum spanning tree (MST) |
Chapters 16 and 23
HW3 out |
| Mon, Mar 6 | MST algorithms of Kruskal and Prim (without data structures) | Chapters 23 |
| Wed, Mar 8 | SSSP with non-negative weights: Dijkstra's algorithm (without data structures) |
Chapter 24
HW3 in by 5 pm, Thu, Mar 9 |
| MAR 13 & 15 | Spring Break | NO CLASS |
| Mon, Mar 20 | Data structures. Priority queue and heapsort; DJP and Dijkstra's algorithms re-visited. | Chapter 6 (and 23, 24) |
| Wed, Mar 22 | Amortized analysis; table expansion and contraction. | Chapter 17
HW4 out |
| Mon, Mar 27 | Disjoint sets data structure; Kruskal's algorithm re-visited | Chapters 21 and 23 |
| Wed, Mar 29 | Binary search trees; red-black trees | Chapters 12 and 13 |
| Mon, Apr 3 | Augmenting data structures; B-trees |
Chapters 14 and 18
HW4 in by 5 pm, Thu, Mar 30 |
| Wed, Apr 5 | Hashing with chaining; universal hashing; perfect hashing |
Chapter 11
HW5 out |
| Mon, Apr 10 | Radix sort; lower bound for comparison sorting | Chapter 8 |
| Wed, Apr 12 | Graph searching: Breadth-first search |
Chapter 22
HW5 in by 5 pm, Thu, Apr 13 |
| Mon, Apr 17 | Depth-first search; topological sort | Chapter 22 |
| Wed, Apr 19 | Feasible computations, P | Chapter 34 |
| Mon, Apr 24 | TEST 2 | |
| Wed, Apr 26 | Polynomial-time verification, NP, polynomial-time reduction |
Chapter 34
HW6 out |
| Mon, May 1 | NP-completeness, approximation algorithms, approx vertex cover | Chapter 35 |
| Wed, May 3 | Wrap-up | HW6 in by 5 pm, Thu, May 5 |
|
|
|
|
| Thu, May 11, 9 a.m. - noon |
FINAL EXAM | |
This is a tentative schedule and some topics may be changed during the course of the semester.
Back to CS357 page.