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, 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 AY2015/16) 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 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, etc), IOI, ACM ICPC (especially ACM ICPC Asia Singapore Regional Contest 2015), 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 four academic years were 4.33, 4.44, 4.43, and 4.45 (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.
4. Are you thinking on applying to top (or emerging) IT companies like Google, Facebook, Microsoft, Dropbox, MemSQL, Garena (NUS ACM ICPC official team sponsor), GrabTaxi, 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?
   • Lecturer: Dr Steven Halim, current Singapore IOI team leader, (former) NUS ACM ICPC coach, current 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 2015 (n=22)	Jan-Apr 2014 (n=19)	Jan-Apr 2013 (n=18)	Jan-Apr 2012 (n=24)
     Module feedback	4.733	4.455	4.545	4.778
     Module difficulty	4.067	3.909	4.364	4.444
     Steven's teaching	4.863	4.548	4.455	4.778

   • Teaching Assistants(s): Stefano Chiesa Suryanto (rank 1 of the 7th iteration of CS3233) and likely two others past/current NUS ACM ICPC team members.

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 attrition rate, the pre-acceptance selection will be made rigorous.

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

News

(Temporary) Ranklist

This table lists the current interested students who will take CS3233 in S2 of AY 2015/2016 (some are forced to take). The list is currently in alphabetical order. This list is by no means complete and will be updated over time. Steven will look for 20 NUS students (including exchange students) who are eligible before accepting the other applicants who are put on hold (up to 25 students). This table is last updated on 30 November 2015, 10.29pm.

Lesson Plan Show Past

The lesson plan is easy to remember: All our face to face activities are on Wednesdays.

1. Students read the assigned CP3 readings before coming to the Wednesday class.
2. Then, students complete weekly homework (of previous week) before every Wednesday, 2.00pm.
3. Then, students come to class, ready to attempt the weekly mini contest every Wednesday, 5.30-6.45pm.
4. Then, TA will give immediate on-the-spot solution discussion until 7.15pm.
   
5. Finally, after a short break, Steven will give more eye-opening lecture about related problem solving techniques every Wednesday, 7.30-9.00pm.
6. We repeat this throughout the semester :).

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)	Rank	Flag and Name	Best ICPC Record	Current Job
2008/09 (1)	1	Ngo Minh Duc	World Finalist 2009 (HM) & 2010 (HM)	Previously Facebook
2008/09 (1)	2	Nguyen Hoanh Tien	World Finalist 2009 (HM) & 2010 (HM)	Microsoft
2009/10 (2)	1	Trinh Tuan Phuong	World Finalist 2012 (HM) & 2013 (joint-48)	Quantcast
2010/11 (3)	1	Koh Zi Chun	World Finalist 2012 (HM)	Microsoft
2010/11 (3)	2	Harta Wijaya	World Finalist 2012 (HM) & 2013 (joint-48)	Garena
2011/12 (4)	1	Yang Mansheng	N/A	?
2012/13 (5)	1	Nguyen Tan Sy Nguyen	World Finalist 2013 (joint-48) & 2016 (TBC?)	4th year UG
2013/14 (6)	1	Nathan Azaria	World Finalist 2014 (joint-19) & 2015 (joint-28)	3rd year UG
2013/14 (6)	2	Jonathan Irvin Gunawan	World Finalist 2014 (joint-19) & 2015 (joint-28)	3rd year UG
2014/15 (7)	1	Stefano Chiesa Suryanto	Fifth place in Regional Bangkok 2014	2nd year UG
2014/15 (7)	2	Vu Dinh Quang Dat	World Finalist 2015 (joint-28)	2nd year UG
2015/16 (8)	1	TBA	TBA	TBA