(Fall 2015)
November 25  Final exam (and solutions) posted.  
November 18  Sample final exams from CS5234 posted.  
November 5  All lectures notes and tutorials for the semester now posted.  
October 20  Lectures notes for Weeks 9 and 10 posted. Miniproject information posted. Email me your project goals soon.  
October 6  Midterm and solutions posted.  
October 1  Notes from Week 7 posted, along with IVLE questions answered. Also, solution sketches for all problem sets are posted.  
September 20  Old midterms from CS5234 (2013 and 2014) posted. Beware that the content covered may not be identical to CS4234 this year.  
September 19  Week 6 lecture notes posted.  
September 19  Week 5 IVLE questions and Week tutorial questions posted.  
September 10  Problem set 5 posted. Lectures notes and tutorial questions for week 5 posted.  
September 5  Solutions to Problem Sets 13 posted.  
September 3  Problem set 4 posted. Tutorial questions from Week 4 posted. Lectures notes from Week 4 on TSP posted.  
September 3  Tutorial questions from Week 3 and IVLE question answers from Week 3 posted.  
August 25  Problem set 3 posted. Lectures notes for Week 3 posted. Please go fill out the IVLE survey before tutorial on Thursday: ask one question!  
August 19  Problem set 2 posted. Lectures notes for Week 2 posted. I also posted some links to interesting papers on the Simplex method.  
August 12  Problem set 1 posted. Lecture notes for Week 1 posted. Please fill out the background survey on IVLE.  
August 11  First class! 
Below is the (very) tentative schedule for the course. I will modify the schedule as the course progresses. Problem sets will be posted below on this schedule as they become available.
Class Number  Date  Description 
Part 1: Introduction to Combinatorial Optimization  
1  11/08  Introduction and logistics. The vertex cover problem. 
2  18/08  Introduction to linear programming. Weighted vertex cover.

3  25/08  Set Cover and Steiner Trees

4  01/09  The Travelling Salesman Problem. 
Part 2: Network Flows and Matching  
5  8/09  Introduction to MaximumFlow / Minimum Cut 
6  15/09  Analyzing the performance of FordFulkerson: FattestPath, Capacity Scaling 
Break  23/09  No class: Midsemester break 
7  30/09  The PushRelabel Algorithm 
8  06/10  Midterm exam 
Part 3: Continuous Optimization  
9  13/10 
Gradient descent and logistic regression
MiniProject information: 
10  20/10  Metaheuristics and more: Metropolis, Simulated annealing, Tabu search, and finding a minimum degree spanning tree. 
Part 4: The Primal Dual Method  
11  27/10  Linear Programming Duality 
12  3/11  The Primal Dual Method (and applications to weighted vertex cover and maximum weight matchings) 
13  10/11  Deepavali (No class) 
End of class  
14  25/11  Final Exam (Evening)

This course focuses on algorithms for solving optimization problems, particularly focusing on combinatorial optimization. These types of problems are ubiquitous, with applications in a multitude of domains. They are used by companies to manage supply chains, retail chains to decide where and when to open new stores, and ports to manage incoming and outgoing cargo containers. In this course, we will cover a variety of powerful techniques for solving these types of problems.
Grades in the course will be based on problem sets (including a miniproject), a midterm exam, and a final exam. In determining your final grade, these components will be combined as follows:
Problem sets / Miniproject  40% 
Midterm  25% 
Final  35% 
The last problem set will involve a small project that involves further exploring some of the ideas that we have covered during the class.
A few tips for doing well in this course without excessive amounts of stress:
For now, office hours are by apointment. Once the semester begins, I'll schedule regular weekly office hours (and update the website here).
To ask me small logistical questions, I prefer that you grab my attention immediately before or after class. For substantive content questions, schedule a meeting with me.
There will be weekly problem sets in the first 2/3rds of the class. (I expect this will end up being 67 problem sets in total.) These problems sets will focus on algorithm questions: solving problems, devising algorithms, proving theorems.
Problems will be graded on a simplistic 0/1/2/3 scale: a 0 indicates minimal understanding (or a problem not completed); a 1 indicates some understanding but many mistakes or poor presentation; 2 indicates a satisfactory answer; a 3 indicates a perfect answer that goes beyond expectations. You should expect to get a 2 on most problems.
The following rules will help keep the problem set submission and grading process running smoothly:
Do not compare or share your solution with others.
Some advice on problem sets:
There will be one two exams in the course: a midterm and a final. The midterm exam will be held in class on October 6. The final exam will be held on November 25. The final exam will be graded and returned to you by the end of the semester.
I take academic integrity seriously. To repeat the problem set instructions from above: the solutions you submit must be your own unique work. Any cases of cheating will be dealt with harshly: a first offense will result in at least a one letter grade deduction for the module (or potentially a zero for the entire module, depending on the severity). When in doubt, ask me what is allowed.