CME 305: Discrete Mathematics and Algorithms

Topics Covered

• Basic Algebraic Graph Theory
• Minimum Spanning Trees and Matroids
• Maximum Flow and Submodularity
• NP-Hardness
• Approximation Algorithms
• Randomized Algorithms
• The Probabilistic Method
• Spectral Sparsification

Course Description

This course is targeting doctorate students with strong foundations in mathematics who wish to become more familiar with the design and analysis of discrete algorithms. An undergraduate course in algorithms is not a prerequisite, only familiarity with basic notions in linear algebra and discrete mathematics.

Required textbook:
Algorithm Design by Kleinberg and Tardos [KT]

Optional textbooks:
Graph Theory by Reinhard Diestel [D]
Approximation Algorithms by Vijay Vazirani [V]
Randomized Algorithms by Rajeev Motwani and Prabakhar Raghavan [MR]
The Probabilistic Method by Noga Alon and Joel Spencer [AS]

Midterm: Thursday, Feb 16th
Final: 03/22/2017, 12:15 - 3:15 P.M. at STLC 114 (science teaching & learning center)

Assignments

• Assignment 1 [pdf] [tex], Due at the beginning of class Thursday 01/26. [Solutions]
• Assignment 2 [pdf] [tex], Due at the beginning of class Thursday 02/09. [Solutions]
• Assignment 3 [pdf] [tex], Due at the beginning of class Thursday 03/02 [Solutions]
• Assignment 4 [pdf] [tex], Due at the beginning of class Thursday 03/16 [Solutions]

References

• Tu 1/10: Lecture   1 "The min-cut is small" (Intro to Graph Theory, Karger's Global Min-Cut): D 1.1-1.6; Notes; A New Approach to the Minimum Cut Problem (Karger and Stein)
• Th 1/12: Lecture   2 "Pigeons and eagles" (s-t Min-Cut, Max-Flow, Ford-Fulkerson): KT 7: Notes
• Tu 1/17: Lecture   3 (Applications of Max-Flow, Probabilistic Method): Notes; MR 5; AS 1
• Th 1/19: Lecture   4 (Minimum Spanning Trees): Notes
• Tu 1/24: Lecture   5 (Ramsey Numbers and Probabilistic Method):MST Alg with Inverse-Ackerman Complexity ; , Exhausting a Graph, Resistance of a Graph and Cover Time; Notes; MR 6
• Th 1/26: Lecture   6 (Cover Times): "Random Walks on Graphs: A Survey"
• Tu 1/31: Lecture   7 (Markov Inequality; Tighter Bounds for Cover Times)
• Th 2/02: Lecture   8 (2-SAT, 3-SAT, Intro to Problem Classes): Notes; The NP Compendium; KT 8
• Tu 2/07: Lecture   9 (Problem Classes, Reductions): Notes; The NP Compendium; KT 8
• Th 2/09: Lecture 10 (Approximation Algorithms) Notes; KT 11
• Tu 2/14: Lecture 11 (Midterm Review)
• Th 2/16: Midterm Solutions
• Tu 2/21: Lecture 13 (Approximation Algorithms - vertex cover, bin-packing) Notes; KT 11
• Th 2/23: Lecture 14 (TSP). Paths, Trees, and Flowers.
• Tu 2/28: Lecture 15 (Dynamic Programing): KT 6
• Th 3/02: Lecture 16 (Asymmetric TSP, Max Cut): V 26; An O(log n/log log n)-approximation Algorithm for ATSP (Asadpour et al.) (Goemans-Williamson Max-Cut): CMU Max-Cut Notes; Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming (Goemans and Williamson)
• Tu 3/07: Lecture 17 (Graph Sparsification) Notes; Graph Sparsification by Effective Resistances (Spielman and Srivastava)
• Th 3/09: Lecture 18 (Machine Learning): Impossibility Theorem; Uniqueness theorem; KMeans++
• Tu 3/14: Lecture 19 (Matroids): MIT Matroid Notes

  2016 lecture notes, by Andreas

Practice Exams

Spring 2012 Qual pdf.

Fall 2012 Qual pdf.

Spring 2013 Qual pdf.

2016 Midterm pdf, Solutions pdf

2015 Midterm pdf, Solutions pdf

2014 Midterm and Solutions pdf,

2011 Midterm pdf, Solutions pdf.

2010 Midterm pdf, Solutions pdf.

Practice Midterm 1 (In-Class) pdf, Solutions pdf.

Practice Midterm 2 (In-Class) pdf, Solutions pdf.

Problem Sessions

Problem Session 3/20/17, 1

Problem Session 2/14/17 Solutions

Problem Session 3/11/16

Problem Session 2/11/15 and Solutions

Problem Session 2/10/15 and Solutions

Problem Session 2/10/14 and Solutions

Problem Session 2/20/14 and Solutions

Pre-Final Workshop

Previous years

Winter 2016: Class website

Winter 2015: Class website

Winter 2014: Class website