CS3233 - Competitive Programming

Introduction

This module aims to prepare students in competitive problem solving.

It will benefit NUS students who want to compete in ACM ICPC, invited high school students who want to compete in IOI (not just for NOI), and NUS students in general who aspire to excel in technical interviews of top IT companies.

It covers techniques for attacking and solving challenging* computational problems. Fundamental algorithmic solving techniques covered include complete search, divide/reduce/transform and conquer, greedy, dynamic programming, etc. Domain specific techniques like graph, mathematics-related, string processing, and computational geometry will also be covered. Some additional topics may be included depending on how the semester progresses. Programming language libraries that are commonly used in problem solving will also be taught.

*We only study well-known/solved problems, not research problems.

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.

Course Registration

The quota of this class (Sem 2 AY2016/17) is ... technically only limited by the size of COM1-B-PL2 (46 PCs) ... but not that many NUS students are eligible (or dare enough) to take this extremely competitive module. In recent years, only ~20 NUS students were enrolled and only a few (7 out of 154) are female...

Useful information to help you decide on whether you should offline register for CS3233:

  1. Do you have national (but preferably international) programming competition background before? Examples: NOI (or IDN OSN, VNM VNOI, CHN NOIP, MYS MCO, PHL NOI, etc), IOI, ACM ICPC, Google Code Jam, Topcoder Open, Facebook Hacker Cup, etc?

    The difficulty of this course is very extreme for those without such background... but typically those that satisfy the next requirement (see question 2) can survive just as well... We will study problems that require (advanced) data structure and/or algorithms that are typically asked in programming competitions, and we have to implement those solutions fast and without bug...

  2. Did you score well (at least A-) in CS2010 or equivalent (and preferably score A+ in all CS1101S+CS2020 or CS1010+CS1020+CS2010)?

    This module has a very high performance bar and the average CAP of the students enrolled in the past five academic years were 4.33, 4.44, 4.43, 4.45, and 4.30 (out of 5.00), respectively. You will need special permission from the instructor (Dr Steven Halim) if you do not satisfy the pre-requisites listed above (the filter is there for your own good).

  3. Are you OK to be tortured for one semester for a mere 4 modular credits (your other modules may also suffer)?

    You may have to take lighter set of other modules or be ready to S/U other modules or to rush final assessment preparations for other modules only during study week (no final assessment for CS3233). Please do NOT take CS3233 module with another module that is known to be challenging unless you are very confident of yourself and have historical academic performance to back that up. Moreover, your ego may be hurt if some of the young NOI 2017 trainees (Sec2-JC2 students) beat you in (many) CS3233 contests. Read this nice module review by Benedict Suratanakavikul. Bottom line: Try to ask CS3233 seniors who have taken (and survived) this module before applying!

  4. Are you thinking on applying to top (or emerging) IT companies like Google, Facebook, Microsoft, Dropbox, MemSQL, Garena (NUS ACM ICPC team sponsor), Grab (NUS ACM ICPC team sponsor), etc in the future?

    Some of our ex-CS3233 graduates are now in those companies :). See the CS3233 Hall of Fame to see the current known status of CS3233 past top students.

  5. Do you want to learn interesting data structures, algorithms, and more importantly: On how to apply them properly — from teaching staffs who are deeply involved in such programming competitions?

    (Senior) Lecturer: Dr Steven Halim, current Singapore IOI team leader, NUS ACM ICPC coach, ACM ICPC Asia Singapore Regional Contest Director, the author of Competitive Programming text book (the official text book of this module).

    Rating (out of 5.00) Jan-Apr 2017 (n=16) Jan-Apr 2016 (n=20)
    Module feedback 4.800 (PB) ▲ 4.563 ▼
    Module difficulty 4.300 4.563 uh oh :O
    Steven's teaching 4.800 ▲ 4.603 ▼

    Teaching Assistant: Gan Wei Liang a.k.a. pandamonium (Singapore two times IOI Silver Medalist 2012-2013, coach 2016, and currently an NUS ACM ICPC team member) with a few guest problem contributors. Usually, CS3233 TAs have teaching feedback rating of around ~4.500 too (i.e. good ones). Wei Liang will be mostly available in NUS ACM ICPC Lab (COM1-02-15), especially every Wednesday, 2.30-4.30pm to answer any CS3233/Competitive Programming queries, if any.

If you have read all (scary) questions above and are still interested, simply notify Steven for offline registration before CORS round 3B (the last day of application). The offline registration will be closed as soon as the number of students hits 25 NUS students as we will be joined by about ~20 SG high school students. To minimize the annual attrition rate on Week 02 (Drop without penalty) and also :O on Recess Week (Drop with a 'W' grade), the pre-acceptance selection will be made rigorous.

Note: This course registration section will not be prominent from Thursday, 12 January 2017 onwards (after first lecture). This behavior is normal. You can view it again by scrolling to the top of this page.

News

Date News

Ranklist

Lesson Plan

Week Class Topics
(Wed, 7.30-8.50pm, PL2)
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
-05/-04/
-03/-02/
-01/00 		No class yet but some old teaching materials are available in this public website
01
11 Jan 		Let's Talk CP

Introduction; Brief Course Admins; Focus on delivering some "Wow Moments"; A Bit of C++11 (a mini preview of a few C++11 features in future CP4); Mock/Preview Contest (not graded, but has high standard and with cash prizes)
02
18 Jan 		Be A Librarian

Mastery of Libraries (C++ STL & Java API); Focus on Bit Manipulation and Binary Indexed (Fenwick) Tree
03
25 Jan 		Searching for Answers

Iterative Techniques; Recursive Backtracking; State-Space Search (harder form of SSSP, Graph modeling + BFS/Dijkstra's) with Meet in the Middle (Bidirectional Search)
04
01 Feb 		The Art of Stenography

Dynamic Programming; Quick review of CS2010/CS2020 DP Materials; Focus on relationship between DP and DAG via discussion of several classic DP examples; Focus on formulating non trivial DP states + transitions
05
08 Feb
 Coping with (NP-)hard Problems

New for 2017: Summary of the first 1/3 of CS4234 - Optimisation Algorithms in CS3233 style.
06
15 Feb 		How to Prevent Flood?

Quick overview of Network Flow; Quick review of Ford Fulkerson's Max Flow algorithm variants: Edmonds Karp's and Dinic's; New for 2017: Introducing Push-Relabel algorithm; Focus on Flow Graph Modeling skill and applications
Recess
22 Feb 		No class
07
01 Mar 		Social Development Network

Quick overview of Graph Matching; Unweighted or Weighted MCBM or MCM; New for 2017: Introducing Edmonds's (Blossom Shrinking)/Matching algorithm; Focus on Bipartite Graph Modeling skill and applications
08
08 Mar 		No lecture, we will do Midterm Team Contest
Steven is still available this night and will run this Midterm Contest with Wei Liang.
08
10 Mar
The birth day of Jemimah Charissa Halim (planned C-section)
Steven takes parental leave 9-14 Mar (6d 5n)
09
15 Mar 		NUMB3RS
Steven will return to work this day, esp that NOI 2017 is this weekend

Mathematics Overview; Focus on Java BigInteger, Combinatorics, Number Theory, a bit of Cycle-Finding
10
22 Mar 		(PS: We have to take class photo tonight, after Mini 08)

A Glance at Bioinformatics

String Processing; Focus on Suffix Trie, Suffix Tree, and Suffix Array
11
29 Mar 		(PS: Final team contest formation after Mini 09)

Inside Video Games

(Computational) Geometry; Focus on Algorithms on Points, Lines, and Polygon

(ADDITIONAL BUT SHORT) The Last Lecture
Please give me 30 extra minutes on 29 March to complete CS3233
We will only end the class at 9.30pm on this night...
12
05 Apr 		(PS: We have to take second class photo this evening at 5.10pm, before final team contest, dinner/pizzas for about 25 pax (15 official students, 2 students, and at most 7 guests) will be provided at 4.40pm++; FCFS mode...)

No lecture, we will do Final Team Contest
Moved to 05 Apr as 12 Apr will be used for the 10th STePS
13
12 Apr 		NO CLASS (except last homework)

Clash with the 10th STePS on this day, 5-9pm and I have to evaluate final projects of my other Sem2 module CS3226 at the same time too...
Reading
Week 		No final assessment, go and save your other modules

Hall of Fame

This table records the previous top students of CS3233 under Dr Steven Halim (rank 1 up to at most rank 2) of that Academic Year and their current known affiliation.

AY (Iteration) Flag and Name Current Job
2008/09 (1) Ngo Minh Duc Addepar
2008/09 (1) Nguyen Hoanh Tien Microsoft
2009/10 (2) Trinh Tuan Phuong Quantcast
2010/11 (3) Koh Zi Chun Microsoft
2010/11 (3) Harta Wijaya Facebook
2011/12 (4) Yang Mansheng ?
2012/13 (5) Nguyen Tan Sy Nguyen Anduin Transactions
2013/14 (6) Nathan Azaria Facebook
2013/14 (6) Jonathan Irvin Gunawan Google (SG)
2014/15 (7) Stefano Chiesa Suryanto 4th year UG
2014/15 (7) Vu Dinh Quang Dat 4th year UG
2015/16 (8) Nguyen Quang Dung 3rd year UG
2015/16 (8) Truong Ngoc Khanh Garena/Sea
2016/17 (9) Tan Jun An 3rd year UG
2016/17 (9) Agus Sentosa Hermawan 2nd year UG