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.
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:
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...
This module has a very high performance bar and the average CAP of the students enrolled in the current and the past six academic years were 4.78 (remember, year 1 nowadays have much more S/U options) , 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).
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!
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.
We will use C++ (11), Java (8), and Python (3.5.2 in Kattis, 2.5.1 :( in Mooshak unless I am able to reconfigure Mooshak to accept Python 3) in CS3233 S2 AY2017/18. In this course, we are expecting students to be multi-lingual :O. Although a few ex-students had survived CS3233 with only Java, they struggled more compared to those who are well versed in C++ (fastest programming language for programming competitions). This time, Python (3) will be introduced. However, Python code is usually slow (albeit usually also shorter). An algorithm written in Python may get TLE while the same algorithm written in C++ pass the time limit.
(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=21) | Jan-Apr 2017 (n=16) | Jan-Apr 2016 (n=20) | Jan-Apr 2015 (n=22) | Jan-Apr 2014 (n=19) | Jan-Apr 2013 (n=18) |
---|---|---|---|---|---|---|
Module feedback | 4.5+?? (maintain) | 4.8 (PB) ▲ | 4.563 ▼ | 4.733 ▲ | 4.455 ▼ | 4.545 ▼ |
Module difficulty | 4.3?? (maintain) | 4.3 | 4.563 uh oh :O | 4.067 | 3.909 | 4.364 |
Steven's teaching | 4.5+?? (maintain) | 4.8 ▲ | 4.603 ▼ | 4.863 (PB) ▲ | 4.548 ▲ | 4.455 ▼ |
Two Qualified Teaching Assistants (they will teach in alternate weeks):
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, winner of ACM ICPC Manila 2017, member of IOI International Scientific Committee (ISC) for IOI 2020 host country).
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, winner of ACM ICPC Manila 2017, member of IOI International Technical Committee (ITC) for IOI 2020 host country).
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.
Known damages are (illustrations are in C++), but not limited to:
Fortunately, it is known that past CP-ers can somehow undo these damages to return back to normal SE practices, e.g. this one.
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 Monday, 15 January 2018 onwards (Week 01). This behavior is normal. You can view it again by scrolling to the top of this page.
Update on 16 Jan 2018: As of today, there are already 23 accepted + 2 admin only students. As I have to now cater for ~20 guest high school students (a few are still put on waiting list pending the actual situation of first class on Wed 17 Jan 2018), all other aspiring students from now-end of CORS round 3B will be redirected to apply for CS3233 in Jan-Apr 2019 instead, if they have not graduate by then...
Date | News |
---|
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.
Week | Homework (Wed, 10.00am) |
Class Topics (Wed, 7.30-8.50pm, PL2) |
||
---|---|---|---|---|
-06/-05/ -04/-03/ -02/-01 |
Lots of preparatory work especially for those who do not have competitive programming background yet | At home: Set up a (free) Kattis account, solve first few easy ≤ 2.5 pointer problems @ Kattis, then use Dec17/early Jan18 holiday (~6 weeks) to get ≥ 100 points (~50 AC of ~2 pointer problems or ~[60..70] AC of ~1.5 pointer problems, use Steven's classification here) in Kattis by Sun, 14 Jan 18, 11.59pm to ensure module acceptance, familiarize yourself with Ubuntu 14 (or 16) LTS with GNOME desktop, or self-read the older teaching materials in this public website | ||
01 17 Jan |
Continue solving various Kattis problems of your choice. |
Let's Talk CP Introduction; Brief Course Admins; Focus on delivering some "Wow Moments"; A Bit of C++11; Introduction to Python for ICPC, Mock/Preview Contest (not graded, but has high standard) |
||
02 24 Jan |
HW01 due Kattis set #01 due |
Be A Librarian Mastery of Libraries (C++ STL, Java API, & Python Standard Library); Focus on Bit Manipulation and Binary Indexed (Fenwick) Tree VisuAlgo: bitmask, segmenttree (optional), fenwicktree |
||
03 31 Jan |
HW02 due Solve Mini 01 B/C Kattis set #02 due |
Searching for Answers Iterative Techniques (the fancier ones); Recursive Backtracking (bitmask-based, reverse thinking, data compression, etc); State-Space Search (harder form of SSSP, Graph modeling + BFS/Dijkstra's) with Meet in the Middle (Bidirectional Search) VisuAlgo: bitmask, recursion |
||
04 07 Feb |
HW03 due Solve Mini 02 B/C Kattis set #03 due |
The Art of Stenography Dynamic Programming; "Instant" review of CS2010/CS2020 DP Materials; Focus on relationship between DP and DAG; Discussion of a few non-classic DP examples; Formulating non trivial DP states + transitions VisuAlgo: bitmask, recursion |
||
05 14 Feb |
HW04 due Solve Mini 03 B/C Kattis set #04 due |
(PS: We will do midterm team contest formation after Mini 04) Coping with (NP-)hard Problems Summary of the first 1/3 of CS4234 - Optimisation Algorithms in CS3233 style. VisuAlgo: mvc, steinertree, tsp |
||
06 21 Feb |
No written HW due to long CNY weekend Solve Mini 04 B/C Kattis set #05 due |
No lecture, we will do Midterm Team Contest VisuAlgo (for self-review): heap, hashtable, bst, graphds, dfsbfs, ufds, mst, sssp |
||
Recess 28 Feb |
Nothing this week Enjoy your break (or enjoy solving Kattis problems) |
No class |
||
07 07 Mar |
HW05 due (no mini contest in recess week) Kattis set #06 due |
How to Prevent Flood? Quick overview of Network Flow; Quick review of Ford Fulkerson's Max Flow algorithm variants: Edmonds Karp's and especially Dinic's (short comparison with Push-Relabel); Focus on Flow Graph Modeling skill and applications VisuAlgo: maxflow |
||
08 14 Mar |
HW06 due Solve Mini 05 B/C Kattis set #07 due |
Social Development Network Quick overview of Graph Matching; Unweighted or Weighted MCBM or MCM; Introducing Kuhn Munkres's (Hungarian) algorithm and Edmonds's (Blossom Shrinking)/Matching algorithm; Focus remains on (Bipartite) Graph Modeling skill and applications VisuAlgo: maxflow, matching |
||
09 21 Mar |
HW07 due Solve Mini 06 B/C Kattis set #08 due |
NUMB3RS Mathematics overview with a movie; Focus on Java/Python Big Integer, Combinatorics, Number Theory (Extended Euclid, Modular Inverse, Chinese Remainder Theorem) VisuAlgo: cyclefinding Note: Minh (and 2 ex CS3233 students) will disappear for Hello India x Russia Programming Bootcamp as one of team DomiNUS preparation for ACM ICPC World Finals 2018, 21-31 March 2018 |
||
10 28 Mar |
HW08 due Solve Mini 07 B/C Kattis set #09 due |
A Glance at Bioinformatics String Processing; Focus on Suffix Trie, Suffix Tree, and Suffix Array VisuAlgo: suffixtree, suffixarray Note: Minh is still on Leave of Absence |
||
11 04 Apr |
HW09 due Solve Mini 08 B/C Kattis set #10 due |
(PS: We have to take class photo tonight, after Mini 09, then do final team contest formation) Inside Video Games (Computational) Geometry; Focus on Algorithms on Points, Lines, and Polygon, Art Gallery Problem VisuAlgo: polygon, convexhull (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 written HW Solve Mini 09 B/C Kattis set #11 due |
No lecture, we will do Final Team Contest |
||
13 18 Apr |
HW10 (special) deferred until Reading Week Kattis set #12 due |
NO CLASS (except last special homework) Clash with the 12th STePS on this day, 5-10pm Clash with ACM ICPC World Finals 2018, Beijing, China, 15-20 April 2018 |
||
Reading Week |
HW10 (special) due | No final assessment, go and save your other modules |
This table records the previous top students of CS3233 under Dr Steven Halim (rank 1 up to at most rank 3) of that Academic Year and their current known affiliation.
AY (Iteration) | Rank | Flag and Name | Current Job |
---|---|---|---|
2008/09 (1) | 1 | Ngo Minh Duc | Addepar (US) |
2008/09 (1) | 2 | Nguyen Hoanh Tien | Microsoft (US) |
2009/10 (2) | 1 | Trinh Tuan Phuong | Quantcast (SG) |
2010/11 (3) | 1 | Koh Zi Chun | Microsoft (US) |
2010/11 (3) | 2 | Harta Wijaya | Facebook (US) |
2011/12 (4) | 1 | Yang Mansheng | Dynamic Technology Lab (SG) |
2012/13 (5) | 1 | Nguyen Tan Sy Nguyen | Anduin Transactions (VN) |
2013/14 (6) | 1 | Nathan Azaria | Facebook (UK) |
2013/14 (6) | 2 | Jonathan Irvin Gunawan | Google (SG) |
2014/15 (7) | 1 | Stefano Chiesa Suryanto | Improbable (UK) |
2014/15 (7) | 2 | Vu Dinh Quang Dat | Graduating by July 2018 |
2015/16 (8) | 1 | Nguyen Quang Dung | 4thd year UG |
2015/16 (8) | 2 | Truong Ngoc Khanh | Sea (SG) |
2016/17 (9) | 1 | Tan Jun An | 4th year UG |
2016/17 (9) | 2 | Agus Sentosa Hermawan | 3rd year UG |
2017/18 (10) | 1 | Robin Christopher Cham Yu | 2nd year UG |
2017/18 (10) | 2 | Sergio Vieri | 2nd year UG |
2017/18 (10) | 3 | Bay Wei Heng | 3rd year UG |