Stanford University
MS&E 217, Combinatorial Optimization

Autumn 2003-04

 

Home | Handouts | General Information

 

General Information

 

Aim

 

Introduces the use of combinatorial and algorithmic techniques for optimization problems. Emphasis on algorithms with provable correctness and efficiency. Illustrates the use of these techniques for several real-world applications.

 

Topics

 

Running time analysis, dynamic programming, trees and paths, flows and matchings, primal-dual algorithms, NP-completeness, approximation algorithms.

Textbooks

 
  1. Combinatorial Optimization, by W. J. Cook, W. H. Cunningham, W. R. Pulleybank and A. Schrijver. Publisher: JohnWiley and sons, Inc. (Required)
  2. Introduction to Algorithms (2nd Edition), by T. H. Cormen, S. Clifford, C. E. Leiserson and R. L. Rivest. Publisher: The MIT Press. (Supplement)  This book is available from Stanford machines online.

Pre-requisites

 

CS 106 A,B, or prior programming experience

Tentative list of sections from the text

 

1.2, 2, 3.1-3.3, 4.1,4.3, 5.1-5.2, 9.1-9.6, 9.8, 7.2
Additionally, there will be lectures on dynamic programming that shall cover material not in the text.

Evaluation Criteria

 

There will be 5 HWs, a special assignment, a midterm, and a final. The HWs are worth 30%, the special assigment worth 10%, the midterm 25%, and the final 35%. The final will be comprehensive, i.e., it will include everything covered in class. We will consider only the best 4 HWs, and you will automatically have one late day that you can use for any one HW. The special assignment will be a choice between a small programming project or a theory problem set.

Homeworks, collaboration policy, additional excercises

 

No collaboration is allowed on the HWs.

From time to time, optional excercises will be suggested in class or on the handouts page. These do not need to be turned in–they are meant to aid your understanding of the material.

Exams

 

The mid-term will be 70 minutes,  in-class mid-term on Mon Nov 3rd.
The final will be 2 hours, on Wed Dec 10th from 9:00-11:00.

Contacting the Instructor

 

If you have any doubts about the material taught in class, we recommend that you drop by during office hours. If the office hours turn out to be very crowded, we will schedule additional office hours as and when needed, or make special appointments.