CME 305: Discrete Mathematics and Algorithms
Instructor: Reza Zadeh
Winter 2016
Time: Tue, Thu 1:30 PM  2:50 PM
Room: Econ 140
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 11th
Final: TBA
Assignments
 Assignment 1, [pdf] [tex], Due at the beginning of class Thursday 01/21 Solutions.
 Assignment 2, [pdf] [tex], Due at the beginning of class Thursday 02/04 Solutions.
References
Note that these references are not intended to be any substitute for the material covered during lectures.
 Tu 1/5: Lecture 1 (Intro to Graph Theory, Karger's Global MinCut): D 1.11.6; Notes; A New Approach to the Minimum Cut Problem (Karger and Stein)
 Th 1/7: Lecture 2 (st MinCut, MaxFlow, FordFulkerson): KT 7: Notes
 Tu 1/12: Lecture 3 (Applications of MaxFlow, Probabilistic Method): Notes; MR 5; AS 1
 Th 1/14: Lecture 4 (Minimum Spanning Trees, Exhausting a Graph): Notes
 Tu 1/19: Lecture 5 (Randomized Walks and Electrical Networks): Notes 1; Notes 2; MR 6
 Th 1/21: Lecture 6 (Markov Inequality; Tighter Bounds for Cover Times): Notes
 Tu 1/26: Lecture 7 (Problem Classes, Reductions): Notes; The NP Compendium; KT 8
 Th 1/28: Lecture 8 (Approximation Algorithms): Notes; KT 11
 Tu 2/3: Lecture 9 (TSP; Dynamic Programing): KT 6
 Th 2/5: Lecture 10 (Dynamic Programming, Cover Times): KT 6
 Tu 2/9: Lecture 11 (Midterm Review): Problem session 1 and 2
 Th 2/11: Lecture 12 (Midterm)
Practice Exams
Spring 2012 Qual pdf.
Fall 2012 Qual pdf.
Spring 2013 Qual pdf.
2015 Midterm pdf, Solutions pdf
2014 Midterm and 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.
Problem Sessions
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
PreFinal Workshop
Previous years
Winter 2015: Class website
Winter 2014: Class website



Contacts
Reza Zadeh (rezab at stanford)
Office hours: by appointment
Arun Jambulapati (jmblpati at stanford)
Office hours: 35pm on Tuesdays
Qingyun Wu (wqy at stanford)
Office hours: 35pm on Wednesdays
TA office hours will be held in the Huang Engineering Center basement (in front of the ICME office)

