Class: MW 9:00-10:20am in LOW 216
Instructor: Cynthia Vinzant (email)
Instructor Office Hours: M 1:30-2:30pm, W 10:30-11:30am in PDL C-439
Teaching Assistant Natasha Crepeau (email)
TA Office Hours: Tu 2-3pm in PDL C-446

Class Syllabus

Quick Links: Gradescope, Discussion Board

References
There is no official textbook for the class. The lectures will follow notes written by Alexander Schrijver that you can find here.

Schedule (Tentative)

Week	Topic	Reading	Homework
Sept. 25	Graphs and Minimum Spanning Trees Notes: 09/25	S 1.4, 6	HW 1 (.tex, .pdf), due Oct. 3
Sept. 30, Oct. 2	Convexity, Polyhedra, and Linear Programming Notes: 09/30, 10/02	S 2.1, 2.2, 2.4	HW 2 (.tex, .pdf) due Oct. 10
Oct. 7,9	Duality in LPs, Matchings Notes: 10/07, 10/09	S 2.3, 2.4, 3.1	HW 3 (.tex, .pdf), due Oct. 17
Oct. 14,16	Matchings Notes: 10/14, 10/16	S 3.2-3.4	HW 4 (.tex, .pdf), due Oct. 24
Oct. 21, 23	Network Flows Notes: 10/21, 10/23	S 4.2-4.4	HW 5 (.tex, .pdf), due Oct. 31
Oct. 28, 30	Max Flow and applications Notes: 10/28, 10/30	S 4.5, 4.6	HW 6 (.tex, .pdf), due Nov. 7
Nov. 4, 6	Integer Programming and Total Unimodularity Notes: 11/04, 11/06	S 8.1, 8.2, 8.4	HW 7 (.tex, .pdf), due Nov. 14
Nov. 13 No class Nov. 11	TU matrices from graphs Notes: 11/13	S 8.3, 8.4	HW 8 (.tex, .pdf), due Nov. 21
Nov. 18, 20	Approximations of Max Cut and SDPs Notes: 11/18, 11/20	Laurent, Vallentin (Ch 2 & 7)
Nov. 25, 27	Matroids Notes: 11/25, 11/27	S 10.1, 10.2, 10.3, 10.7	HW 9 (.tex, .pdf), due Dec. 5
Dec. 2,4	Matroids (cont') Notes: 12/02, 12/04	S 10.4, 10.5