CME 305/MS&E 316: Discrete Mathematics and Algorithms

Instructor: Aaron Sidford

Winter 2018
Time: Tuesdays and Thursdays, 10:30 AM - 11:50 AM
Room: Education Building, Room 128
Here is the course syllabus.

Overview

This class will introduce the theoretical foundations of discrete mathematics and algorithms. Emphasis will be on providing mathematical tools for combinatorial optimization, i.e. how to efficiently optimize over large structured finite sets. The course will provide a rigorous understanding of both discrete mathematical structures, e.g. graphs, matroids, submodular functions, set systems, etc., as well algorithmic paradigms for optimizing over them, e.g. greedy methods, linear programming, randomized methods, etc. The class constitutes a fast-paced proof-based introduction to the broad area of designing and analyzing algorithms for combinatorial problems. By course completion you should have a solid foundation to enable future theoretical research and practical work on discrete problems.

Textbooks and Schedule

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

Recommended Reading:
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]
The Design and Analysis of Algorithms by Dexter C. Kozen [K]
CS261: Optimization and Algorithmic Paradigms by Luca Trevisan [T]

Grade breakdown: 40% final, 30% midterm, 30% assignments (4 of them). The midterm and final will be good practice for the ICME qualifying exam.

Midterm: Thursday, 02/15/2018 in class
Final: 03/21/2018, 12:15 - 3:15 P.M. at TBA

Lecture Notes and Recommended Reading

Note that these notes are not intended to be any substitute for the material covered during lectures. Further, homework assignments will be exclusively on Canvas.

Tu 1/9: Lecture 1: Class Overview, Global Min-Cut. Notes. Reading: [KT] Chapter 2
Th 1/11: Lecture 2: Introduction to Graph Theory. Notes. Reading: [KT] Chapter 3
Tu 1/16: Lecture 3: Spanning Trees & Matroids. Notes. Reading: [KT] Section 4.5
Th 1/18: Lecture 4: More Matroids & Maximum Flow. Notes. Reading: [KT] Chapter 4, Michel Goemans' matroid lecture notes
Tu 1/23: Lecture 5: Maximum Flow & Minimum s-t Cut. Notes. Reading: [KT] Sections 7.1-7.3
Th 1/25: Lecture 6: Bipartite Matching & Other Applications of Flow. Notes. Reading: [T] Sections 9-11, [KT] Sections 7.5-7.12
Tu 1/30: Lecture 7: Algebraic Methods for Matching. Notes. Reading: Virginia Williams' notes, Marek Cygan's notes
Th 2/1: Lecture 8: More Algebraic Methods for Matching. Notes.
Tu 2/6: Lecture 9: Matrix Multiplication Equivalences and Intro to Spectral Graph Theory. Notes.
Th 2/8: Lecture 10: Spectral Graph Theory. Notes. Reading: [T] Sections 1-2.
Tu 2/13: Lecture 11: More Spectral Graph Theory. Notes.
Th 2/15: Midterm
Tu 2/20: Lecture 12: Random Walks, Cheeger's Inequality. Notes. Optional Reading: Dan Spielman's Spectral Graph Theory Class
Th 2/22: Lecture 13: More Random Walks, commute and cover times. Notes. Optional Reading: Random Walks on Graphs: A Survey Exhausting a Graph, Resistance of a Graph and Cover Time Shayan Oveis Gharan's notes on effective resistances
Tu 2/27: Lecture 14: P vs NP. Notes. Reading: Chapter 8 of [KT]. Optional Reading: The NP-Completeness Compendium
Th 3/1: Lecture 15: NP-Completeness. Notes. Optional Reading: Proof that NP-intermediate problems exist if P != NP

Practice Exams and Problem Sessions

This will be filled in closer to exam time.

Previous years

Please note that the material given in previous years deviates somewhat from this class. If you are looking for additional problems for self-study, it is still worth looking at these however.

Winter 2017: Class website

Winter 2016: Class website

Winter 2015: Class website

Winter 2014: Class website

Contacts

Aaron Sidford (sidford at stanford)
Office hours: Wednesday 5 - 6

Arun Jambulapati (jmblpati at stanford)
Office hours: Friday, 2:30 - 4:30.

Nolan Skochdopole (naskoch at stanford)
Office hours: Wednesday, 1 - 3.

Ananthakrishnan Ganesan (ananthg at stanford)
Office hours: Tuesday, 3 - 4.

TA office hours will be held in the Huang Engineering Center basement (in front of the ICME office)