## Instructor: Avrim Blum

### 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.

### General info

• 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.

1. 01/08: Divide-and-conquer paradigm: Karatsuba multiplication, Strassen's algorithm, solving recurrences.
2. 01/09: Concrete models, analysis of upper & lower bounds.
01/10: (tutorial) Asymptotic analysis, recurrences - Appendix A.
3. 01/15: Greedy algorithms: scheduling, Huffman codes. [Quiz 1 - covers material in lectures 1 & 2 + tutorial]
01/16: (tutorial) Problems related to greedy algorithms.
4. 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.
5. 01/23: Dynamic Programming I: Bellman-Ford, Floyd-Warshall.
6. 01/24: Dynamic Programming II: LCS, Knapsack, Matrix parenthesization. [Quiz 2]
7. 01/29: Network Flows and Matchings I.
01/30: (tutorial) Examples of problems that can be solved with network flow.
8. 01/31: Network Flows and Matchings II. [Hwk2 presentations]
9. 02/05: Zero-sum games.
02/06: (tutorial) More network flow and Review
02/07: Midterm
10. 02/12: Linear Programming I.
02/13: (tutorial) Examples of writing problems as LPs.
11. 02/14: Linear Programming II. [Hwk3 due]
12. 02/19: Linear Programming III / NP-Completeness I.
02/20: (tutorial) Linear programming and NP-completeness.
13. 02/21: NP-Completeness II. [Quiz 3]
14. 02/26: Approximation algorithms.
02/27: (tutorial) Approximation algorithms, integrality gaps
15. 02/28: Randomized algorithms. [Hwk 4 due]
16. 03/05: Amortized analysis.
03/06: (tutorial) Practice with probabilities.
17. 03/07: Online algorithms. [Quiz 4]
18. 03/12: Online routing / Awerbuch-Azar-Plotkin. [Hwk5 presentations]
19. 03/13: Review
03/21: Final Exam 10:30-12:30

### Expected outcomes

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