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.
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:
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, 15 pax) and Teoh Jun Jie (T3, 22 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...
Rating (out of 5.0) |
Aug-Nov 23 (n=??/58) ≥ 50?% |
Aug-Nov 22 (n=27/43) 63% ▼ |
Aug-Nov 21 (n=24/31) 77% ▲ |
Aug-Nov 20 (n=15/44) 34% ▼ |
Aug-Nov 19 (n=18/32) 56% ▼ |
Aug-Nov 18 (n=19/26) 73% ▲ |
---|---|---|---|---|---|---|
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:
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.
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 |
---|
Week | Tutorial |
Lecture |
Assignment |
---|---|---|---|
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 | |||
-01, Bef 07 Aug |
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 |
PS1-Prerequisites 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. |
00, 07-11 Aug |
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 |
01, 14-18 Aug |
Has Not Started |
Introduction and Min-Vertex-Cover Pre-reading material: CP4 Book 2, Chapter 8.6.6 (Min Vertex Cover) 01.VertexCover.pdf 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 _{3}C_{2} idea MVC Online Quiz (easy, still many static questions) |
PS1, continued |
02, 21-25 Aug |
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) 02.LPIntro.pdf 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... |
03, 28 Aug- 01 Sep |
T01.pdf The Intro COP: Min-(Weight)-Vertex-Cover LP, 2 More COPs: Max-Clique, Graph-Coloring, 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) 03a.SetCover.pdf No Min Set Cover visualization @ VisuAlgo yet :'(... 03b.SteinerTree.pdf 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 |
04, 04-08 Sep |
T02.pdf 4 More COPs: Min-Set-Cover Steiner-Tree Min-(Weight)-Feedback-Edge-Set 2-CNF-SAT PS2 Overview |
Travelling-Salesperson-Problem Pre-reading material: 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 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 |
05, 11-15 Sep |
T03.pdf 3 More COPs: Travelling-Salesperson-Problem Max-Independent-Set PIT PS3 Overview |
Max-Flow 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 |
06, 18-22 Sep |
T04.pdf Back to a P optimization problems: Max-Flow Edmonds-Karp vs Dinic's discussion and analysis Max-Cardinality-Bipartite-Matching Max-Independent(/Edge-Disjoint)-Path Min-Cut Alternative Ford-Fulkerson analysis |
Graph-Matching-1 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 |
||
07, 02-06 Oct |
T05.pdf 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) |
Graph-Matching-2 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), Wrap-ups of Graph Matching Topic |
PS4, continued |
08, 09-13 Oct |
T06 (modal answers are NOT uploaded) Midterm test preparation Prof Halim has the modal 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 not print questions papers (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) — will be our paper, N/A yet. |
PS4, continued |
09, 16-20 Oct |
T07.pdf Midterm test debrief Weighted MCBM: Hungarian tracing One weighted MCBM problem Another Optimization Problem involving matching |
NEW for 2023: VisuAlgo CS4234 Online Quiz (9%) Stochastic-Local-Search (2016) [not flipped-classroom]: Introduction to Stochastic Local Search (SLS) Paradigm change, SLS Characteristics, No proof, just experiments... |
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 in 15 project groups of size 6... (or in 18 project groups of size 5...) (actual group size TBC) |
10, 23-27 Oct |
T08.pdf 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 |
11, 30 Oct-03 Nov |
T09.pdf Discussion about SLS, continued 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 |
12, 06-10 Nov |
T10 (modal answers are NOT uploaded) Past Paper discussion (last) round Final class photo (TG1+TG3) "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 TBC) Final assessment preview 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 |
Mini-Project due on Thu, 09 Nov 2023, 11.59am (10%) Before the last onsite lecture |
13, 13-17 Nov 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) Prof Halim plans to record the optional Push-Relabel lecture here. Push-Relabel Pre-reading material: CP4 Book 2 Chapter 9.24 (Push-Relabel Algorithm) No Push Relabel visualization @ VisuAlgo yet :'(... Slides used in the flipped classroom: 11.PushRelabel.pptx (2016) 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), AY 2023/24: Final paper (S1 AY 2023/24, without the MCQs, will be our paper) NUS Online Teaching Feedback System closes on Friday of Study Week |
|||
Final Assessment, Thu, 30 Nov 2023 (AM, 9-11am SGT), Venue: TBC (F2F), Open book (no more Open Laptop, too risky now) 50% MCQs (very tricky); then just two essay questions (of easier level than the midterm) (the MCQs are there to speed up grading as Prof Halim has other final assessments on 01 Dec (126 pax), ICPC Asia Jakarta (02-03 Dec), and 07 Dec (161 pax)) (35%) |