| Wed, Jan 21 | Lecture 1: Introduction. Divide and conquer: Merge-sort |
Course org. handout;
Chapters 1 and 2 |
| Mon, Jan 26 | Lecture 2: Growth of functions; asymptotic analysis; recurrence relations |
Chapters 3, 4, Appendix A
HW1 out |
| Wed, Jan 28 |
Lecture 3: Recurrence relations; Master theorem
Quiz 1 |
Chapter 4, Appendix A
|
| Mon, Feb 2 | Lecture 4: Strassen's matrix multiplication; Quicksort |
Chapters 7, 28.2
HW1 due Tues, Feb 3 by 4 pm |
| Wed, Feb 4 | Lecture 5: Dynamic programming: LCS |
Chapter 15
|
| Mon, Feb 9 |
Lecture 6:
Graphs; graph representation; all-pairs shortest paths (APSP)
|
Chapter 22, Appendix B.4, B.5
HW2 out |
| Wed, Feb 11 |
Lecture 7:
Floyd Warshall; matrix multiplication APSP
Quiz 2 |
Chapter 25 |
| Mon, Feb 16 | Lecture 8: Greedy algorithms |
Chapter 16
HW2 due Tues, Feb 17 by 4 pm |
| Wed, Feb 18 | Lecture 9: Minimum spanning tree (MST); Kruskal's algorithm Dijkstra-Jarnik-Prim (DJP) algorithm (without data structures) | Chapter 23 | Mon, Feb 23 | Lecture 10: SSSP algorithms: Dijkstra and Bellman-Ford |
Chapter 24
HW3 out |
| Wed, Feb 25 |
Lecture 11:
Data structures. Priority queue and heapsort;
DJP and Dijkstra's algorithms re-visited.
Quiz 3 |
Chapters 6, 23, 24 |
| Mon, Mar 2 | Lecture 12: Amortized analysis; table expansion and contraction |
Chapter 17
HW3 due Tues, Mar 3 by 4 pm |
| Wed, Mar 4 | Lecture 13: Disjoint sets data structure; Kruskal's algorithm re-visited | Chapters 21 and 23 |
| Mon, Mar 9 | TEST 1 | |
| Wed, Mar 11 | Lecture 14: Dictionaries: Binary search tree; red-black tree | Chapters 12 and 13 |
| MAR 16 & 18 | Spring Break | NO CLASS |
| Mon, Mar 23 | Lecture 15: Augmenting data structures; hashing |
Chapters 14, 11
HW4 out |
| Wed, Mar 25 |
Lecture 16:
Basic probability; perfect hashing
Quiz 4 |
Appendix C, Chapter 11
|
| Mon, Mar 30 | Lecture 17: Universal hashing; randomized algorithms |
Chapters 11, 5
HW4 due Tues, Mar 31 by 4 pm |
| Wed, Apr 1 | Lecture 18: Randomized Quicksort; randomized selection | Chapters 7, 9 |
| Mon, Apr 6 | Lecture 19: Binomial and geometric distributions; sorting lower bound; radix sort |
Appendix C, Section 5.4.2, Chapter 8
HW5 out |
| Wed, Apr 8 |
Lecture 20:
Maximum flow
Quiz 5 |
Chapter 26 |
| Mon, Apr 13 | Lecture 21: Maxflow-mincut theorem; bipartite matching |
Chapter 26
HW5 due Tues, Apr 14 by 4 pm |
| Wed, Apr 15 | Lecture 22: P, polynomial-time verification, NP |
Chapter 34
|
| Mon, Apr 20 | TEST 2 |
|
| Wed, Apr 22 | Lecture 23: Polynomial-time reductions; NP-completeness | Chapter 34 |
| Mon, Apr 27 | Lecture 24: Approximation algorithms: approx vertex cover,triangle-TSP |
Chapter 35
HW6 out |
| Wed, Apr 29 |
Lecture 25: Linear programming
Quiz 6 |
Chapter 29 |
| Mon, May 4 | Lecture 26: Online algorithms -- paging |
HW6 due Tues, May 5 by 4 pm |
| Wed, May 6 | Lecture 27: Wrap-up | Chapter 29 |
|
|
|
|
| Wed, May 13, 7-10 p.m. | FINAL EXAM | Room JGB 2.218 |
Course URL: http://www.cs.utexas.edu/~vlr/s09.357h/index.html