| Wed, Jan 17 | CLASS MOVED TO April 5 (Lecture lb) |
|
| Mon, Jan 22 | Lecture 1: Introduction; Merge-sort; analysis of Merge |
Course org. handout;
Chapters 1 and 2 |
| Wed, Jan 24 | Lecture 2: Analysis of Merge-sort; growth of functions; asymptotic analysis |
Chapters 2 and 3
HW1 out. |
| Mon, Jan 29 | Lecture 3: Divide & conquer; recurrence relations; summations; Master theorem | Chapter 4, Appendix A |
| Wed, Jan 31 | Lecture 4: Quicksort: algorithm and correctness; basic probability |
Chapter 7, Appendix C
HW1 due by 4 p.m. on Thu, Feb 1 |
| Mon, Feb 5 | Lecture 5: Randomized algorithms; Generating a random permutation |
Chapter 5
HW2 out |
| Wed, Feb 7 | Lecture 6: Randomized Quicksort |
Chapter 7
|
| Mon, Feb 12 | Lecture 7: Randomized Selection |
Chapter 9
HW2 due by 4 p.m. on Tues, Feb 13 |
| Wed, Feb 14 | Lecture 8: Dynamic programming: LCS | Chapter 15 |
| Mon, Feb 19 | Lecture 9: Graphs; graph representation; all-pairs shortest paths (APSP) |
Chapter 22, Appendix B.4, B.5
HW3 out |
| Wed, Feb 21 | Lecture 10: Floyd Warshall; matrix multiplication APSP | Chapter 25 |
| Mon, Feb 26 | Lecture 11: Greedy paradigm |
Chapters 16
HW3 due by 4 pm on Tues, Feb 27 |
| Wed, Feb 28 | Lecture 12: Minimum spanning tree (MST); Kruskal's algorithm (without data structures) | Chapter 23 |
| Mon, Mar 5 | TEST 1 | |
| Wed, Mar 7 |
Test review
Lecture 13: MST algorithm of Dijkstra-Jarnik-Prim (without data structures) |
Chapter 23 |
| MAR 12 & 14 | Spring Break | NO CLASS |
| Mon, Mar 19 | Lecture 14: Single-source shortest paths (SSSP) |
Chapter 24
HW4 out |
| Wed, Mar 21 | Lecture 15: SSSP with non-negative weights: Dijkstra's algorithm (without data structures) | Chapter 24 |
| Mon, Mar 26 | Lecture 16: Data structures. Priority queue and heapsort; DJP and Dijkstra's algorithms re-visited. |
Chapter 6 (and 23, 24)
HW4 due by 4 pm on Tues, Mar 27 |
| Wed, Mar 28 | Lecture 17: Amortized analysis; table expansion and contraction | Chapter 17 |
| Mon, Apr 2 | Lecture 18: Disjoint sets data structure; Kruskal's algorithm re-visited |
Chapters 21 and 23
HW5 out |
| Wed, Apr 4 | Lecture 19: Dictionaries: hashing with chaining |
Chapter 11
|
| THU, APR 5 | Lecture lb: Lower bound for comparison sorting; radix sort |
Chapter 8
|
| Mon, Apr 9 | Lecture 20: Universal hashing; perfect hashing; Bloom filters |
Chapter 11
HW5 due by 4 pm on Tues, Apr 10 |
| Wed, Apr 11 | Lecture 21: Binary search trees; B-trees | Chapters 12 and 18 |
| Mon, Apr 16 | Lecture 22: Feasible computations, P | Chapter 34 |
| Wed, Apr 18 | TEST 2 | |
| Mon, Apr 23 | Lecture 23: Polynomial-time verification, NP, polynomial-time reduction |
Chapter 34
HW6 out |
| Wed, Apr 25 | Lecture 24: NP-completeness; approximation algorithms, approx vertex cover | Chapters 34, 35 |
| Mon, Apr 30 | Lecture 25: Introduction to maximum flow |
Chapter 24
HW6 due by 4 p.m. on Tues, May 1 |
| Wed, May 2 | Lecture 26: Introduction to linear programming; wrap-up | Chapter 29 |
|
|
|
|
| Wed, May 9, 9am-noon | FINAL EXAM | WEL 2.256 |
Back to CS357 page.