CS4234 - Optimisation Algorithms


Overview (from Dr Seth Gilbert's version of S1 AY 2015/16 - many AYs 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 course 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

CS4234 class size average in the past 7 AYs is ~36 pax. We will go full F2F throughout this sem (except on week 03 and 13 when Prof Halim is known to be away).

Useful information that has been used by current students to decide on whether they should register for CS4234 (see CS4234 in nusmods.com) in S1 AY21/22:

  1. It is Prof Halim's eight iteration. From AY 2016/17 until the present, he has received teaching feedback ratings from 4.1 (average, just one iteration) to 4.7 (very good) out of a maximum of 5.0 for these offerings, with a running average rating of 4.504 (very good). Prof Halim did his PhD thesis around this topic more than one decade ago (2004-2010) and teaching the first iteration back in 2016 has refreshed his own knowledge of this topic. Back in 2017, VisuAlgo started to have some NP-hard/complete visualization topics created by the 2017 TA of this course (Muhammad Rais) and currently being extended by the 2023/24 FYP students (Ng Wee Han and Radian Krisno). Hopefully the eight iteration runs well again.
  2. Teaching staffs:

    Associate Professor Steven Halim, the key man behind VisuAlgo that will be used with increasing importance in some of CS4234 lectures. Prof Halim is working towards fully flipping almost every modules that he teaches and there will be more flipped components (not all) in this course this semester... PS: His 'Dr' title was obtained after ~6 years working on (visualizations of local search algorithms on) NP-hard Combinatorial Optimization Problems (2004-2010)...

    Teaching Assistants (TAs): Past CS4234 students Lee Zheng Han (T1, 21 pax and T2, 16 pax) and Teoh Jun Jie (T3, 20 pax).
    Prof Halim does not run any tutorial session this time.

    Machines, e.g., VisuAlgo and Kattis will continue be used to help Prof Halim run this course...

    (out of 5.0)
    Aug-Nov 23
    ≥ 53%
    Aug-Nov 22
    Aug-Nov 21
    Aug-Nov 20
    Aug-Nov 19
    Aug-Nov 18
    Course feedback (SoC avg ~3.8) ≥ 4.2 (target) 4.3 4.5 (PB) 4.1 (C-19+IOI20) 4.2 (> avg) 4.3
    Course difficulty (SoC avg ~3.8) ≤ 4.3 (ok let's limit to this) 4.3 == 4.3 4.4 (C-19+IOI20) 4.2 == 4.2
    Prof Halim's teaching (SoC avg ~4.1) ≥ 4.3 (target) 4.5 == 4.5 4.1 (C-19+IOI20) 4.7 (PB) 4.6 ==


For this iteration of CS4234, Prof Halim uses the following lesson plan (initially derived from Associate Professor Seth Gilbert's version of S1 AY15/16 but has significantly branched out since then). Also in S1 AY 2023/24, Prof Halim is trying to push even more 'flipped classroom' components in CS4234:

  • Part 1 (about 4 weeks: Wk01-04): (Combinatorial) Optimization Problems:
    1. Some NP-hard (Combinatorial) Optimization Problems. These are the ones to be officially discussed in lectures:
      1. Min-Vertex-Cover (2 variants, both are available @ VisuAlgo),
      2. Min-Set-Cover (not yet in VisuAlgo),
      3. Steiner-Tree (3 variants, the General-Steiner-Tree variant is available @ VisuAlgo),
      4. Traveling-Salesperson-Problem (4 variants, one is available @ VisuAlgo),
      5. plus a few others in tutorial/PSes/mini projects (Prof Halim has one FYP student who has completed CS4234 before working on a few more visualizations starting from Aug 2023)
    2. Current Approaches: Special Case(s), Small Instance/Parameterized Solution(s), Approximation Algorithm(s), and one more at Part 3 below
    3. Techniques Covered: (Clever) Brute Force/Complete Search, Dynamic Programming, Greedy Algorithm, Approximation Algorithm, Linear Programming, Integer Linear Programing (with relaxation)
  • Part 2 (about 3 weeks+1 recess week: Wk05-07, plus the last Wk13): Network Flows and Matching:
    1. Problem Definition and Basic Algorithm: The Ford-Fulkerson Algorithm (faster analysis)
    2. Analysis of various Augmenting Path heuristics for Ford-Fulkerson Method, three variants have Max Flow Visualizations @ VisuAlgo
    3. The Push-Relabel Algorithm
    4. Graph Matching Algorithms, especially the Unweighted Bipartite Matching Visualization @ VisuAlgo
    5. Harder Graph Matching applications/algorithms: Kuhn-Munkres (not yet in VisuAlgo) and Edmonds' Matching Algorithms (in VisuAlgo; but still in raw form)
  • Part 3 (about 4 weeks: Wk09-12): (Meta-)Heuristics/(Stochastic) Local Search:
    1. Techniques Covered: Gradient Descent/Hill Climbing, Simulated Annealing, Tabu Search, Iterated Local Search, etc
    2. A Trip to the Past: Discussing Prof Halim's past PhD Thesis about Optimization Algorithms (2004-2010): SLS Design and Tuning Problem
  • Throughought this course:
    1. Many 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/tutorial reference answers)
    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 course, email dcssh at nus edu sg. Relevant answers will be posted here to reach wider audiences.

Q: Will this course be graded using Bell curve?
A: Historically, with average of ~36 students in the past 7 AYs, Prof Halim usually does not have to (strictly) follow Bell Curve system for CS4234...
Q: Will this course flocked by students who have (very) good CS3230 grades?
A: Experience from past AYs tell Prof Halim that the answer is not 100% true, but indeed many students from the earlier iterations have reasonably strong interest in algorithm (thus reasonably good CS3230 grades and also good grades on previous related algorithm modules).
Q: Will this course flocked by students who have taken CS3233?
A: In recent AYs, there is an increasing trend that a fraction of Prof Halim's past CS3233 students (strong experience with the implementation parts of this CS4234 course) are now taking CS4234 too (the reverse is actually rarer as CS4234 is coded as a level 4 course and CS3233 is coded as a level 3 course).
Q: Is this course suitable for (advanced) exchange students?
A: In recent AYs, Prof Halim also recognizes that there are always a few (suitable) Exchange students taking this course. With COVID becoming endemic, Prof Halim continues to expect a few (suitable) Exchange students to join the class.
Q: How different will this year's (AY 2023/24) version be compared to last seven years (2016 until last year) versions?
A: CS4234 course feedback rating is already at ≥ 4.3 in the last two AYs (SoC avg is 3.8), i.e., the setup is already good. Therefore, most elements will be kept constant and only a small local changes will be implemented:
  1. Prof Halim reduces the weightage of the two-weeks Problem Sets (it is too difficult to fight ChatGPT/generative AI...) and replace the reduced weightage with a NEW VisuAlgo Online Quiz.
  2. return of Push-Relabel algorithm (as there is no Public Holiday on Thursday this semester) -- slotted at the back of the semester (Week 13, now live , as recorded lecture, as Prof Halim is away again on Week 13 this time),
  3. further reduce the competition level one notch compared to the last seven iterations,
  4. a bit more of basic stuffs delegated to VisuAlgo e-Lecture (to make this course more into flipped classroom),
  5. continue refining the more interesting Graph Matching topics: Kuhn-Munkres and Edmonds' Matching Algorithm,
  6. there will be two weeks (Week 03+13) just one week where Prof Halim himself is the one who is away (IOI 2023 on Week 03 and the combo ICPC World Finals 2022+23 on Week 13).
Q: Will there be some form of coding in this course?
A: The lecturer is was a competitive programmer, has written a book (now two separate books) about it, and manages various programming competitions in SoC/Singapore/Worldwide :O. So yes, there will always 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 course. See CPbook Methods to Solve, CS4234 related stuffs. Warning: Some of these (NP-)hard optimization problems discussed in class are time limit-critical... so students who can only code in Python will be at strong disadvantage at a few programming exercises. Java coder is still somewhat affected (but will 99% able to also solve the programming exercises with the same algorithm or different algorithm but similar time complexity). C++ coder is preferred.
Q: Do I have to buy any textbook for this course?
A: My Competitive Programming book: CP4, Book 2 (last few stock at NUS Central Library co-op or @ SIMCC e-Store (31.9 SGD nett, no shipping cost) and @ lulu.com (22.99 USD+shipping cost+10-14 days of shipping), or the e-book (PDF) version @ lulu.com) (actually for CS3233), can be a good book for about two-thirds of the course topics (especially the implementation side) of CS4234 (Pre-requisites topics, Network Flow, Graph Matching (including some of the rare ones), small or special-cases of NP-hard/complete problems). Introduction to Algorithms (by CLRS, the 3rd or new 4th edition, the typical textbook used in CS3230) or Algorithm Design (by Kleinberg and Tardos) are also recommended. There are two other books that Steven use: the rare-and-hard-to-find Stochastic Local Search: Foundations and Applications book and an optional The Golden Ticket book.

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.


Date News

Lesson Plan

Week Tutorial
Cells with course material that have not been updated are highlighted with pink color, past classes more than one week ago are hidden so that we can focus on the current and future classes, but you can restore them by clicking 'Show Past' button above, future classes are not highlighted
Has Not Started Has Not Started, Please revise your CS1010+CS2040+CS3230
PS: If you are the few to have taken CS3233 before,
revise Max Flow, Matching, and NP-hard/complete
that we have discussed in CS3233 before

Out on Wed, 02 Aug 2023, 08.00am
(4 'compulsory' tasks A+B+C+D)
(4 more 'extra challenge tasks' E+F+G+H)
nus.kattis will help Prof Halim + TA(s) check your code
PS1 only contains problems that can be solved
with just CS1010+CS2040+CS3230 knowledge,
namely: Greedy, DP, SSSP/APSP, MST,

If you struggle to solve the first 4 tasks,
it is a sign that maybe CS4234 is not for you (yet)

Btw, to show Prof Halim that you are very ready,
simply solve all 8 tasks.
Has Not Started
Has Not Started, Please continue revising your CS1010+CS2040+CS3230

Continue attempting PS1 (hints in class Discord)

Singapore National Day on Wed, 09 August 2023
This time, CS4234 first lecture is not affected
PS1, continued
Has Not Started Introduction and Min-Vertex-Cover

Pre-reading material:
CP4 Book 2, Chapter 8.6.6 (Min Vertex Cover)
MVC @ VisuAlgo (the unweighted version)
Understanding Unsolvable Problem
Extra Material: The Golden Ticket, Chapter 1-6

Slides used in the flipped classroom:
00.Introduction.pdf (2023)
Administrative stuffs for the S1 AY 2023/24 edition
01.VertexCoverLecture.pdf (2021)
(Re)-Introduction to the Min-Vertex-Cover problem (CS3230 review)
The important 3C2 idea
MVC Online Quiz (easy, still many static questions)
PS1, continued
Has Not Started Approximation Algorithms

Pre-reading material:
Week 01 material (especially if you were absent on Week 01), plus:
CP4 Book 2, Chapter 8.6.6 (Min Weight Vertex Cover)
CP4 Book 2, Chapter 9.32 (Linear Programming)
MVC @ VisuAlgo (now the weighted version)
Extra Material: The Golden Ticket, Chapter 6

Slides used in the flipped classroom:
02.ApproximationLecture.pdf (2023)
Approximation Algorithms for M(W)VC
Introduction to (Integer) Linear Programming + Relaxation
The Min-Weight-Vertex-Cover problem + its approximate solution
Extra Material: 02.ExcelSample.xlsx, lp_solve tutorial,
Simplex code in C++ or Java
Or linprog-simplex in Python scipy
MVC Online Quiz (medium, still many static questions)

Prof Halim departed to Europe
a few hours after this lecture 02.
PS2-NP-hard 1
Out on Sat, 26 Aug 2023, 08.00am

PS1 due
on Sun, 27 Aug 2023, 11.59pm (4%)

Do not forget to decide whether CS4234
is for you (or not) by end of this Week 02...
28 Aug-
01 Sep
The Intro COP: Min-(Weight)-Vertex-Cover
2 More COPs:
PS1 Debrief
Prof Halim was in Szeged, Hungary,
for IOI 2023 (28 Aug-04 Sep 2023)
Prof Halim has recorded lecture 03a + part of 03b.

Min-Set-Cover and Steiner-Tree

Pre-reading material:
CP4 Book 2 Chapter 8.6.7 (Set Cover) + 8.6.10 (Steiner Tree)
No Min Set Cover visualization @ VisuAlgo yet :'(...
Steiner Tree @ VisuAlgo (the general/graph version)
Steiner Tree Online Quiz (medium, one question type only)

Slides used in the [RECORDING]:
03a.SetCoverLecture.pdf (2023)
Another Combinatorial Optimization Problem (COP): Min-Set-Cover
03b.SteinerTreeLecture.pdf (2023)
Yet another COP: Steiner-Tree (3 variants)
PS2, continued
4 More COPs:
PS2 Overview

Pre-reading material:
CP4 Book 2 Chapter 3.5 + 8.6.3 (TSP)
TSP @ VisuAlgo (1.5-approx has a 'bug')
Extra Material: Someone made a movie out of this: Trailer, Movie website
The plot is similar to The Golden Ticket, Chapter 2.

Slides used in the flipped classroom:
Quickly finish 03b.SteinerTreeLecture.pdf (2023) first
04.TSPLecture.pdf (2021)
Going deeper on this classic Travelling-Salesperson-Problem
TSP Online Quiz (medium, still many static questions)
PS2 due
on Sat, 09 Sep 2022, 07.59am (4%)

PS3-NP-hard 2+Flows 1
Out on Sat, 09 Sep 2022, 08.00am
This one runs for 2.5 weeks
3 More COPs:
PS3 Overview

Pre-reading material:
CP4 Book 2 Chapter 8.4 (Network Flow)
Max-Flow Visualization @ VisuAlgo (Slide 1-7)
Before attending the class, at least read Overview and Motivation,
Flow and Residual Graph (and their technical definitions), and
test run FF/EK/Dinic's on some Example (flow) Graphs in VisuAlgo

Slides used in the flipped classroom:
05.MaxFlowLecture.pdf (2022)
Introduction to Max-Flow Problem and its applications (using a random flow graph)
Ford-Fulkerson Algorithm (a quick demonstration on that random flow graph)
Max-Flow/Min-Cut Theorem (the hard one, the focus of the lecture)
Analyzing the performance of Ford-Fulkerson (quick analysis)
Better FF algorithms analysis: Edmonds-Karp + Dinic's Algorithm (follow up in T04)
Max Flow Online Quiz (Medium)
Live solve one simple max flow problem
PS3, continued
Back to a P optimization problems: Max-Flow
Edmonds-Karp vs Dinic's discussion and analysis
Alternative Ford-Fulkerson analysis

Pre-reading material:
CP4 Book 1 Chapter 3.4 (Greedy Bipartite Matching)
CP4 Book 1 Chapter 4.6.3 (Bipartite Graph)
CP4 Book 2 Chapter 8.5 (Graph Matching)
CP4 Book 2 Chapter 8.6 (special cases of some NP-hard problems)
CP4 Book 2 Chapter 9.26 (Hopcroft-Karp Algorithm)
Graph Matching Visualization @ VisuAlgo (Slide 1 to 4-21)
Before attending the class, at least read Overview and
skim through the various MCBM Algorithms
then test run Augmenting Path algorithm (3 variants)
on some Example (Bipartite Matching) Graphs in VisuAlgo

Slides used in the flipped classroom:
06.MatchingLecture1.pdf (2022)
Introduction to (Weighted) Max-Cardinality-(Bipartite)-Matching Problem
Week 06 focus: MCBM and its applications
Max-Flow, Augmenting Path Algorithm Plus, Hopcroft-Karp/Dinic's Algorithm
Matching Online Quiz (Medium)
Live solve one MCBM-related problem
PS3, continued
Recess Week, 23 Sep-01 Oct 2023
We can take a break this week :)
But only if you can finish PS3 earlier...
and choose not to start PS4 early...
PS3 due
on Wed, 27 Sep 2023, 07.59am (4%)

PS4-Flows 2+Matchings
Out on Wed, 27 Sep 2023, 08.00am
This one runs for 3 weeks
Assignment-Problem (Max-Flow vs MCBM version)
Greedy MCBM
Application of MCBM (or Max-Flow) on 2 (or 3) NP-hard COPs
Berge's theorem (revisited/optional)

Pre-reading material:
CP4 Chapter 4.6.3+8.5+8.6+9.26 again, plus
CP4 Book 2 Chapter 9.25 (Min Cost (Max) Flow)
CP4 Book 2 Chapter 9.27 (Kuhn-Munkres Algorithm)
CP4 Book 2 Chapter 9.28 (Edmonds' Matching Algorithm)
Hungarian Method visualization @ TUM
Graph Matching Visualization @ VisuAlgo (for Unweighted MCM)

Slides used in the flipped classroom:
07.MatchingLecture2.pdf (2021)
The 'harder' matching problems/algorithms
Week 09 focus: Weighted MCBM (MCMF or Kuhn-Munkres/Hungarian),
Unweighted MCM (Edmonds' Matching) --- high level tour,
Weighted MCM (small graph/DP bitmask),
Wrapping up Graph Matching Topic
PS4, continued
T06 (reference answers are NOT uploaded)
Midterm test preparation
Prof Halim has the reference answers for all past midterm papers.
(but we will scope our discussion to the recent 3 AYs only).
(TAs will run out of time otherwise).
The plan is for the three tutorial groups
to discuss three different papers.
T1/2/3 will discuss AY22/23, 21/22, and 20/21, respectively.
You can attend ≥ 1 tutorial groups if you want.
Midterm Test [ONSITE, F2F] (25%)
Material: Week 01-06, up to Matching Lecture part 1
Excluding Matching Lecture part 2 (only discussed on Week 07)
Including stuffs from PS1-3 plus the first 2 tasks of PS4
Including stuffs from Tut01-06 notice the inclusion of Tut05+Tut06
Open book+Open laptop (no restriction other than airplane mode)
That is, this test is strictly NOT Open Internet
Prof Halim will only print 1/3 * N questions papers (the rest, read the PDF)
Prof Halim will print N answer sheets
You will write-down your answers on printed answer sheets
You will only hand-in the answer sheets at the end.

Midterm Test Past Papers (recent 3 AYs+ours only):
Midterm test paper (S1 AY 2020/21),
Midterm test paper (S1 AY 2021/22),
Midterm test paper (S1 AY 2022/23),
Midterm test paper (S1 AY 2023/24) — our paper.
PS4, continued
Midterm test debrief
Weighted MCBM: Hungarian tracing
One weighted MCBM problem
Another Optimization Problem involving matching
Stochastic-Local-Search (2016)
[not flipped-classroom]:
Introduction to Stochastic Local Search (SLS)
Paradigm change, SLS Characteristics,
No proof, just experiments...

Last 15m: NEW for 2023 - VisuAlgo CS4234 Online Quiz (9%)
Approx time window: [1.17-1.35pm] (18 Qs, 18 mins).
Bring your own laptop that can run at least 18 minutes on battery power.
(we do not provide any spare laptop).
Material: /sssp, /mst, /maxflow, /matching, /mvc, /steinertree, /tsp,
and of course the rest are 'new' questions.
PS4 due
on Thu, 19 Oct 2023, 07.59am (4%)

Mini-Project - Local Search
Out on Thu, 19 Oct 2023, 12 noon
Proper launch during Lecture
13 project groups of size 4 + last group 14 of size 5

Overview of Mini-Project
Discussion about Stochastic Local Search
Using Mini Project topics as the context
Past Paper discussion round 1
Meta-heuristics (2016)
[not flipped-classroom]:
Discussions of a few, more-sophisticated SLS algorithms
Simulated Annealing, Tabu Search, Iterated Local Search, Evolutionary Algorithms, etc...
Highlight on the need of tuning certain parameters of those SLS algorithms...

NUS Online Teaching Feedback opens this Fri
But this timing is too early for our course...
You can wait until the end of Mini-Project
Mini-Project, continued
30 Oct-03 Nov
Discussion about SLS, continued
Past Paper discussion round 2
Its applications for your Mini Project

First round of "Active in Class" achievement is given this week
Given to the most present+most active students in each Tutorial Group
SLS-DTP.pdf (2016)
SLS Design and Tuning Problem (DTP)
Designing SLS algorithm; Doing (Parameter) Tuning;
Fitness Landscape and Search Trajectory Analysis
Example on another NP-hard COP: Quadratic-Assignment-Problem
qap_a-ro-ts-i.avi, qap_a-ro-ts-a.avi, qap_b-ro-ts-i.avi, qap_b-ro-ts-b.avi, QAP_FL_Demo.exe
Invitation to do PhD in algorithm... :)
Prof Halim's PhD Thesis: 2004-2010 is downloadable from NUS ScholarBank
Mini-Project, continued
06-10 Nov
Mini Project, last discussion
Past Paper discussion (last) round 3
Final class photo

"Active in Class" achievement is finalized this week
(2nd or even 3rd most talkative students in each TG to be identified)

Tutorial Participation Marks given (5%)
Mini Project Presentations
Mini Project Presentations and Q&A Segment
(Details in the Canvas announcement)
Course review
Reminder about Teaching Feedback
Official class onsite photo at COM3-01 MPH123

Fri, 10 Nov 2023 is chosen as
NUS well-being day S1 AY 2023/24

Prof Halim will depart to Sharm el-Sheikh, Egypt,
on Sat, 11 Nov 2023 night

WF22+23 is postponed again... due to war...
Mini-Project due
on Thu, 09 Nov 2023, 11.59am (10%)
Before the last onsite lecture
13-17 Nov
Sun, 12 Nov 2023 is Deepavali PH
Thus, Mon, 13 Nov 2023 is also a PH
CS4234 last tutorial is cancelled
Prof Halim will be in Sharm el-Sheikh, Egypt,
for combo ICPC World Finals 2022+2023 (12-17 Nov 2023)

WF22+23 is postponed again... due to war...
Prof Halim plans to just run Push-Relabel lecture here.

Pre-reading material:
CP4 Book 2 Chapter 9.24 (Push-Relabel Algorithm)
No Push Relabel visualization @ VisuAlgo yet :'(...

Slides used in the traditional... classroom:
12.PushRelabel.pptx (2023)
Introducing the Push-Relabel Algorithm
Sample (manual) execution
Analysis of Basic Push-Relabel Algorithm
No more assignment :)
Study Week, 18-24 Nov 2023

Final Assessment Consultations (per request)

Final Assessment Past Papers (recent 3 AYs only):
Final paper (S1 AY 2020/21),
Final paper (S1 AY 2021/22),
Final paper (S1 AY 2022/23, without the MCQs),
Final paper (S1 AY 2023/24, without the MCQs, our paper)

NUS Online Teaching Feedback System closes on Friday of Study Week
Final Assessment (35%)
Date and Time: Thu, 30 Nov 2023, 9-11am
Venue: MPSH4
Open book but *not* Open Laptop (prepare accordingly)
42% MCQs (extremely tricky)
(the MCQs are there to speed up grading as Prof Halim has other final assessments
on 01 Dec (128 pax), ICPC Asia Jakarta (01-04 Dec), and 07 Dec (201 pax))
The other 58% are split into three essay questions (end up not easier than our midterm)