TTIC 31010 / CMSC 37000 Algorithms, Winter Quarter 2019
TA: Kevin Stangl (kevin at ttic.edu),
Graders: Peter Hong and Pranav Nanga
This is a graduate level course on algorithms with the emphasis on central combinatorial optimization problems and important methods for algorithm design and analysis. Topics covered include greedy algorithms, dynamic programming, network flow, linear programming, NP-completeness, approximation algorithms, randomized algorithms and the probabilistic method, and online algorithms.
- Lectures: Tue/Thu 9:30-10:50, TTIC Room 526.
- Tutorial: Wed 3:00-4:00, TTIC Room 526. Note: some weeks the tutorial will be swapped with a lecture - see schedule below.
- Office hours: Wed 2:00-3:00, TTIC Room 439 (Prof. Blum). Wed 4:00-5:00, TTIC Room 530 (Kevin Stangl).
- Coursework: 3 written homeworks, 2 oral presentation homeworks, 4 quizzes, 1 midterm, 1 final. Breakdown: hwks 50%, quizzes 10%, midterm 15%, final 25%.
- Rules: Written homeworks are to be done by yourself, oral presentations in groups of 3.
- Textbook: Recommended textbook is Kleinberg & Tardos, Algorithm Design, which comes with a free helpful resource (but CLRS and Dasgupta-Papadimitriou-Vazirani are fine too).
Lecture/tutorial topics and notes (subject to change). All lectures, tutorials, and tests in TTIC Room 526.
- 01/08: Divide-and-conquer paradigm: Karatsuba multiplication, Strassen's algorithm, solving recurrences.
- 01/09: Concrete models, analysis of upper & lower bounds.
01/10: (tutorial) Asymptotic analysis, recurrences - Appendix A.
- 01/15: Greedy algorithms: scheduling, Huffman codes. [Quiz 1 - covers material in lectures 1 & 2 + tutorial]
01/16: (tutorial) Problems related to greedy algorithms.
- 01/17: Greedy algorithms: Dijkstra's algorithm (shortest paths), Prim's algorithm (MSTs), Kruskal's algorithm (MSTs). [Hwk 1 due]
01/22: (tutorial) Graph algorithms and spanning trees.
- 01/23: Dynamic Programming I: Bellman-Ford, Floyd-Warshall, Longest-Common-Subsequence.
- 01/24: Dynamic Programming II: LCS contd., Knapsack, Matrix parenthesization. [Quiz 2]
- 01/29: Network Flows and Matchings I.
01/30: (tutorial) CLASS CANCELLED TODAY.
- 01/31: CLASS CANCELLED TODAY. [Hwk2 presentations]
- 02/05: Network Flows and Matchings II.
02/06: (tutorial) More network flow and Review
02/07: Midterm (one sheet of notes allowed)
- 02/12: Linear Programming I.
02/13: (tutorial) Examples of writing problems as LPs.
- 02/14: Linear Programming II. [Hwk3 due]
- 02/19: Linear Programming III / NP-Completeness I.
02/20: (tutorial) Linear programming and NP-completeness.
- 02/21: NP-Completeness II. [Quiz 3]
- 02/26: Approximation algorithms.
02/27: (tutorial) Approximation algorithms, integrality gaps
- 02/28: Randomized algorithms. [Hwk 4 due]
- 03/05: Online algorithms.
- 03/07: Online routing / Awerbuch-Azar-Plotkin. [Quiz 4]
- 03/12: Mechanism design and VCG. [Hwk5 presentations]
- 03/13: Review
03/21: Final Exam 10:30-12:30 Note: you may bring 1 sheet of notes.
Expected course outcomes include:
- Ability to design and rigorously analyze algorithms using paradigms such as dynamic programming, greedy algorithms, and reduction.
- Familiarity with important graph algorithms such as shortest paths, MSTs, and network flow.
- Understand the use of linear programming in optimization. Be able to formulate problems as linear programs. Familiarity with linear programming duality.
- Ability to apply NP-completeness via reductions and understanding the role of lower bounds
- Comfort with thinking about and analyzing randomized and online algorithms