|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.
|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 Maximum-Flow / Minimum Cut|
|6||15/09||Analyzing the performance of Ford-Fulkerson: Fattest-Path, Capacity Scaling|
|Break||23/09||No class: Mid-semester break|
|7||30/09||The Push-Relabel Algorithm|
|Part 3: Continuous Optimization|
Gradient descent and logistic regression
|10||20/10||Meta-heuristics 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 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.
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 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:
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 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.
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.