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 AY2017/18) 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 (8 out of 170) 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, IND ICO, 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/CS2040/C or equivalent (and preferably score A+ in all CS1101S+CS2020 (senior batch) or CS1010+CS1020+CS2010 (senior batch) or CS1010/CS1101S+CS2030+CS2040 (current batch))?

    This module has a very high performance bar and the average CAP of the students enrolled in the past six academic years were 4.3+ (not tracked) , 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 course project submissions (for project-based modules that have STePS on Wednesday night of Week 13) 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 2018 trainees (Sec2-JC2 students) beat you in (many) CS3233 contests. Read this nice module review by a senior: 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 NUS ACM ICPC team donors: Sea (Garena), Indeed Tokyo, Google, Jump Trading, (and one more TBC); or other IT companies like Facebook, Microsoft, Dropbox, MemSQL, Grab, 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, we will use 2017b version).

    Rating (out of 5.00) Jan-Apr 2018 (n=25??) Jan-Apr 2017 (n=16)
    Module feedback 4.500+?? (maintain) 4.800 (PB)
    Module difficulty 4.300?? (maintain) 4.300
    Steven's teaching 4.500+?? (maintain) 4.800

    Two Qualified Teaching Assistants:
    1. Gan Wei Liang a.k.a. pandamonium (Singapore two times IOI Silver Medalist 2012-2013, SGP coach 2016, and currently an NUS ACM ICPC team member, team Pandamiao).
    2. Ranald Lam Yun Shao a.k.a. ranaldlys (Singapore IOI Bronze→Silver→Gold Medalist 2012-2013-2014, SGP coach 2017, and currently an NUS ACM ICPC team member, also in team Pandamiao).
    Usually, CS3233 TAs have teaching feedback rating of around ~4.500 too (i.e. good ones).
    Wei Liang and/or Ranald 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 much more rigorous than usual, i.e. by showing Steven that the applicant can score at least 100 Kattis points by Sunday, 14 January 2018, 23.59.

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

News

Date News

Jan-Apr 2018 Temporary Student List

No Flag Name Course/Year Qualified? Kattis account/rank/points (21 Nov 17)
1 Singaporean Ranald Lam Yun Shao COM/1 Obviously, he is enrolled in class roster only for 'administrative purposes' ranaldlys/112/739.3
2 Vietnamese Phan Duc Nhat Minh COM/1 Obviously, ACM ICPC World Finalist 2017 (VNU) and 2018 (NUS, next year) minh141198/1545/112.8
3 Indonesian Sergio Vieri COM/1 Obviously, ACM ICPC Team 3Freshmen (9th in Jakarta17) sergio.vieri/10084/12.7
4 Philippines Robin Christopher Yu COM/1 Obviously, ACM ICPC Team 3Freshmen (9th in Jakarta17) robinyu/655/231.8
5 Indonesian Kwee Lung Sin COM/1 Obviously, ACM ICPC Team 3Freshmen (9th in Jakarta17) ???/30000+/0.0
6 Singaporean Bernard Teo Zhi Yi COM/1 Obviously, he is enrolled in class roster only for 'administrative purposes' btzy/27889/1.0
7 Indian Sidhant Bansal COM/1 Obviously, ACM ICPC Team 3body (5th in Jakarta17) ???/30000+/0.0
8 Vietnamese Hoang Duong COM/2 Obviously, ACM ICPC Team Tourism (13th in NhaTrang16), CS2040C Lab TA hoangduong/2389/72.0
9 Singaporean Bay Wei Heng COM/2 Obviously, ACM ICPC Team Pikachu (15th in Jakarta17) bay-wei-heng/84/913.4
10 Malaysian Ho Yi Hang COM/3 Obviously, Malaysian IOI team leader 2017 :O yihangho/3564/47.2
11 Singaporean Ng Yi Chong Raynold COM/2? Yes, joined NUS ICPC Selection 2017 and have collected more than 100.0 Kattis points raynold-ng/746/213.4

Lesson Plan

The lesson plan is easy to remember: All our face to face activities are on Wednesdays, but basically you will work for the entire week for the entire semester 2 if you take this module, possibly harming the Continuous Assessment (CA) marks of your other modules.

  1. Students read the assigned CP3.17b readings before coming to the Wednesday class.
  2. Then, students complete weekly homework (of previous week) before every Wednesday, 10.00am, problem Bs by Wednesday, 4.30pm, and Kattis set of that week by Wednesday, 8.59pm (preferably by 5.30pm, before the next class).
  3. Then, students come to class, ready to attempt the weekly mini contest (with time and peer-(or young Sec/JC student)-pressure) every Wednesday, 5.30-6.45pm.
  4. Then, TA will give immediate on-the-spot solution discussion until at most 7.15pm (max 25 minutes with buffer).
  5. Finally, after a short break, Steven will give more eye-opening lecture about related (but not 100% the same as what you have read by yourself at home) problem solving techniques every Wednesday, 7.30-8.50pm (max 1h 15m with buffer). Steven will have to dismiss everyone from PL2 latest by 9pm.
  6. We repeat this throughout the semester :).
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
-06/-05/
-04/-03/
-02/-01
No class yet but some old teaching materials are available in this public website
01
17 Jan
Let's Talk CP

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

Mastery of Libraries (C++ STL & Java API); Focus on Bit Manipulation and Binary Indexed (Fenwick) Tree
03
31 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
07 Feb
The Art of Stenography

Dynamic Programming; Quick review of CS2010/CS2020 DP Materials; Focus on relationship between DP and DAG via discussion of a few non-classic DP examples; Focus on formulating non trivial DP states + transitions, A bit of DP speed up ideas
05
14 Feb
Coping with (NP-)hard Problems

Summary of the first 1/3 of CS4234 - Optimisation Algorithms in CS3233 style.
06
21 Feb
No lecture, we will do Midterm Team Contest
Recess
28 Feb
No class
07
07 Mar
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; Introducing Push-Relabel algorithm; Focus on Flow Graph Modeling skill and applications
08
14 Mar
Social Development Network

Quick overview of Graph Matching; Unweighted or Weighted MCBM or MCM; Introducing Edmonds's (Blossom Shrinking)/Matching algorithm and Hungarian/Kuhn Munkres's algorithm; Focus on (Bipartite) Graph Modeling skill and applications
09
21 Mar
NUMB3RS

Mathematics Overview; Focus on Java BigInteger, Combinatorics, Number Theory, a bit of Cycle-Finding
10
28 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
04 Apr
(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 04 April to complete CS3233
We will only end the class at 9.30pm on this night...

12
11 Apr
No lecture, we will do Final Team Contest
13
18 Apr
NO CLASS (except last special homework)

Clash with the 12th STePS on this day, 5-10pm
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 (US)
2008/09 (1) Nguyen Hoanh Tien Microsoft (US)
2009/10 (2) Trinh Tuan Phuong Quantcast (SG)
2010/11 (3) Koh Zi Chun Microsoft (US)
2010/11 (3) Harta Wijaya Facebook (US)
2011/12 (4) Yang Mansheng ?
2012/13 (5) Nguyen Tan Sy Nguyen Anduin Transactions (VN)
2013/14 (6) Nathan Azaria Facebook (UK)
2013/14 (6) Jonathan Irvin Gunawan Google (SG)
2014/15 (7) Stefano Chiesa Suryanto Looking for job in S2
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 Sea (SG)
2016/17 (9) Tan Jun An 3rd year UG
2016/17 (9) Agus Sentosa Hermawan 2nd year UG
2017/18 (10) You? ??? year UG