CS4234 - Optimisation Algorithms

Introduction

Overview (from Dr Seth Gilbert's version of S1 AY 2015/16 - 2 years ago): This course focuses on algorithms for solving optimization (American spelling) or optimisation (British spelling) 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.

Official description: This module covers common algorithmic techniques for solving optimisation problems, and introduces students to approaches for finding good-enough solutions to NP-hard problems. Topics covered include linear and integer programming, network flow algorithms, local search heuristics, approximation algorithms, and randomized algorithms. Through analysis and application of the techniques to a variety of canonical problems, students develop confidence to (i) appropriately model a given optimisation problem, (ii) apply appropriate algorithmic techniques to solve the problem, (iii) analyse the properties of the problem and candidate algorithms, such as time and space complexity, convergence, approximability, and optimality bound.

Note: This introductory message will not be prominent the next time you visit this URL again. This behavior is normal. You can view it again by scrolling to the top of this page.

Course Registration

The expected number of CS4234 students for Semester 1 (S1) AY2017/2018 should be similar to the past 2 AYs: ~40 students.

Useful information to help you decide on whether you should register for CS4234 (see CS4234 in nusmods.com, no review though) in S1 AY 2017/2018:

1. It will be Steven's second iteration. The first iteration went relatively well and many known weaker spots from the first iteration will be improved in the second iteration. Steven did his PhD thesis around this topic more than ~13 years ago (2004) and teaching the first iteration last year (2016) has refreshed his own knowledge of this topic. VisuAlgo is currently being enhanced to include some NP-hard/complete topics too by the TA of this module (Rais). Hopefully the second iteration will run at least equal or even better than the first iteration :).
2. Teaching staffs:
   (Senior) Lecturer: Dr Steven Halim, the key man behind VisuAlgo that will be used with increasing importance in some of CS4234 lectures.
   His 'Dr' title was obtained after ~6 years working on NP-hard Combinatorial Optimization Problems (2004-2010)...

   Teaching Assistant (TA): Muhammad Rais Fathin Mudzakir, our main coder in recent ACM ICPC World Finals 2017.
   Machines, e.g. Mooshak, VisuAlgo, and Kattis will continue be used to help Steven run this module...

   Rating (out of 5.00)	Aug-Nov 2017 (n=??/33?)	Aug-Nov 2016 (n=23/40)
   Module feedback	Hopefully ▲	4.00 (slightly above CS dept average)
   Module difficulty	Hopefully ▼ just a bit	4.13 (slightly harder than CS dept average)
   Steven's teaching	Hopefully ▲	4.53 (above CS dept average)

Syllabus

Steven will improve his second iteration of CS4234 with the following updated lesson plan (initially derived from Dr Seth Gilbert's version of S1 AY 2015/16 but has branched out since then):

• Part 1 (about 4 weeks): Introduction to Combinatorial Optimization:
  1. Some NP-hard optimization problems: Min-Vertex-Cover (2 variants, both are available @ VisuAlgo), Max-Clique, Min-Set-Cover, Steiner-Tree (3 variants), Traveling-Salesman-Problem (4 variants, one is available @ VisuAlgo), and a few others
  2. Current Approaches: Special Case(s), Small Instance/Parameterized Solution(s), Approximation Algorithm(s), and one more at Part 3
  3. Techniques Covered: (Clever) Brute Force/Complete Search, Dynamic Programming, Greedy Algorithm, Approximation Algorithm, Linear Programming, Integer Linear Programing (with relaxation)
• Part 2 (about 4 weeks): Network Flows and Matching:
  1. Problem Definition and Basic Algorithm: The Ford Fulkerson's Algorithm
  2. Analysis of various Augmenting Path heuristics for Ford Fulkerson's Algorithm, some have Max Flow Visualization @ VisuAlgo
  3. The Push-Relabel Algorithm
  4. Graph Matching Algorithms, especially the (Basic) Bipartite Matching Visualization @ VisuAlgo
• Part 3 (about 4 weeks): (Meta-)Heuristics/(Stochastic) Local Search:
  1. Techniques Covered: Gradient Descent/Hill Climbing, Simulated Annealing, Tabu Search, Iterated Local Search, etc
  2. Trip to the Past: Discussing Steven's past PhD Thesis about Optimization Algorithms (2004-2010): SLS Design and Tuning Problem
• Throughought this module:
  1. Lots of Proofs :O (but we will skip some complicated one-time proofs in class if they become too dry but the details are in the lecture notes)
  2. Implementation of (some of) these advanced optimization algorithms (via help of Online Judge) and their empirical analysis (especially for Part 3)

Course Registration Additional FAQ

If you have any important questions regarding this module, email stevenhalim at gmail dot com. Relevant answers will be posted here to reach wider audiences.

Q: Will this module be graded using Bell curve?

A: With ~40 students, a kind of weaker Bell Curve system will be used, which Steven used last AY...

Q: Will this module flocked by students who have (very) good CS3230 grades?

A: Not 100% true, but indeed many of the first iteration students have reasonably strong interest in algorithm (thus reasonably good CS3230 grades and also good grades on previous related algorithm modules)

Q: How different will your version be compared to last year (AY 2016/17) version?

A: The second iteration will improve on the relatively successful first iteration. However, as Steven teaches about 'local search' in this module that emphasizes minor changes if the (local) search is already near a local (not necessarily global) optima, he will only do these minor local changes: (Slightly) less coding, (slightly) better proof presentation, (slightly) less competitive than the first iteration.

Q: Will there be some form of coding in this course?

A: The lecturer is (or was?) a competitive programmer. So yes, there will be implementation side of the various optimization algorithms that we discuss in class. You will implement real algorithms to attack real NP-hard optimization problems throughout this module.

Q: Do I have to buy any textbook for this course?

A: My Competitive Programming book, the CP3.17b edition (actually for CS3233) can be a good book for a small subset of the topics (especially the implementation side). But in CS4234, we will also discuss NP-hard problems that do not have efficient solutions (started to be covered a bit in CP3.17b edition and will be expanded a bit more by CP4). Introduction to Algorithms (by CLRS, the typical textbook used in CS3230) and Algorithm Design (by Kleinberg and Tardos) are also recommended. Steven will also try to continue expanding Seth's initial LaTeX-style lecture summary that was already available for the Part 1 of the class but not yet available for Part 2-3 of the class.

Note: This course registration section will not be prominent from Week 02 onwards (after the first lecture). This behavior is normal. You can view it again by scrolling to the top of this page.

News Show All

Lesson Plan

Class Roster

Steven uses a small-scale gamification system in his version of CS4234 for extra study motivation.
The list of possible achievements are as follows: (achievements highlighted with red color/green color are already completed in the past/being given, respectively)

1. MPE: Given to students who got CS4234 via MPE (21 July 2017), i.e. the early birds...
2. Bid (Round): Given to students who bid CS4234 via CORS (late July-early August 2017) instead of MPE-ing it during early July 2017 (closed after round 3B; Master/PhD student do not have to bid but will be classified here anyway)
3. I Say Hi: Given to students who reply Steven's first email regarding their reasons for taking CS4234 (sent on Monday, 07 August 2017, 3.50pm); It will help Steven in planning the second iteration of this module (closed after the first lecture)
4. In FB: Given to students who are already in CS4234 FB group (closed after tutorial 01)
5. Kiasu (#): Given to the first 7 students who solve all subtasks of PS1-Art Gallery+
6. Spanning Tree Master (#): Given to the first 7 students who solve all subtasks of PS2-Rubble+
7. Mini Researcher (#): Given to the top 7 students who are judged to have the best PS3 (written) submission on certain topic
8. Test Master (#): Given to the top 7 students who have the highest Midterm Test scores
9. Flows Like Water (#): Given to the first 7 students who solve all (different) tasks of PS4-Flows
10. Active in Class (Reason): Given to the top 3 students per tutorial group who participated the most in our first 9 tutorial classes (Given on Week 11, these students will get full 5% tutorial participation points, the rest will fight for 4, 3, 2, 1% tutorial participation points)
11. Future Algorithm Researcher: Given to top 3 project groups who perform well in their mini project.
12. Nowhere to Hide (Reason): Given to students who already remembered by Steven; These students can choose to hide their matric cards during CS4234 official assessments and Steven will allow them to do so