This schedule will be updated periodically throughout the term. Last update: May 10.
The text is Cormen, Leiserson, and Rivest: Introduction to Algorithms, MIT
Press, 1990.
The handout listed below for MaxFlow is a chapter written by Kleinberg &
Tardos for CS482; the corresponding chapters in the text are also listed below, but the
handout is more readable.
| Tuesdays | Thursdays | |||||
|---|---|---|---|---|---|---|
| Date | Topics | Text | Date | Topics | Text | |
| Jan 26 | General Course Information Asymptotic Notation (big-O) Worst-Case vs. Expected Times |
1 2 |
Jan 28 | Abstract Data Types (ADTs) ADT Stack, ADT Queue ADT Dictionary Direct Address Table, Intro to Hashing |
11 12.1-2 |
|
| Feb 2 | Hashtables Table Doubling Application: Spell-Checking |
12.2-3 |
Feb 4 | Application: Geometric Hashing Binary Search Trees (BSTs) |
13.1-3 |
|
| Feb 9 | Balanced Trees, Rotations Examples: Randomized BSTs, Splay Trees |
14.2 |
Feb 11 | 234-Trees Red-Black Trees Choosing a Dictionary Scheme ADT Priority Queue |
19.1-2 14.1 7.5 |
|
| Feb 16 | PQ using a Heap PQ using an Array of Lists Application: Event Driven Simulation Application: Line Segment Intersection |
7.1-3 |
Feb 18 | Choosing a Priority Queue Scheme Union/Find |
22.1-3 |
|
| Feb 23 | Divide & Conquer MergeSort, Binary Search Recurrence Relations Recursive Integer Multiplication Strassens's Matrix Multiplication |
1.3 1.3 4.1,4.3 31.2 |
Feb 25 | More Divide & Conquer Closest Pair of Points Gravitational N-Body Problem |
35.4 |
|
| Mar 2 | Dynamic Programming Matrix-Chain Multiplication |
16.1 16.2 |
Mar 4 | More Dynamic Programming Optimal Polygon Triangulation Protein Alignment (similar to LCS: 16.3) |
16.4 |
|
| Mar 9 | Review | Mar 11 | *** Midterm Exam *** | |||
| Mar 16 | Greedy Algorithms Graphs Minimum Spanning Trees (MSTs) |
17.1 23.1 24 |
Mar 18 | More Greedy Algorithms Shortest Common Superstring DNA Sequencing Knapsack Problems |
17.2 |
|
| Mar 23 | *** Spring Break *** | Mar 25 | *** Spring Break *** | |||
| Mar 30 | Amortized Analysis Finding the Convex Hull |
18.1-2 35.3 |
Apr 1 | More Amortized Analysis Analysis of Union/Find |
22.4 |
|
| Apr 6 | Reductions Lower Bounds for Sorting |
9.1 |
Apr 8 | Digraphs Graph Traversals (DFS & BFS) Reductions among Geometric Problems |
23.1 23.2-3 |
|
| Apr 13 | Guest Lecturer: MaxFlow | 27.1 handout |
Apr 15 | Guest Lecturer: MaxFlow | 27.2 handout |
|
| Apr 20 | Maximum Bipartite Matching | 27.3 handout |
Apr 22 | Circulation with Demands Airline Scheduling Protein Sequence Design |
handout handout |
|
| Apr 27 | Intro to NP-Completeness | 36.1-2 | Apr 29 | NP-Completeness Satisfiability (SAT), Clique Hamiltonian Cycle Traveling Salesman Problem (TSP) |
36.4-5 | |
| May 4 | More NP-Completeness Vertex-Cover, 3SAT, Subset Sum |
36.4-5 | May 6 | Approximating TSP What I do (Computational Geometry) |
37.2 |
|
Thursday, May 20: Review for Final Exam; 9am, Upson 205 |
||||||
*** Friday, May 21: Final Exam; noon in Bard 140 *** |
||||||