New Course: MS&E 317, Advanced Combinatorial Optimization

Autumn 2003-04

Stanford University

Instructor: Ashish Goel

Location: RedwdG19, MW 9:30-10:45

(occasional discussion sections on F 9:30-10:45)

Introduces the use of combinatorial and algorithmic techniques for optimization problems. Emphasis on algorithms with provable correctness and efficiency. Reading assignments and homework problems will extend and apply the theory developed in class. Topics: Running time analysis, dynamic programming, trees and paths, flows and matchings, primal-dual algorithms, the probabilistic method, NP-completeness and approximation algorithms.

Pre-requisites:CS 106 A,B, or prior programming experience.

Important Notes:

1. This course can be used to satisfy one of the group I-A Operations Research PhD curriculum requirements.

2. The classes will be co-located with MS&E 217. Please see the MS&E 217 website at http://www.stanford.edu/~ashishg/msande217 for more details about specific course topics, textbook, contact info, evaluation policy, class time-table etc.

3. If you enroll in MS&E 317, you will have to do different HWs, exams etc. from students in MS&E 217 and attend one or two special discussion sections.