# CS4234 - Optimisation Algorithms

## Introduction

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 6 AYs is ~35 pax. We will go full F2F throughout this sem (except on the first and last weeks when Steven 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 Steven's seventh iteration. The first six iterations were reasonably good (5 of them) or average (1 of them). Steven 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). Hopefully the seventh iteration runs well again (last AY's 6th iteration was the Personal Best for the course feedback so the setup is working) :).
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. Steven 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 Assistant (TA): Audrey Felicio Anwar (took CS4234 last AY, A), Steven runs one tutorial session and Audrey takes the other two tutorial sessions.

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

Rating
(out of 5.0)
Aug-Nov 22
(n=27/43)
63%
Course feedback (SoC avg ~3.9) 4.3 (but as per target)
Course difficulty (SoC avg ~3.8) 4.3 == (fail to reduce diff)
Steven's teaching (SoC avg ~4.2) 4.5 == (more than target)

### Syllabus

For the sixth iteration of CS4234, Steven uses the following lesson plan (initially derived from Dr Seth Gilbert's version of S1 AY15/16 but has significantly branched out since then). Also in S1 AY 2022/23, Steven is trying to push more 'flipped classroom' components in CS4234:

• Part 1 (about 4 weeks): (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-Salesman-Problem (4 variants, one is available @ VisuAlgo),
5. plus a few others in tutorial/PSes/mini projects
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 4 weeks+1 recess week): 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 Algorithm, some have Max Flow Visualization @ 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): (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 Steven's past PhD Thesis about Optimization Algorithms (2004-2010): SLS Design and Tuning Problem
• Throughought this course:
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/tutorial modal 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 stevenhalim at gmail dot com. Relevant answers will be posted here to reach wider audiences.

Q: Will this course be graded using Bell curve?
A: Historically, with average of ~35 students in the past 6 AYs, Steven usually do not have to 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 Steven 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 Steven'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, Steven also recognizes the growing number of exchange students taking this course. SEP should have resumed for S1 AY 2022/23, thus Steven is expecting some Exchange students to join the class.
Q: How different will this year's (AY 2022/23) version be compared to last six years (2016 until last year) versions?
A: Last year, CS4234 course feedback rating reached its personal best (4.5 out of 5.0), i.e., the setup is already good. Therefore, most elements will be kept constant and only a small local changes will be implemented:
1. start with 5 easier problems in the first 2 PSes and then automatically go down to 4 (medium-hard) problems only in the middle two PSes when the school gets busier,
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, as recorded lecture),
3. (slightly) better proof presentation in lectures and tutorials (also to re-prepare Steven for CS3230 in Sem 2 AY 2022/23),
4. continue asking more proving questions in tests,
5. further reduce the competition level one notch compared to the last six iterations,
6. a bit more of basic stuffs delegated to VisuAlgo e-Lecture (to make this course more into flipped classroom),
7. continue refining the more interesting Graph Matching topics: Kuhn-Munkres and Edmonds' Matching Algorithm,
8. there will be two sessions (the first and the last) where Steven himself is the one who is away (IOI 2022/clash with week 1 and then the postponed ICPC World Finals 2021/clash with week 13).
Q: Will there be some form of coding in this course?
A: The lecturer is 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 (no more stock at NUS Central Library co-op or maybe last few stocks at @ 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 is one other book that Steven use but this one is rare-and-hard-to-find: Stochastic Local Search: Foundations and Applications so just read the notes.

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 Lecture
Thu 12-2pm
LT19 (F2F with post-lecture recordings)
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
00,
Bef
08
Aug
Please revise your CS1010+CS2040 (or their variants) and CS3230
PS: If you happen to have taken CS3233 before,
revise Max Flow, Matching, and NP-hard/complete
that we have discussed in CS3233 before

CP4 Book 2 Chapter 8.6.6 (Min Vertex Cover)
01.VertexCover.pdf
MVC @ VisuAlgo (the unweighted version)
Understanding Unsolvable Problem

Slides used in the flipped classroom (early recording:
00.Introduction.pdf (2022)
Administrative stuffs for the S1 AY 2022/23 edition
01.VertexCoverLecture.pdf (2021, no change)
(Re)-Introduction to the Min-Vertex-Cover problem (CS3230 review) and the 3C2 idea
MVC Online Quiz (easy static questions at the moment)
01,
08-12
Aug
National Day is on Tue, 09 Aug 2022

But Steven is in Yogyakarta, Indonesia, for IOI 2022
According to the schedule for Thu, 11 Aug 22, midday
(GMT+7 in IDN or GMT+8 in SGP),
he is not able to do live (Zoom) class at this time,
The first Lecture has been recorded on Week 00
02,
15-19
Aug
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)
02.LPIntro.pdf
MVC @ VisuAlgo (now the weighted version)

Slides used in the flipped classroom:
02.ApproximationLecture.pdf (2021)
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
03,
22-26
Aug
CP4 Book 2 Chapter 8.6.7 (Set Cover) + 8.6.10 (Steiner Tree)
03a.SetCover.pdf
No Min Set Cover visualization @ VisuAlgo yet :'(...
03b.SteinerTree.pdf
Steiner Tree @ VisuAlgo (the general/graph version)

Slides used in the flipped classroom:
03a.SetCoverLecture.pdf (2021)
Another Combinatorial Optimization Problem (COP): Min-Set-Cover
03b.SteinerTreeLecture.pdf (2021)
Yet another COP: Steiner-Tree (3 variants); stop at Complete Search solution
04,
29 Aug-
02 Sep
CP4 Book 2 Chapter 3.5 + 8.6.3 (TSP)
04.TSP.pdf
TSP @ VisuAlgo (1.5-approx has a 'bug')
Extra Material: Someone made a movie out of this: Trailer, Movie website

Slides used in the flipped classroom:
The last part (2-approximation) of 03b.SteinerTreeLecture.pdf (2021)
04.TSPLecture.pdf (2021)
Going deeper on this classic Travelling-Salesman-Problem
TSP Online Quiz (medium, static questions at the moment)
05,
05-09
Sep
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:
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
06,
12-16
Sep
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:
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
Recess Week, 17-25 Sep 2022
We can take a break this week :)
But only if you can finish PS3 earlier...
and choose not to start PS4 early...
07,
26-30
Sep
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),
Wrap-ups of Graph Matching Topic
08,
03-07
Oct
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 NOT Open Internet
Steven will only print 15 questions papers (out of 43 students)
Majority will just read the questions on their laptop
Steven will print 43 answer sheets
You will only hand-in the (thinner) answer sheets at the end.

Midterm Test Past Papers (recent 3 AYs+ours only):
Midterm test paper (S1 AY 2019/20),
Midterm test paper (S1 AY 2020/21),
Midterm test paper (S1 AY 2021/22),
Midterm test paper (S1 AY 2022/23) — our paper.
09,
10-14
Oct
08.StochasticLocalSearch.pdf (2016)
[not flipped-classroom]:
Introduction to Stochastic Local Search (SLS)
Paradigm change, SLS Characteristics,
No proof, just experiments...
10,
17-21
Oct
09.Meta-heuristics.pdf (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...

Fri, 21 Oct 2022 is chosen as
NUS well being day S1 AY 2022/23
No CS4234 class is affected

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
11,
24-28
Oct
Deepavali is on Mon, 24 Oct 2022
CS4234 Monday Tutorial classes are cancelled

10.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... :)
Steven's PhD Thesis: 2004-2010 is downloadable from NUS ScholarBank
12,
31 Oct-
04 Nov
Mini Project Presentations and Q&A Segment

Final assessment preview
Course review
Reminder about Teaching Feedback
Official class onsite photo at LT19
13,
07-11
Nov
Steven is at Dhaka, Bangladesh, for ICPC World Finals 2021
(that has been postponed until this week, 06-11 Nov 2022)
Thu, 10 Nov 2022 is ICPC World Finals 2021 date.
So Steven has decided to just put the optional PushRelabel lecture here.

11.PushRelabel.pptx (2016)
CP4 Book 2 Chapter 9.24 (Push-Relabel Algorithm)
No Push Relabel visualization @ VisuAlgo yet :'(...

Introducing the Push-Relabel Algorithm
Sample (manual) execution
Analysis of Basic Push-Relabel Algorithm
Study Week, 12-18 Nov 2022
Final Assessment Consultations (per request)

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

NUS Online Teaching Feedback System closes on Friday of Study Week
Final Assessment, Tue, 29 Nov 2022 (EV, 5-7pm SGT),
Venue: COM1-2-SR1 (F2F),
Open book+Open laptop (no restriction on this) but NOT open Internet (i.e., airplane mode)
40% MCQs (very tricky); then three essay questions (of easier level than the midterm)
(the MCQs are there to speed up grading as Steven has other final assessments
on 26 Nov (206 pax) and 03 Dec (178 pax))
(35%)

## 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. I Say Hi: Given to first 7 students who reply Steven's welcome email with at least one paragraph of reply (sent on Mon, 25 July 2022, 5.05pm); Any early feedback will always help Steven in refining the preparation of the next iteration of this course, especially voice any concern about the plan to go full 100% F2F for this course
2. Kiasu (#): Given to the first 7 students who solve all tasks of PS1-Prerequisites
3. This Course Is Not Hard (#): Given to the first 7 students who solve all tasks of PS2-NP-hard 1
4. Flows Like Water (#): Given to top 7 students who solve all tasks of PS3-NP-hard 2+Flows 1
5. It is a Match (#): Given to the first 7 students who solve all tasks of PS4-Flows 2+Matchings
6. Test Master (#): Given to the top 7 students who have Midterm Test scores ≥ 78 points (Update on 04 October 2022: VisuAlgo Online Quiz system is half-ready by Week 08, so it is used as optional exercise only for this S1 AY 22/23)
7. Active in Class: Given to the top 2-3 students per tutorial group who participated the most in our tutorial classes (Given on the last Week 13, these students will get full 5% tutorial participation points, the rest will fight for 4, 3, 2, 1% tutorial participation points)
8. Future Algorithm Researcher: Given to top 3 project groups who perform well in their mini project about SLS experiments on two (NP-)hard COPs
9. Nowhere to Hide (Reason): Given to students who already remembered by Steven (stopped by last lecture)
10. Kattis Mini Apprentice (Kattis profile link): Given to students who manage to get 500.0 or more Kattis points at open.kattis during the execution of CS4234 in S1 AY 2022/23 (closed by last lecture); doing PS1+2+3+4+Mini Project will only give you about ~100.0 Kattis points... so you must have done a lot more extra homework than necessary; PS: This is my account and this CS4234-specific page of Methods to Solve can help you get this achievement)
Student Name