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.
Useful information to help you decide on whether you 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=??/33?)  AugNov 2016 (n=23/40) 

Module feedback  Hopefully ▲  4.00 (slightly above CS dept average) 
Module difficulty  Hopefully ▼ just a bit  4.13 (slightly harder than CS dept average) 
Steven's teaching  Hopefully ▲  4.53 (above CS dept average) 
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 (TBA) 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 (TBA) Dinic's algorithm, 'Tighter' FF analysis MinCut PS3 (written) submission 

08, 0913 Oct 
Midterm Test (25%) Plan: Week0106 material, excluding Lecture 7 PushRelabel, but including T05 Including stuffs from PS13 Open book (no restriction on this) Only one constraint: No electronic device (except normal calculator) Last year paper (S1 AY 2016/17) is here. 
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 and Edmonds's Matching Algorithm (Bipartite) Matching Visualization @ VisuAlgo PS: Deepavali, 18 Oct 2017 (Wed) No CS4234 class is affected 
T07.pdf (TBA), T07ans.pdf (TBA) Discussion about 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 (TBA), T08ans.pdf (TBA) Discussion about Graph Matching problems Especially 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 (TBA), T09ans.pdf (TBA) Discussion about Stochastic Local Search Using one of Mini Project topic as the context "Active in Class" achievement will be finalized this week 

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 (TBA), T10ans.pdf (TBA) Discussion about SLS DTP Using one of Mini Project topic as the context Tutorial Participation Marks given (5%) 

Steven, Rais, and 3 other current CS4234 students (Wei Liang, Kien, Xinan) will depart to ACM ICPC Jakarta 2017, 10111213 Nov 2017 No CS4234 class should be 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) 


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 
