Overview (from Dr Seth Gilbert's version): 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 Steven is assigned to teach this module again (TBC), should be similar to the past 2 AYs: ~40.
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): Hopefully for the second iteration, Steven can get ONE (1) eligible Teaching Assistant to help him run the second iteration instead of 100% himself in the first iteration.
Machines, e.g. Mooshak, VisuAlgo, and Kattis will continue to be used to help him run this module...
Rating (out of 5.00)  AugNov 2017 (n=??/??)  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 lesson plan (initially derived from Dr Seth Gilbert's version of S1 AY 2015/16):
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 

The CS4234 syllabus will be delivered over 13 weeks, except on Week 02 and Recess Week.
There is an important schedule deviation on Week 01 due to Public Holiday on Tuesday, 9 August 2016 and Steven's absence on Week 02 due to IOI 2016.
Week  Lecture Tue 122pm COM10204 (no webcast facility here) 
Tutorial Thursday, 23/34/45pm COM10203 


00, Before 09 Aug 
Not started But please revise your CS1020+CS2010/CS2020 and CS3230 
Not Started  
01a, 0809 Aug 
00.Introduction.pptx 01.VertexCover.pptx, 01.VertexCover.pdf Extra Reference: Understanding Unsolvable Problem (Re)Introduction to the MinVertexCover problem (CS3230 review) and the 3C2 idea Make up class due to public holiday on 9 Aug (National Day) Date and Time: Monday, 08 August 2016, 6.308.30pm; Venue: COM10206 (SR1) Webcast is available for those who cannot make it (you need to watch to do PS1) Update: Only ~15/41 attended the first make up class 
Not started  
CS4234 first lecture will be affected. 

01b, 1012 Aug 
02.LPIntro.pptx, 02.LPIntro.pdf Extra Material: 02.ExcelSample.xlsx Introduction to (Integer) Linear Programming + Relaxation The MinWeightVertexCover problem Make up class due to Steven's absence on Week 02 Date and Time: Wednesday, 10 August 2016, 6.308.30pm; Venue: COM10206 (SR1) Webcast is available for those who cannot make it (you need to watch to do PS1) Update: Only ~22/41 attended the second make up class 
Not started  
02, 1519 Aug 
Steven is in Russia for IOI 2016 No class on Week 02, see the second make up class on Week 01 Do not forget to decide whether CS4234 with all those (NP)hard problems are for you or not by end of Week 02... 
Not Started  
03, 2226 Aug 
03a.SetCover.pptx, 03a.SetCover.pdf Another Combinatorial Optimization Problem (COP): MinSetCover 03b.SteinerTree.pptx, 03b.SteinerTree.pdf Yet another COP: SteinerTree (3 variants) 
T01.pdf, T01ans.pdf The Intro COP: Min(Weight)VertexCover ILP, LP, and PS1 discussion 

04, 29 Aug02 Sep 
04.TSP.pptx, 04.TSP.pdf Going deeper on this classic TravellingSalesmanProblem Extra Material: Someone made a movie out of this: Trailer, Movie website 
T02.pdf, T02ans.pdf 3 More COPs: MinSetCover, SteinerTree MinFeedbackEdgeSet 

05, 0509 Sep 
05.MaxFlow.pptx Introduction to MaxFlow Problem FordFulkerson Algorithm MaxFlow/MinCut Theorem MaxFlow Visualization @ VisuAlgo 
T03.pdf, T03ans.pdf 2 More COPs: TravellingSalesmanProblem MinIndependentSet 



06, 1216 Sep 
06.FFAnalysis.pptx Analyzing the performance of FordFulkerson Other Augmenting Path Heuristics: FattestPath, CapacityScaling, Edmonds Karp's Algorithm 
T04.pdf, T04ans.pdf Back to P Problems: MaxFlow PS2 debrief 



07, 2630 Sep 
07.PushRelabel.pptx Introducing the PushRelabel Algorithm Sample (manual) execution Analysis of Basic PushRelabel Algorithm 
T05.pdf, T05ans.pdf Dinic's algorithm, 'Tighter' FF analysis Exposure to a MinCut problem PS3 submission 

08, 0307 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 ( The paper 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 IVLE Workbin) 

09, 1014 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 
T07.pdf, T07ans.pdf Discussion about PushRelabel algorithm Application of Matching/MaxFlow on two NPhard COPs 

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

11, 2428 Oct 
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 Discussion about Stochastic Local Search using Mini Project 2LABS Problem as the context "Active in Class" achievement will be finalized this week 



12, 31 Oct 04 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 Discussion about SLS DTP To make it relevant, using Mini Project 1TSP as the context Tutorial Participation Marks given (5%) 

13, 0711 Nov 
12.StevenPhDThesis Steven's PhD thesis: 20042010, downloadable from NUS ScholarBank Continuation of Lecture 11 This time showcasing TSP and LABS that you will need for Mini Project: 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) But see the hall of fame Mini Project Presentations By project groups 

Final Assessment Consultations (per request) 


Steven uses a smallscale gamification system in his version of CS4234.
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 
