CME 305: Discrete Mathematics and Algorithms
Instructor: Reza Zadeh
Winter 2014
Time: Tuesdays and Thursdays 12:50 PM  2:05 PM
Room: Sequoia Hall 200
Topics Covered
 Basic Algebraic Graph Theory
 Minimum Spanning Trees and Matroids
 Maximum Flow and Submodularity
 NPHardness
 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]
Grade breakdown: 50% final, 30% midterm, 20% assignments (4 of them). The midterm and final will be good practice for the ICME qualifying exam.
Midterm: Thursday Feb. 13 in class
Final: Wednesday Mar. 19, 710PM in 200205 (in the quad, NOT Sequoia)
Assignments
References
Note that these references are neither required reading for the class nor intended to be any substitute for the material covered during lectures.
 Tu 1/7: Lecture 1 (Intro to Dynamic Programming): KT 6.16.4
 Th 1/9: Lecture 2 (Trees, Eulerian Circuits, MST): KT 3.1, 4.5; Notes
 Tu 1/14: Lecture 3 (MinCut, MaxFlow, FordFulkerson): KT 7; Notes
 Th 1/16: Lecture 4 (st MinCut/MaxFlow Applications, Global MinCut): Previous Notes; Notes; A New Approach to the Minimum Cut Problem (Karger and Stein)
 Tu 1/21: Lecture 5 (Randomized Algorithms): KT 13.113.5; MR 1, 6
 Th 1/23: Lecture 6 (Randomized Walks and Electrical Networks): Notes; MR 6 (Highly Recommended)
 Tu 1/28: Lecture 7 (Concentration Inequalities): MR 34, 6.5; KT 13.9
 Th 1/30: Lecture 8 (The Probabilistic Method): Notes; MR 5; AS 1
 Tu 2/4: Lecture 9 (Problem Classes, Reductions): Notes; The NP Compendium; KT 8
 Th 2/6: Lecture 10 (Approximation Algorithms): Notes; KT 11
 Tu 2/11: Lecture 11 (Midterm Review)
 Th 2/13: Lecture 12 (Midterm)
 Tu 2/18: Lecture 13 (GoemansWilliamson MaxCut, Bin Packing): V 26; CMU MaxCut Notes; Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming (Goemans and Williamson)
 Th 2/20: Lecture 14 (Asymmetric TSP, Spectral Graph Theory, Sparsification Intro): An O(log n/log log n)approximation Algorithm for ATSP (Asadpour et al.); Sparsification Notes
 Tu 2/25: Lecture 15 (Graph Sparsification): Sparsification Notes; Graph Sparsification by Effective Resistances (Spielman and Srivastava)
 Th 2/27: Lecture 16 (Graph Sparsification): Sparsification Notes; Graph Sparsification by Effective Resistances (Spielman and Srivastava)
 Tu 3/4: Lecture 17 (Matroids): MIT Matroid Notes
 Th 3/6: Lecture 18 (Applications: ML and Clustering): An Impossibility Theorem for Clustering (Kleinberg); A Uniqueness Theorem for Clustering (Zadeh and BenDavid)
 Tu 3/11: Lecture 19 (Applications: Distributed Computing): NodeIterator Analysis; Counting Triangles with Spark
 Th 3/13: Lecture 20 Exam Review
Exams
Midterm Solutions pdf,
2011 Midterm pdf,
Solutions pdf.
2010 Midterm pdf,
Solutions pdf.
Practice Midterm 1 (InClass) pdf,
Solutions pdf.
Practice Midterm 2 (InClass) pdf,
Solutions pdf.
Spring 2012 Qual pdf.
Fall 2012 Qual pdf.
Spring 2013 Qual pdf.
Problem Sessions
Problem Session 2/10/14 and Solutions
Problem Session 2/20/14 and Solutions
PreFinal Workshop



Contacts
Reza Zadeh (rezab at stanford)
Office hours: by appointment
Edward Schmerling (schmrlng at stanford)
Office hours: 2:154:15PM Tuesdays
Kun Yang (kunyang at stanford)
Office hours: 2:304:30PM Wednesdays
TA office hours will be held in the Huang Engineering Center basement (in front of the ICME office)

