CME 305: Discrete Mathematics and Algorithms
Instructor: Reza Zadeh
Time: Tuesdays and Thursdays 12:50 PM - 2:05 PM
Room: Building 60 Room 120
- Basic Algebraic Graph Theory
- Minimum Spanning Trees and Matroids
- Maximum Flow and Submodularity
- Approximation Algorithms
- Randomized Algorithms
- The Probabilistic Method
- Spectral Sparsification
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.
Grade breakdown: 50% final, 30% midterm, 20% assignments (4 of them). The midterm and final will be good practice for the ICME qualifying exam.
Algorithm Design by Kleinberg and Tardos [KT]
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. 12 in class
Final: Date TBA
- Assignment 1 [pdf] [tex] [solutions], Collected Thursday Jan 22nd at beginning of class
- Assignment 2 [pdf] [tex] [solutions], Collected Thursday Feb 5th at beginning of class
- Assignment 3 [pdf] [tex] [solutions], Collected Thursday Feb 26th at beginning of class
- Assignment 4 [pdf] [tex], Due Thursday Mar 12th at beginning of class
Note that these references are neither required reading for the class nor intended to be any substitute for the material covered during lectures.
Scanned lecture notes by Vineet
2015 Midterm pdf, Solutions pdf
2014 Midterm and Solutions pdf,
2011 Midterm pdf,
2010 Midterm pdf,
Practice Midterm 1 (In-Class) pdf,
Practice Midterm 2 (In-Class) pdf,
Spring 2012 Qual pdf.
Fall 2012 Qual pdf.
Spring 2013 Qual pdf.
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
Winter 2014: Class website
Reza Zadeh (rezab at stanford)
Office hours: by appointment
Nolan Skochdopole (naskoch at stanford)
Office hours: 2:15 - 4:15 pm Tuesdays
Simon Anastasiadis (simonsa at stanford)
Office hours: 2:15 - 4:15 pm Wednesdays
TA office hours will be held in the Huang Engineering Center basement (in front of the ICME office)