Overview (from Dr Seth Gilbert's version of S1 AY 2015/16  2 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 goodenough solutions to NPhard 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) AY2017/2018 should be similar to the past 2 AYs: ~40 students.
After recess week, the final official number of students for S1 AY2017/2018 is 33 students.
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 AY 2017/2018:
Teaching Assistant (TA): Muhammad Rais Fathin Mudzakir, our main coder in recent ACM ICPC World Finals 2017.
Machines, e.g. Mooshak, VisuAlgo, and Kattis will continue be used to help Steven run this module...
Rating (out of 5.00)  AugNov 2017 (n=20/33)  AugNov 2016 (n=23/40) 

Module feedback  4.4 ▲ (above CS dept average)  4.00 
Module difficulty  4.1 (slightly harder than CS dept average, similar across 2 AY)  4.13 
Steven's teaching  4.6 ▲ (above CS dept average)  4.53 
Steven will improve his second iteration of CS4234 with the following updated lesson plan (initially derived from Dr Seth Gilbert's version of S1 AY 2015/16 but has 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  Lecture Tue 122pm COM10204 (no webcast facility here) 
Tutorial Thursday, 23 (Steven)/ 34 (Rais)/45pm (Rais) COM10203 


but CS4234 first lecture is not affected and Steven has already returned from Tehran, Iran (for IOI 2017) by this week. 

00, Before 14 Aug 
Not started But please revise your CS1020+CS2010/CS2020 (future: CS2040) and CS3230 
Not Started  
01, 1418 Aug 
00.Introduction.pptx 01.VertexCover.pptx, 01.VertexCover.pdf (both 2017 version) Extra Reference: MVC @ VisuAlgo (the unweighted version) Understanding Unsolvable Problem (Re)Introduction to the MinVertexCover problem (CS3230 review) and the 3C2 idea 
Not started  
02, 2125 Aug 
02.LPIntro.pptx, 02.LPIntro.pdf (2016 version) Extra Reference: MVC @ VisuAlgo (the weighted version) Extra Material: 02.ExcelSample.xlsx, Simplex C++ implementation Introduction to (Integer) Linear Programming + Relaxation The MinWeightVertexCover problem 
Not started  
03, 28 Aug01 Sep 
03a.SetCover.pptx, 03a.SetCover.pdf (2016 version) Another Combinatorial Optimization Problem (COP): MinSetCover 03b.SteinerTree.pptx, 03b.SteinerTree.pdf (2016 version) Yet another COP: SteinerTree (3 variants) Extra Reference: Steiner Tree @ VisuAlgo (the general/graph version) 
T01.pdf, T01ans.pdf (see IVLE) The Intro COP: Min(Weight)VertexCover (I)LP, MaxClique, and PS1 discussion 

04, 0408 Sep 
04.TSP.pptx, 04.TSP.pdf (2016 version) Going deeper on this classic TravellingSalesmanProblem Extra Reference: TSP @ VisuAlgo Extra Material: Someone made a movie out of this: Trailer, Movie website 
T02.pdf, T02ans.pdf (see IVLE) 3 More COPs: MinSetCover, SteinerTree Min(Weight)FeedbackEdgeSet 

05, 1115 Sep 
05.MaxFlow.pptx Introduction to MaxFlow Problem FordFulkerson Algorithm MaxFlow/MinCut Theorem MaxFlow Visualization @ VisuAlgo 
T03.pdf, T03ans.pdf (see IVLE) 2 More COPs: TravellingSalesmanProblem MaxIndependentSet 

06, 1822 Sep 
06.FFAnalysis.pptx Analyzing the performance of FordFulkerson Other Augmenting Path Heuristics: FattestPath, CapacityScaling, Edmonds Karp's Algorithm MaxFlow Visualization @ VisuAlgo again 
T04.pdf, T04ans.pdf (see IVLE) Back to a P optimization problems: MaxFlow MaxCardinalityBipartiteMatching MaxIndependent(/EdgeDisjoint)Path PS2 debrief 

We can take a break this week :) 

07, 0206 Oct 
07.PushRelabel.pptx Introducing the PushRelabel Algorithm Sample (manual) execution (no VisuAlgo page yet involving PushRelabel) Analysis of Basic PushRelabel Algorithm 
T05.pdf, T05ans.pdf (see IVLE) Dinic's algorithm, 'Tighter' FF analysis MinCut AssignmentProblem PS3 (written) submission 

08, 0913 Oct 
Midterm Test (25%) Plan: Week0106 material, excluding Lecture 7 PushRelabel, but including T05 Including stuffs from PS13 (PS4 exposure is good to have too btw) Open book (no restriction on this) Only one constraint: No electronic device (except normal calculator) Last year paper (S1 AY 2016/17) is here. This year paper (S1 AY 2017/18) is currently in IVLE Workbin only. 
T06 (no new question) Midterm Test Debrief Solutions and common mistakes of the Midterm Test paper will be discussed here but the solution file will not be uploaded publicly (see passwordprotected IVLE Workbin) 

09, 1620 Oct 
08.Matching.pdf Introduction to Max(Cardinality/Weight)(Bipartite)Matching Problem MaxFlow, Augmenting Path Algorithm++, Hopcroft Karp's Algorithm Preview of MinCost MaxFlow, Hungarian, and Edmonds's Matching Algorithm Graph Matching Visualization @ VisuAlgo PS: Deepavali, 18 Oct 2017 (Wed) No CS4234 class is affected 
T07.pdf, T07ans.pdf (see IVLE) Discussion about O(n^{3}) PushRelabel algorithm Application of Matching/MaxFlow on two NPhard COPs 

10, 2327 Oct 
09.StochasticLocalSearch.pdf Introduction to Stochastic Local Search (SLS) Paradigm change, SLS Characteristics, No proof, just experiments... 
T08.pdf, T08ans.pdf (see IVLE) Discussion about Graph Matching problems/algorithms Two applications of (Bipartite) Matching 

11, 30 Oct03 Nov 
10.Metaheuristics.pdf Discussions of a few, moresophisticated SLS algorithms Simulated Annealing, Tabu Search, Iterated Local Search, Evolutionary Algorithms, etc... Highlight on the need of tuning certain parameters of those SLS algorithms... 
T09.pdf, T09ans.pdf (see IVLE) Discussion about Stochastic Local Search Using one of Mini Project topic as the context 

12, 0610 Nov 
11.SLSDTP.pdf SLS Design and Tuning Problem (DTP) Designing SLS algorithm; Doing (Parameter) Tuning; Fitness Landscape and Search Trajectory Analysis Example on another NPhard COP: QuadraticAssignmentProblem qap_arotsi.avi, qap_arotsa.avi, qap_brotsi.avi, qap_brotsb.avi, QAP_FL_Demo.exe 
T10.pdf, T10ans.pdf (TBA) Discussion about SLS DTP Using one of Mini Project topic as the context "Active in Class" achievement will be finalized this week Tutorial Participation Marks given (5%) 

Steven, Rais, and 3 other current CS4234 students (Wei Liang, Kien, Xinan) have competed in ACM ICPC Jakarta 2017, 10111213 Nov 2017 No CS4234 class was affected 

13, 1317 Nov 
12.StevenPhDThesis Steven's PhD thesis: 20042010, downloadable from NUS ScholarBank Continuation of Lecture 11 More FL/ST insights; More on SLS implementation techniques Invitation to do PhD in algorithm... :) Closed with module review and final assessment preview 
T11 (no new question) Mini Project Presentations By project groups 

Final Assessment Consultations (per request) 

Last year paper (S1 AY 2016/17) is here. This year paper (S1 AY 2017/18) can be found at IVLE workbin (will be a 'past paper' next year). 
Steven uses a smallscale 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)
Tut  Student Name 
