# Syllabus

Readings refer to the course text: Kleinberg and Tardos, *Algorithm Design*, Addison Wesley/Pearson, 2005. ISBN 0-321-29535-8.

Lecture topics are subject to change.

DATE | LECTURE/EVENT | NOTES/READINGS |
---|---|---|

1/21 | Welcome and introduction | 1.2 |

1/23 | The stable matching problem | 1.1 |

1/25 | Greedy algorithms I: Interval scheduling and the “greedy stays ahead” analysis technique | 4.1 |

1/28 | Greedy algorithms II: Scheduling to minimize lateness and the “exchange argument” analysis technique | 4.2, 4.3 |

1/30 | Greedy algorithms III: Minimum spanning tree algorithms | 4.5 |

1/31 | Homework 1 due | |

2/1 | Greedy algorithms IV: Data structures for fast minimum spanning tree implementations | 4.6 |

2/4 | Dynamic programming I: Weighted interval scheduling | 6.1–6.3 |

2/6 | Dynamic programming II: Edit distance, aka sequence alignment | 6.6 |

2/8 | Dynamic Programming III: Bellman-Ford shortest path algorithm | 6.8 |

2/10 | Homework 2 due | |

2/11 | Divide-and-conquer I: Closest pair of points in the plane | 5.4 |

2/13 | Divide-and-conquer II: Fast multiplication of integers and matrices | 5.5 |

2/15 | Divide-and-conquer III: Fast Fourier transform, polynomial multiplication | 5.6 |

2/18 | Dynamic programming IV: RNA secondary structure | 6.5 |

2/20 | Prelim 1 review | Review sheet |

2/21 | Prelim 1, 7:30–9pm, Uris G01 | |

2/22 | Network Flow I: Basic definitions | 7.1 |

2/24 | Homework 3 due | |

2/25 | Network Flow II: The Ford-Fulkerson Algorithm | 7.1 |

2/27 | Network Flow III: Max-Flow Min-Cut, Bipartite Matching | 7.2, 7.5 |

3/1 | Network Flow IV: Further examples of flow reductions | 7.10–7.12 |

3/4 | Network Flow V: Extensions to network flow | 7.7–7.9 |

3/6 | Network Flow VI: Polynomial-time max-flow algorithms | 7.3, Notes on the Edmonds-Karp algorithm, Notes on Dinic's algorithm |

3/7 | Homework 4 due | |

3/8 | NP-Completeness I: Reductions between SAT and Clique | 8.2, Notes on reductions and NP-completeness |

3/11 | NP-Completeness II: Formal Definition of the Class NP. More NP-Complete Problems in Graph Theory | 8.1, 8.3 |

3/13 | NP-Completeness III: Covering problems. Set Cover, Exact Cover, Three-Dimensional Matching | 8.6 |

3/15 | NP-Completeness IV: Colorability | 8.7 |

3/18–22 | Spring Break | |

3/25 | NP-Completeness V: Hamiltonian Cycle | 8.5 |

3/26 | Homework 5 due | |

3/27 | NP-Completeness VI: NP-complete numerical problems. Subset sum, Partition, Knapsack | 8.8 |

3/29 | Review of NP-completeness, discussion of other complexity classes. (L, #P, PSPACE) | 8.10 |

4/1 | Turing machine definitions | Notes on TMs, §1,2 |

4/3 | Turing machine examples. Multitape Turing machines | Notes on TMs, §2,3 |

4/5 | Universal Turing machine | Notes on TMs, §4 |

4/7 | Homework 6 due | |

4/8 | Prelim 2 review | Review sheet |

4/9 | Prelim 2, 7:30–9pm, Kimball B11 (aab227–jdb387), Olin 155 (jdh339–sra57), Olin 165 (ss2249–zp34) | |

4/10 | Diagonalization and undecidability | Notes on TMs, §4 |

4/12 | Decidable and undecidable problems | Notes on TMs, §5,6 |

4/15 | The Cook-Levin Theorem | Notes on the Cook-Levin theorem |

4/17 | Greedy approximation algorithms: load balancing | 11.1 |

4/19 | Greedy approximation algorithms: center selection | 11.2 |

4/21 | Homework 7 due | |

4/22 | Greedy approximation algorithms: set cover | 11.3 |

4/24 | Approximation algorithms via rounding and dynamic programming: the knapsack problem | 11.8 |

4/26 | Randomized algorithms I: Randomized algorithms, linearity of expectation, waiting times for independent trials | 13.1, 13.3 |

4/29 | Randomized algorithms II: k-th element, quicksort, 3SAT | 13.4, 13.5 |

5/1 | Randomized algorithms III: Universal hashing | 13.6 |

5/3 | No lecture — slope day | |

5/5 | Homework 8 due | |

5/12 | Final exam review, 4–6pm, Upson B17 | |

5/16 | Final Exam, 9–11:30am (exam period Q), Statler Hall 185 (Statler Auditorium) |