TTIC 31010 / CMSC 37000 Algorithms, Winter Quarter 2019

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


Homeworks


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: