Overview (from Dr Seth Gilbert's version of S1 AY 2015/16 - 5 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 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.
The upperbound number of CS4234 students for Semester 1 (S1) AY20/21 is approximately about 15 less than the past 5 AYs, which is 60-15 = at most 45 students due to ZERO exchange student (S1 SEP is cancelled, both for incoming exchange students and outgoing NUS exchange students). CS4234 usually has about ~10 exchange students annually. Steven conservatively estimates that there will only be about ~26 students this time (running average in the past 4 AYs is ~33 students/year) - Steven will prepare at least two tutorial sessions, one F2F (for those who prefer that way and in NUS zone C) and one more online (for those who prefer that way, not in NUS zone C, or still stuck overseas). That estimate of ~26 students for lecture and ~13 per tutorial group (but not necessarily equal size) fall into 'small' class size. The latest COVID-19 advisory says classes ≤ 50 can go F2F so this is the current plan as of 23 July 2020.
The actual number of CS4234 students for Semester 1 (S1) AY20/21 is currently 61 students (as of 12 August 2020). As per latest COVID-19 advisory, I am instructed to go to e-Learning (for now)... We will also run 3 tutorial groups (1 F2F/zone C, 2 online/zone-free).
The actual number of CS4234 students for Semester 1 (S1) AY20/21 is currently 52 students (as of 17 August 2020). We are nearing the magic number threshold (50) for conducting F2F+hybrid lecture, so let's see how it goes.
The final number of CS4234 students for Semester 1 (S1) AY20/21 is 46 students (as of 26 August 2020) 44 students (as of 06 October 2020). We will go back to F2F @ iCube Auditorium + Zoom Hybrid mode for the rest of the semester.
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 AY20/21:
(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... 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): Ammar Fathin Sabili, IOI Bronze 2013; IOI Problem Author 2018, already did CS4234 TA S1 AY19/20 with rating 4.3/5.0 (good) :).
Machines, e.g., VisuAlgo and Kattis will continue be used to help Steven run this module...
Rating (out of 5.0) (SoC avg ~4.1) |
Aug-Nov 2020 (n=15/44) 34% ▼ |
Aug-Nov 2019 (n=18/32) 56% ▼ |
Aug-Nov 2018 (n=19/26) 73% ▲ |
Aug-Nov 2017 (n=20/33) 60% ▲ |
Aug-Nov 2016 (n=23/40) 58% |
---|---|---|---|---|---|
Module feedback | 4.1 ▼ (COVID-19+IOI20) | 4.2 ▼ (> avg) | 4.3 ▼ | 4.4 ▲ | 4.00 |
Module difficulty | 4.4 ▲ (COVID-19+IOI20) | 4.2 == (> avg) | 4.2 ▲ | 4.1 ▼ | 4.13 |
Steven's teaching | 4.1 ▼ (COVID-19+IOI20) | 4.7 ▲ (PB, > avg) | 4.6 == | 4.6 ▲ | 4.53 |
For the fifth 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):
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.
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 Mon, 11am-12pm/T1 (COM1-VCRM, F2F) Mon, 2-3pm/T2 (Zoom, online) Mon, 5-6pm/T3 (Zoom, online) Open ended consultation, Wed 4-6pm |
Lecture Thu 12-2pm I3-Aud (F2F again from Wk03 onwards, venue is big enough for social distancing, Zoom sessions will still be used and recorded) |
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 | |||
00, Bef 10 Aug |
Not Started |
Not started But please revise your CS1020+CS2010 (or CS2020/CS2040) and CS3230 Use this set for your revision (CS1010+CS2040+CS3230 stuffs) PS: If you have taken CS3233 before, revise Max Flow, Matching, and NP-hard/complete that we have discussed in CS3233 before |
Not Started |
01, 10-14 Aug |
Not started |
National Day is on Sun, 09 Aug 2020 The following Mon, 10 Aug 2020 is a Public Holiday CS4234 first lecture is not affected 00.Introduction.pptx (2020) 01.VertexCover.pptx (2020), 01.VertexCover.pdf (2017) Extra Reference: MVC @ VisuAlgo (the unweighted version) Max-Clique Quiz Understanding Unsolvable Problem (Re)-Introduction to the Min-Vertex-Cover problem (CS3230 review) and the 3C2 idea |
PS1-(NP-)hard Optimization 1 Out on Fri, 14 Aug 2020, 08.00pm nus.kattis will help Steven checks your code PS1 runs until end of Week 03 so you have time for self-study And there is time to discuss PS1 during Week03 Lecture/Tutorial Use all these information to decide whether CS4234 is for you Or drop it before end of Week 02 |
02, 17-21 Aug |
Not Started |
02.LPIntro.pptx (2019), 02.LPIntro.pdf (2016) Extra Reference: MVC @ VisuAlgo (the weighted version) Extra Material: 02.ExcelSample.xlsx, lp_solve tutorial, Simplex code in C++ or Java Introduction to (Integer) Linear Programming + Relaxation The Min-Weight-Vertex-Cover problem |
PS1, continued Do not forget to decide whether CS4234 with all those (NP)-hard problems is for you (or not) by end of this Week 02... |
03, 24-28 Aug |
T01.pdf, T01-ans.pdf (see LumiNUS) The Intro COP: Min-(Weight)-Vertex-Cover LP, Max-Clique, Graph-Coloring, Graph-Coloring Quiz, (optional) PS1 discussion |
03a.SetCover.pptx (2019), 03a.SetCover.pdf (2016) Another Combinatorial Optimization Problem (COP): Min-Set-Cover 03b.SteinerTree.pptx (2019), 03b.SteinerTree.pdf (2016) Yet another COP: Steiner-Tree (3 variants) Extra Reference: Steiner Tree @ VisuAlgo (the general/graph version) |
PS1 due on Sat, 29 Aug 2020, 07.59am (5%) PS2-(NP-)hard Optimization 2 Out on Sat, 29 Aug 2020, 08.00am |
04, 31 Aug- 04 Sep |
T02.pdf, T02-ans.pdf (see LumiNUS) PS1 Quick Debrief 3 More COPs: Min-Set-Cover Steiner-Tree Min-(Weight)-Feedback-Edge-Set |
04.TSP.pptx (2016), 04.TSP.pdf (2016) Going deeper on this classic Travelling-Salesman-Problem Extra Reference: TSP @ VisuAlgo Hamiltonian-Cycle Quiz Extra Material: Someone made a movie out of this: Trailer, Movie website |
PS2, continued |
05, 07-11 Sep |
T03.pdf, T03-ans.pdf (see LumiNUS) 2++ More COPs: Travelling-Salesman-Problem Max-Independent-Set |
05a.MaxFlow.pptx (2020) + 05b.FFAnalysis.pptx (2020) Introduction to Max-Flow Problem (a quick one) Ford-Fulkerson Algorithm (another quick run through) Max-Flow/Min-Cut Theorem (in details) Analyzing the performance of Ford-Fulkerson (quick analysis) 'Tighter' FF analysis: Edmonds-Karp Algorithm (in details) Dinic's algorithm (quick analysis) Max-Flow Visualization @ VisuAlgo |
PS2 due on Sat, 12 Sep 2020, 07.59am (5%) PS3-Mini Researcher, Out on Sat, 12 Sep 2020, 08.00am PS3 is a written PS The task requirements and associated files are uploaded to LumiNUS Files |
Online IOI 2020, 13-19 Sep 2020 Steven is super busy with the rescheduled online IOI 2020 Hence Week 06 lectures are pre-recorded and Tut+PS2 queries all handled by TA |
|||
06, 14-18 Sep |
T04.pdf, T04-ans.pdf (see LumiNUS) Back to a P optimization problems: Max-Flow Max-Cardinality-Bipartite-Matching Max-Independent(/Edge-Disjoint)-Path Min-Cut Alternative Ford-Fulkerson analysis |
[RECORDED E-LECTURE] 06.PushRelabel.pptx (2016) Introducing the Push-Relabel Algorithm Sample (manual) execution (no VisuAlgo page yet involving Push-Relabel) Analysis of Basic Push-Relabel Algorithm |
PS3, continued |
Recess Week, 19-27 Sep 2020 We can take a break this week :) |
|||
07, 28 Sep- 02 Oct |
T05.pdf, T05-ans.pdf (see LumiNUS) Assignment-Problem Review of O(n2m) Basic Push-Relabel algorithm Discussion about O(n3) Push-Relabel algorithm One more Push-Relabel question |
07.Matching.pdf (2020) Introduction to (Weighted) Max-Cardinality-(Bipartite)-Matching Problem Week 07 focus: MCBM and its applications Max-Flow, Augmenting Path Algorithm++, Hopcroft-Karp/Dinic's Algorithm Graph Matching Visualization @ VisuAlgo (for Unweighted MCBM) |
PS3 due on Sat, 03 Oct 2020, 07.59am (5%) PS4 - Flows+Matchings Out on Sat, 03 Oct 2020, 08.00am |
08, 05-09 Oct |
T06 Midterm test preparation Both Ammar+Steven have the modal answers of past 4 papers. |
Midterm Test (25%) Material: Week01-05, up to Max Flow Excluding Push Relabel (only a recording, so better not included yet) Including stuffs from PS1-3 (PS3 task 3 style question appears) (solving some PS4 problems early is good to have but not crucial; only ~[15..30]% questions on Max-Flow) ACTUAL FORMAT FOR HYBRID TEST IN EMAIL Open book/laptop (no restriction on this) But NOT open Internet (turn off WiFi for onsite/ strictly no web browser for online proctoring until you have to upload your work) Past papers: Midterm test paper (S1 AY 2016/17), Midterm test paper (S1 AY 2017/18), Midterm test paper (S1 AY 2018/19), Midterm test paper (S1 AY 2019/20), Midterm test paper (S1 AY 2020/21) (our paper). |
PS4, continued |
09, 12-16 Oct |
T07.pdf, T07-ans.pdf (see LumiNUS) Short Midterm test debrief Discussion about Graph Matching problems/algorithms: Application of Matching/Max-Flow on one NP-hard COP Two applications of MCBM |
08.Matching2.pdf (2020) Week 09 focus: Weighted MCBM (MCMF or Kuhn-Munkres/Hungarian), Unweighted MCM (Edmonds' Matching), Weighted MCM (small graph), Wrap-ups of Graph Matching Topic Hungarian Method visualization @ TUM Graph Matching Visualization @ VisuAlgo (for Unweighted MCM) |
PS4, continued |
10, 19-23 Oct |
T08.pdf, T08-ans.pdf (see LumiNUS) More graph matching questions: Another Optimization Problem involving matching, Unweighted MCM, Weighted MCBM |
09.StochasticLocalSearch.pdf (2016) Introduction to Stochastic Local Search (SLS) Paradigm change, SLS Characteristics, No proof, just experiments... |
PS4 due on Thu, 22 Oct 2020, 07.59am (5%) Mini-Project - Local Search Out on Thu, 22 Oct 2020, 12 noon Proper launch during Lecture 10 |
11, 26-30 Oct |
T09.pdf, T09-ans.pdf (see LumiNUS) Discussion about Stochastic Local Search Using Mini Project topic as the context |
10.Meta-heuristics.pdf (2016) 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... |
Mini-Project, continued |
12, 02-06 Nov |
T10.pdf, T10-ans.pdf (see LumiNUS) SLS Review 1 Past Paper discussion 1 Optional: Mini Project progress discussion |
11.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 Closed by: Module review Reminder about Teaching Feedback Invitation to do PhD in algorithm... :) Steven's PhD Thesis: 2004-2010 is downloadable from NUS ScholarBank Final assessment preview Official class (e-)photo NUS Online Teaching Feedback System opens this Friday |
Mini-Project, continued |
13, 09-13 Nov |
T11.pdf, T11-ans.pdf (see LumiNUS) Discussion about SLS DTP Its applications for your Mini Project Final assessment preparation Both Ammar+Steven have the modal answers of past 4 papers. Final class photo "Active in Class" achievement is finalized this week Tutorial Participation Marks given (5%) |
Mini Project Presentations By 44/4 = 11 project groups In reverse order of final ranking as shown in Mini-Project session At most 11x(3m/TSP+3m/MWVC+1m/short QnA+2m/buffer) = 99 minutes Latter groups should *not* repeat what earlier groups have said Deepavali is on Sat, 14 Nov 2020 No CS4234 class is affected |
Mini-Project due on Thu, 12 Nov 2020, 11.59am (15%) Before last lecture, you will present your work during the first hour (up to 70 minutes) of last lecture |
Study Week Final Assessment Consultations (per request) NUS Online Teaching Feedback System closes on Friday of Study Week |
|||
Final Assessment, Tue, 01 Dec 2020 (AM, 9-11am SGT), Venue: e-Exam (35%) Past Papers: Final paper (S1 AY 2016/17), Final paper (S1 AY 2017/18), Final paper (S1 AY 2018/19), Final paper (S1 AY 2019/20, without the MCQs), Final paper (S1 AY 2020/21) (our paper). |
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)
No | Student Name | Achievements |
---|