Overview (from Dr Seth Gilbert's version of S1 AY 2015/16 - 3 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.
The expected number of CS4234 students for Semester 1 (S1) AY18/19 is actually slightly larger than the past 3 AYs, which is 60 students. This is the initial number that Steven is working with when preparing this module albeit Steven has a feeling it will hover around 40+ after round 3B based on the enrollment data in the earlier rounds.
Useful information that has been used by current students to decide on whether they should register for CS4234 (see CS4234 in nusmods.com, no review though) in S1 AY18/19:
Teaching Assistant (TA): Gan Wei Liang, IOI International Scientific Committee member 2018-2021, Champion of ICPC Manila Regional 2017, CS4234 alumni (S1 AY17/18, A+), Student Tutor Honour List AY16/17.
Lab TA (Grader): Yohanes Yudhi Adhikusuma, PhD Candidate, NUS SoC, CS4234 alumni (S1 AY16/17, A-).
Machines, e.g. Mooshak, VisuAlgo, and Kattis will continue be used to help Steven run this module...
Rating (out of 5.0) (SoC avg ~4.1) |
Aug-Nov 2018 (n=??/33) 70%+ |
Aug-Nov 2017 (n=20/33) 60% |
Aug-Nov 2016 (n=23/40) 58% |
---|---|---|---|
Module feedback | Target: 4.3+ (maintain) | 4.4 ▲ (above avg) | 4.00 |
Module difficulty | Target: 4.1- (maintain) | 4.1 ▼ (above avg :O) | 4.13 |
Steven's teaching | Target: 4.4+ (let's see) | 4.6 ▲ (above avg) | 4.53 |
For the third 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 |
---|
After exam, Bay Wei Heng, Muhammad Irham R B Z, Ng Yi Chong Raynold (students) will also going to compete in ICPC Asia Yangon 2018.
Lastly, on 13 December 2018, many CS4234 staffs/students will be involved in ICPC Asia Singapore 2018.
Week | Tutorial Mon, 10-11 (3), 11-12 (2), or 17-18 (1) |
Lecture Wed 12-2pm, COM1-0204 (no webcast facility here) |
Assignment |
---|---|---|---|
but CS4234 first lecture is not affected |
|||
00, Bef 13 Aug |
Not Started |
Not started But please revise your CS1020+CS2010 (or CS2020/CS2040) and CS3230 PS: If you have taken CS3233 before, revise NP-hard/complete, Max Flow, and Matching that we have discussed in CS3233 before |
Not Started |
01, 13-17 Aug |
Not started |
00.Introduction.pptx (2018 version) 01.VertexCover.pptx, 01.VertexCover.pdf (2017 version) Extra Reference: MVC @ VisuAlgo (the unweighted version) Understanding Unsolvable Problem (Re)-Introduction to the Min-Vertex-Cover problem (CS3230 review) and the _{3}C_{2} idea PS: Sat, 18 Aug 2018, 12-5pm (SoC homecoming) |
PS1-Art Gallery+, out on Wed, 15 Aug 2018, 13.45pm A machine will help Yohanes/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 27/08/2018 00:00 |
02, 20-24 Aug |
Not Started |
Public holiday on Wed, 22 Aug 18 (Hari Raya Haji) CS4234 second class on this day is cancelled and replaced with a make up class. Make up class (due to missing Week 02+04) is on Sat, 25 Aug 2018, 10am-12pm @ COM1-0204 02.LPIntro.pptx, 02.LPIntro.pdf (2016 version) Extra Reference: MVC @ VisuAlgo (the weighted version) Extra Material: 02.ExcelSample.xlsx, 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, 27-31 Aug |
T01.pdf, T01-ans.pdf (see IVLE) The Intro COP: Min-(Weight)-Vertex-Cover (I)LP, Max-Clique, and PS1 discussion |
03a.SetCover.pptx, 03a.SetCover.pdf (2016 version) Another Combinatorial Optimization Problem (COP): Min-Set-Cover 03b.SteinerTree.pptx, 03b.SteinerTree.pdf (2016 version) Yet another COP: Steiner-Tree (3 variants) Extra Reference: Steiner Tree @ VisuAlgo (the general/graph version) |
PS1 due on Sat, 01 Sep 2018, 07.59am (5%) PS2-Rubble+, out on Sat, 01 Sep 2018, 08.00am Also on Mooshak |
Sat, 01-08 Sep 2018, (IOI 2018 @ Tsukuba, Japan) Steven (lecturer/SGP IOI team leader), Wei Liang (TA/International Scientific Committee member), and Ranald (student/International Technical Committee member) will not be available... |
|||
04, 03-07 Sep |
No tutorial |
Steven (lecturer) and Wei Liang (tutor) will be in IOI 2018, Tsukuba, Japan No Lecture and Tutorial this week and no make up class for Week 04 :O But there is a self-reading assignment to prepare you for Week 05+06: Self explore: TSP @ VisuAlgo and Max-Flow Visualization @ VisuAlgo. |
PS2, continued |
05, 10-14 Sep |
T02.pdf, T02-ans.pdf (see IVLE) PS1 Debrief 3 More COPs: Min-Set-Cover Steiner-Tree Min-(Weight)-Feedback-Edge-Set |
04.TSP.pptx, 04.TSP.pdf (2016 version) Going deeper on this classic Travelling-Salesman-Problem Extra Reference: TSP @ VisuAlgo Extra Material: Someone made a movie out of this: Trailer, Movie website |
PS2 due on Sat, 15 Sep 2018, 07.59am (5%) |
Sat, 15 Sep 2018, ICPC Asia Singapore 2018 Preliminary Contest This also doubles as NUS ICPC Team Selection Contest Some problems there may be relevant to CS4234, e.g. those that say 'maximize that' or 'minimize this' |
|||
06, 17-21 Sep |
T03.pdf, T03-ans.pdf (see IVLE) PS2 Debrief 2++ More COPs: Travelling-Salesman-Problem Max-Independent-Set |
05.MaxFlow.pptx + 06.FFAnalysis.pptx (flipped classroom) Introduction to Max-Flow Problem (flipped classrom) Ford-Fulkerson Algorithm (quick run through) Max-Flow/Min-Cut Theorem (in details) Analyzing the performance of Ford-Fulkerson (quick analysis) Other Augmenting Path Heuristics: Fattest-Path, Capacity-Scaling (skipped), 'Tighter' FF analysis: Edmonds Karp's Algorithm (in details) Dinic's algorithm (quick analysis) Max-Flow Visualization @ VisuAlgo |
PS3-Mini Researcher, out on Wed, 19 Sep 2018, ~10.30am PS3 is a written PS Download the tasks here |
We can take a break this week :) |
|||
07, 01-05 Oct |
T04.pdf, T04-ans.pdf (see IVLE) Back to a P optimization problems: Max-Flow Max-Cardinality-Bipartite-Matching Max-Independent(/Edge-Disjoint)-Path Min-Cut Alternative Ford Fulkerson's analysis |
07.PushRelabel.pptx Introducing the Push-Relabel Algorithm Sample (manual) execution (no VisuAlgo page yet involving Push-Relabel) Analysis of Basic Push-Relabel Algorithm |
PS3, continued |
08, 08-12 Oct |
T05.pdf, T05-ans.pdf (see IVLE) Assignment-Problem Discussion about O(n^{3}) Push-Relabel algorithm Midterm test preparation PS3 (written) submission (during tutorial) |
Midterm Test (25%) Material: Week01-06, excluding Lecture 7 Push-Relabel, but including T05 Including stuffs from PS1-3 (PS3 task 3 style question appears) (PS4 exposure is good to have but not crucial; only ~20% questions on Max-Flow) Dinic's algorithm is not yet written properly in L5/6 ppt but can be reviewed here There are more proving questions this time Open book (no restriction on this) Only one constraint: No electronic device (except normal calculator) Midterm test paper (S1 AY 2016/17), Midterm test paper (S1 AY 2017/18), Midterm test paper (S1 AY 2018/19). |
PS3 due on Mon, 08 Oct 2018 (5%) (submit hardcopy to Weiliang during your T05) PS4 Flows, out on Mon, 08 Oct 2018, 08.00am The last one on Mooshak |
09, 15-19 Oct |
T06 (no new question) Midterm Test Debrief Solutions and common mistakes of the paper will be discussed in tutorial but the solution file will not be uploaded publicly (see password-protected IVLE Workbin) Scripts will be returned during tutorial You can also ask stuffs about ongoing PS4 during T06 |
08.Matching.pdf Introduction to (Weighted) Max-Cardinality-(Bipartite)-Matching Problem Max-Flow, Augmenting Path Algorithm++, Hopcroft Karp's/Dinic's Algorithm Overview of Min-Cost Max-Flow, Hungarian, and Edmonds's Matching Algorithm Graph Matching Visualization @ VisuAlgo |
PS4 due on Sat, 20 Oct 2018, 07.59am (5%) |
10, 22-26 Oct |
T07.pdf, T07-ans.pdf (see IVLE) Discussion about Graph Matching problems/algorithms Application of Matching/Max-Flow on two NP-hard COPs Two other applications of (Weighted) (Bipartite) Matching |
09.StochasticLocalSearch.pdf Introduction to Stochastic Local Search (SLS) Paradigm change, SLS Characteristics, No proof, just experiments... |
Mini-Project: Local Search, start on Mon, 22 Oct 2018 Preview on Mon, 22 Oct 2018 Proper launch during Lecture 09 Download S1 AY 2018/19 tasks here. |
11, 29 Oct- 02 Nov |
T08.pdf, T08-ans.pdf (see IVLE) Discussion about Stochastic Local Search Using one of Mini Project topic as the context |
10.Meta-heuristics.pdf 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, 05-09 Nov |
T09.pdf, T09-ans.pdf (see IVLE) Discussion about SLS DTP Mini Project progress discussion "Active in Class" achievement will be finalized this week Tutorial Participation Marks given (5%) |
11.SLS-DTP.pdf 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 PS: Deepavali, 06 Nov 2018 (Tue) Does not clash with CS4234 class |
Mini-Project, continued |
Steven and a few other students outside CS4234 has competed in ICPC Jakarta 2018, Fri 09-Sat 10-Sun 11-Mon 12 Nov 2018 Result: 3rd, 12th, and 20th out of 74 teams. No CS4234 class should be affected Wei Liang is still present for the last tutorial T10 |
|||
13, 12-16 Nov |
T10.pdf, T10-ans.pdf (see IVLE) SLS Design and Tuning Problem Final assessment preparation (also see links of past two final papers below) Final class photo |
First 1.5 hour: Mini Project Presentations By 9 project groups At most 9x5 = 45 minutes + buffer Closed by: Invitation to do PhD in algorithm... :) Module review, and Final assessment preview |
Mini-Project due on Wed, 14 Nov 2018, 11.59am (15%) Before last lecture, you will present your work during the first hour of last lecture |
Gan Wei Liang (TA), Ranald Lam Yun Shao (student), and Nguyen Tien Trung Kien (last year CS4234 student) has competed in ICPC Nakhon Pathom 2018, Thu 15-Fri 16-Sat 17-Sun 18 Nov 2018 Result: 1st and 3rd out of 69 teams. No CS4234 class should be affected |
|||
Final Assessment Consultations (per request) |
|||
Past Papers: Final paper (S1 AY 2016/17), Final paper (S1 AY 2017/18). |
|||
Bay Wei Heng, Muhammad Irham R B Z, and Raynold Ng Yi Chong (CS4234 students) will compete in ICPC Asia Yangon 2018, Fri 07-Sat 08-Sun 09-Mon 10 Dec 2018 No CS4234 class should be affected |
|||
ICPC Asia Singapore 2018, Wed 12-Thu 13-Fri 14 Dec 2018 |
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 | Tut | Grp | TSP | MWVC | Student Name | Achievements |
---|