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, Longest-Common-Subsequence.
  6. 01/24: Dynamic Programming II: LCS contd., Knapsack, Matrix parenthesization. [Quiz 2]
  7. 01/29: Network Flows and Matchings I.
    01/30: (tutorial) CLASS CANCELLED TODAY.
  8. 01/31: CLASS CANCELLED TODAY. [Hwk2 presentations]
  9. 02/05: Network Flows and Matchings II.
    02/06: (tutorial) More network flow and Review
    02/07: Midterm (one sheet of notes allowed)
  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: Online algorithms.
    03/06: (tutorial)
  17. 03/07: Online routing / Awerbuch-Azar-Plotkin. [Quiz 4]
  18. 03/12: Mechanism design and VCG. [Hwk5 presentations]
  19. 03/13: Review
    03/21: Final Exam 10:30-12:30 Note: you may bring 1 sheet of notes.

Expected outcomes

Expected course outcomes include: