CS 4234 - Optimization

(Fall 2015)

NUS School of Computing

Prof. Seth Gilbert

Tuesday 12:00pm - 2:00pm



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. Mini-project information posted. E-mail 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 1-3 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 NumberDateDescription
Part 1: Introduction to Combinatorial Optimization
111/08Introduction and logistics. The vertex cover problem.
218/08Introduction to linear programming. Weighted vertex cover.
  • Lecture 2 notes (pdf) [Download]
  • Problem Set 2 [Download]
  • Problem Set 2 Solutions [Download]
  • Interesting papers:
    • Smoothed analysis (and why Simplex is almost always fast in practice).
    • A more accessible general interest article on smoothed analysis: here
    • There are some simplex-like algorithms that are polynonial time. This one uses something called the shadow vertex method.
325/08Set Cover and Steiner Trees
  • Set cover notes (pdf) [Download]
  • Steiner tree notes (pdf) [Download]
  • Problem Set 3 [Download]
  • Problem Set 3 Solutions [Download]
  • Tutorial Questions Week 3 [Download]
  • IVLE Questions Answered [Download]
  • Interesting papers:
    • How do you implement algorithms for set cover on very large data sets? See this paper here.
401/09The Travelling Salesman Problem.
Part 2: Network Flows and Matching
58/09Introduction to Maximum-Flow / Minimum Cut
615/09Analyzing the performance of Ford-Fulkerson: Fattest-Path, Capacity Scaling
Break23/09No class: Mid-semester break
730/09The Push-Relabel Algorithm
  • Lecture notes (handwritten) [Download]
  • Week 7 tutorial questions (from old midterms/exams) [Download]
  • Week 7 IVLE questions answered [Download]
806/10Midterm exam
  • Midterm [pdf]
  • Midterm solutions [pdf]
Part 3: Continuous Optimization
913/10 Gradient descent and logistic regression
  • Lecture notes (handwritten) [Download]

Mini-Project information:

1020/10 Meta-heuristics and more: Metropolis, Simulated annealing, Tabu search, and finding a minimum degree spanning tree.
Part 4: The Primal Dual Method
1127/10 Linear Programming Duality
  • Lecture notes on linear programming duality (beginning on page 12), including a review of some material from Week 2 and a preview of Week 12 (handwritten) [Download]
  • Tutorial questions [Download]
123/11 The Primal Dual Method (and applications to weighted vertex cover and maximum weight matchings)
  • Lecture notes on the primal-dual method (handwritten) [Download]
  • Tutorial questions [Download]
1310/11Deepavali (No class)
End of class
1425/11 Final Exam (Evening)
  • Final exam [pdf] and solutions [pdf].
  • Sample final exam from CS5234 2014 [pdf] and solutions [pdf].
  • Sample final exam from CS5234 2013 [pdf] and solutions [pdf].
  • Course Overview


    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 mini-project), a mid-term exam, and a final exam. In determining your final grade, these components will be combined as follows:

    Problem sets / Mini-project 40%

    The last problem set will involve a small project that involves further exploring some of the ideas that we have covered during the class.

    How to do well in the class (without burning out)

    A few tips for doing well in this course without excessive amounts of stress:

    Course Logistics

    Office Hours

    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.

    Problem Sets

    There will be weekly problem sets in the first 2/3rds of the class. (I expect this will end up being 6-7 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:

    Some advice on problem sets:


    There will be one two exams in the course: a midterm and a final. The mid-term 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.

    Academic Integrity

    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.