This module aims to prepare students in competitive problem solving.
It will benefit NUS students who want to compete in 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, especially NUS current (2018/19) ICPC donors: Indeed Singapore, Seagroup, Jump Trading, DRW, Tezos.
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 AY2018/19) is ... technically only limited by the size of COM1-B-PL2 (46 PCs → will be Acer Nitro laptops soon) ... 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 (10 out of 189) are female...
Useful information to help you decide on whether you should offline register for CS3233:
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, ICPC (especially ICPC Asia Singapore Regional Contest 2015/2018), Google Code Jam, Facebook Hacker Cup, Topcoder Open, 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...
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 eight academic years were 4.57 , 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).
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 trainees (Sec2-JC2 students) beat you in (many) CS3233 contests. Try to ask CS3233 seniors who have taken (and survived) this module before applying!
Are you thinking on applying to top (or emerging) IT companies like NUS current (2018/19) ICPC donors: Indeed Singapore, Seagroup, Jump Trading, DRW, Tezos; or other IT companies like Google, 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.
Can you code in C++ (primary language), Java (second choice), and/or Python (a new one for this round)?
We will use C++ (11), Java (8), and Python (3.5.2 in Kattis, 2.5.1 :( in Mooshak for now until I am able to reconfigure Mooshak to accept Python 3) in CS3233 S2 AY2018/19. 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.
Do you want to learn interesting data structures, algorithms, (other programming language especially if C++ is not your primary language) 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 ICPC coach, ICPC Asia Singapore Regional Contest Director, the author of Competitive Programming text book (the official text book of this module, we will use 2018b version that is given for free onsite at ICPC Asia Singapore 2018 — Yes, all accepted students will get free CP3.18b courtesy of Tezos Southeast Asia).
Rating (out of 5.0, SoC avg ~4.1) | Jan-Apr 2019 (n=20+??) | 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) | Jan-Apr 2012 (n=24) |
---|---|---|---|---|---|---|---|---|
Module feedback | 4.7+? (Target) | 4.8 (PB) | 4.8 (PB) ▲ | 4.563 ▼ | 4.733 ▲ | 4.455 ▼ | 4.545 ▼ | 4.778 |
Module difficulty | 4.1-? (Target) | 4.1 | 4.3 | 4.563 :O | 4.067 | 3.909 | 4.364 | 4.444 |
Steven's teaching | 4.7+? (Target) | 4.8 | 4.8 ▲ | 4.603 ▼ | 4.863 (PB) ▲ | 4.548 ▲ | 4.455 ▼ | 4.778 |
Qualified Teaching Assistant:
Robin Christopher Yu a.k.a. robinyu (Philippines first Bronze medalist (2x), then Philippines first Silver medalist, and currently an NUS ICPC team member: team 3Sophomores, 3rd place in ICPC Jakarta 2018).
Usually, CS3233 TAs have teaching feedback rating of around ~4.5 too (i.e. very good).
Robin will be mostly available in NUS ICPC Lab (COM1-02-15), especially every Monday, 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 accepted 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 even last year's crazy rate, i.e. by showing Steven that the applicant can score at least 500 Kattis points (only 100 Kattis points in previous AY) by Monday, 14 January 2019, 08.59AM.
Note: This course registration section will not be prominent from Tuesday, 15 January 2019 onwards (Week 01). This behavior is normal. You can view it again by scrolling to the top of this page.
Date | News |
---|
Week | Self Reading from CP3.18b before class (Flipped Classroom) | Homework (Mon, 10.00am) |
Contest + Debrief (Mon, 5.30-6.45-7.15pm, PL2) |
Class Topics (Mon, 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 |
As many pages from CP1/2/3/3.17a/b/3.18a/b; At least from preface up to the end of Chapter 4; Note: For the actual semester, you must have a copy of CP3.18b to go through this course successfully | Lots of preparatory work especially for those who do not have competitive programming background yet | No contest yet; But if you are not a multi-lingual programmer yet, pick up both C/C++11 (main), Python3, and Java8 by yourself during holiday time | At home: Set up a (free) Kattis account (open), solve first few easy ≤ 2.5 pointer problems @ Kattis, then use Dec18/early Jan19 holiday (~6 weeks) to get ≥ 500 points (~200 AC of ~2.5 pointer problems or ~330 AC of ~1.5 pointer problems (first ~3+ pages sorted based on difficulty :O), use Steven's classification here) in Kattis by Mon, 14 Jan 19, 09.59am to ensure module acceptance, familiarize yourself with Ubuntu 16 (or 18) LTS with GNOME desktop, or self-read the older teaching materials in this public website |
01 14 Jan |
Preface to Chapter 1 (all pages) plus simple Ad Hoc problems in Chapter 9 Steven is away Thu, 17 Jan to Sun, 20 Jan 2019 a family event; No CS3233 class is affected; but HW1 grading may be delayed |
Do Kattis set #01 :) |
Mock Ad Hoc (after first lecture) |
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 21 Jan |
Chapter 2; Focus on Section 2.2, 2.4.3, and 2.4.4; Read the rest of Chapter 2 by yourself Decision to Drop CS3233 without penalty by Sun, 27 Jan 19 (email UG office for manual drop, cc to Dr Steven Halim) |
HW01 due Kattis set #01 due |
Mini 01 "Around Linear" Algorithms |
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 28 Jan |
Chapter 3, 4, and 8; Focus on Section 3.1-2, 4.2.3, 4.4.2-3, and 8.1-8.2; Read Section 3.3 and 3.4 by yourself |
HW02 due Solve Mini 01 B/C Kattis set #02 due |
Mini 02 Libraries |
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 04 Feb |
No Mon EV Class Due to CNY Week CNY Reunion Dinner on Mon, 04 Feb... CNY Day 1 on Tue, 05 Feb CNY Day 2 on Wed, 06 Feb |
Kattis set #03 due (auto, half basic graph, half complete search stuffs) |
No Mini Contest | No Lecture |
05 11 Feb |
Chapter 3, 4, 5, 6, 8, and 9; Focus on various sections about DP: Section 3.5, 4.7, 4.8.1, 5.4, 5.6, 5.9, 6.5, 8.3, 8.4.2, 8.4.4, 9.6, 9.19, and 9.29 Happy Valentine's Day (Thu) |
HW03 due Solve Mini 02 B/C Kattis set #04 due |
Mini 03 Complete Search Hongbao Contest sponsored by Jump Trading |
The Art of Stenography Dynamic Programming; "Instant" review of CS3230 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 |
06 18 Feb |
Chapter 8; Focus on the new Section 8.4; Optional: Read the first 1/3 of CS4234 material |
HW04 due Solve Mini 03 B/C Kattis set #05 due |
Mini 04 DP |
Coping with (NP-)hard Problems Summary of the first 1/3 of CS4234 - Optimisation Algorithms in CS3233 style. VisuAlgo: mvc, steinertree, tsp |
Recess 25 Feb |
Although we are not supposed to have any face to face activity this week, nobody prevents you to keep solving Kattis problems 'by yourself' :). Again, peruse Steven's classification here, this time probably aiming for the 3-4+ pointer problems... Decision to Drop CS3233 with 'W' grade by Sun, 03 Mar 19 Week 07-13 Plan TBA |
Nothing this week Enjoy your break (or enjoy solving random Kattis problems) |
No class |
No class |
07 04 Mar |
Chapter 4 and 9; Focus on Section 4.6 and 9.20; Optional: Read the Max-Flow material of CS4234 |
HW05 due (no mini contest in recess week) Kattis set #06 due |
Mini 05 (NP-)hard Problems Money Contest sponsored by TBC |
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 11 Mar |
Chapter 4, 8, and 9; Focus on Section 4.7, 4.8.4, 8.4.5, 9.6, 9.8, 9.12, and 9.16; Read the Graph Matching material of CS4234. |
HW06 due Solve Mini 05 B/C Kattis set #07 due |
Mini 06 Graph1 Network Flow |
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 18 Mar |
Chapter 5 and 9; Focus on Section 5.3-5.5; Read the rest of Chapter 5 by yourself; Plus Section 9.9, 9.10, and 9.23 NOI 2018 Competition; Fri-Sat, 22-23 Mar 19 |
HW07 due Solve Mini 06 B/C Kattis set #08 due |
Mini 07 Graph2 Matching |
NUMB3RS Mathematics overview with a movie; Focus on Java/Python Big Integer, Combinatorics, Number Theory (Extended Euclid, Modular Inverse, Chinese Remainder Theorem) VisuAlgo: cyclefinding |
10 25 Mar |
Chapter 6; Focus on Section 6.6; Read the rest of Chapter 6 by yourself |
HW08 due Solve Mini 07 B/C Kattis set #09 due |
Mini 08 Mathematics Money Contest sponsored by TBC |
(PS: We will do midterm team contest formation after Mini 08) A Glance at Bioinformatics String Processing; Focus on Suffix Trie, Suffix Tree, and Suffix Array VisuAlgo: suffixtree, suffixarray |
11 01 Apr |
Re-read Week 01-05 reading materials and CS1020/2010/2020/2040/C stuffs; Read "standard" graph topics by yourself (Section 4.1-4.5) |
No written HW Solve Mini 08 B/C Kattis set #10 due |
Midterm Team Contest CS2010/2020/2040/C + Week01-05 5.30-9.00pm (3h 30m) |
No lecture, we will do Midterm Team Contest on Week 11 :O VisuAlgo (for self-review): heap, hashtable, bst, graphds, dfsbfs, ufds, mst, sssp Steven and 3 past CS3233 students: Bay Wei Heng+Bernard Teo Zhi Yi+Sidhant Bansal (team 3body2) will go to Porto, Portugal to represent NUS for ICPC World Finals 2019. This Midterm Team Contest will be invigilated by Steven's colleague (TBC). It will be on Kattis (TBC) :O. |
12 08 Apr |
Chapter 7; Focus on Section 7.2, 7.3, 9.4; Read the rest of Chapter 7 by yourself Also something from Chapter 8/9 and something not found in CP3.18b |
HW09 due Solve some non AC midterm contest by yourself (optional) Kattis set #11 due |
Mini 09 String Money Contest sponsored by Jump Trading |
(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 08 April to complete CS3233 We will only end the class at 9.30pm on this night... |
13 15 Apr |
The entire CP3.18b book and beyond |
No written HW (HW10 during reading week) Solve Mini 09 B/C Kattis set #12 due |
Final Team Contest Week01-11 stuffs (geometry problemS exist!) 5.30-9.00pm (3h 30m) With food (TBC) |
No lecture, we will do Final Team Contest (should NOT clash with STePS this time, as we have moved to Monday night) Good Friday and Easter Sunday this Week |
Reading Week | Time for you to study for your other modules... unless you are chasing some more points from Kattis apprentice achievement... | HW10 (special) due |
Join NUS ICPC team selection (~Late August? 2019) |
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 as per last contact with Dr Steven Halim.
AY (Iteration) | Rank | Flag and Name | Best ICPC Record | Current Job |
---|---|---|---|---|
2008/09 (1) | 1 | ![]() |
World Finalist 2009 (HM) & 2010 (HM) | Addepar (US) |
2008/09 (1) | 2 | ![]() |
World Finalist 2009 (HM) & 2010 (HM) | Microsoft (US) |
2009/10 (2) | 1 | ![]() |
World Finalist 2012 (HM) & 2013 (joint-48) | Quantcast (SG) |
2010/11 (3) | 1 | ![]() |
World Finalist 2012 (HM) | Microsoft (US) |
2010/11 (3) | 2 | ![]() |
World Finalist 2012 (HM) & 2013 (joint-48) | Facebook (US) |
2011/12 (4) | 1 | ![]() |
N/A | Dynamic Technology Lab (SG) |
2012/13 (5) | 1 | ![]() |
World Finalist 2013 (joint-48) & 2016 (joint-14) | Anduin Transactions (VN) |
2013/14 (6) | 1 | ![]() |
World Finalist 2014 (joint-19) & 2015 (joint-28) | Facebook (UK) |
2013/14 (6) | 2 | ![]() |
World Finalist 2014 (joint-19) & 2015 (joint-28) | Google (SG) |
2014/15 (7) | 1 | ![]() |
Fourth place in Regional Asia Singapore 2015 | Improbable (UK) |
2014/15 (7) | 2 | ![]() |
World Finalist 2015 (joint-28) & 2018 (joint-56) | Dynamic Technology Lab (SG) |
2015/16 (8) | 1 | ![]() |
Tenth place in Regional Asia Phuket+Singapore 2015 | 4th year UG |
2015/16 (8) | 2 | ![]() |
Twentieth place in Regional Asia Singapore 2015 | Seagroup (SG) |
2016/17 (9) | 1 | ![]() |
Sixteenth place in Regional Asia Singapore 2018 | 4th year UG |
2016/17 (9) | 2 | ![]() |
World Finalist 2017 (joint-20) | 3rd year UG |
2017/18 (10) | 1 | ![]() |
Third place in Regional Asia Jakarta 2018 | 2nd year UG |
2017/18 (10) | 2 | ![]() |
Third place in Regional Asia Jakarta 2018 | 2nd year UG |
2017/18 (10) | 3 | ![]() |
Champion in Regional Asia Yangon 2018, World Finalist 2019 (Result TBA) | 3rd year UG |
There are two big scoring components: SP(eed) (from live contests, up to 60%) and DI(ligence) (from non-speed-related stuffs, up to 53%).
The theoretical max is therefore 113%, with just 62% needed to secure at least a B+ grade in this extremely competitive module.
The SP(eed) component is further divided into two sub-components: M(ini)C(ontest) (up to 36%) and T(eam)C(ontest) (up to 24%).
The DI(ligence) component is further divided into four sub-components: H(ome)W(ork) (up to 15%), (Problem)Bs (up to 9%), K(attis)S(ets) (up to 12%), and Ac(hievements) (up to 17%).
9 Weekly Mini Contests, three problems in 75 minutes, using Mooshak.
(9 weeks x (3%+0.5%+0.5%)/week = 36%).
Occasionally (if Steven is not that lazy), we may open problem D (or even E) which is (are) the easier form of problem A/B/C. We give bonus 0.5% for top 3 in each mini contest. We use strict binary grading (Accepted or not Accepted: Wrong Answer, Time Limit, Memory Limit, Runtime Error, etc) for our contests.
1 Midterm Team Contest (10%+0.5%=10.5%, 10 "original" problems, worth 1.0% each).
1 Final Team Contest (13%+0.5%=13.5%, 10 "original" problems, worth 1.3% each).
Bonus 0.5% for top 3 teams in both team contests.
Team size is three students.
If the class size is not divisible by 3, the last team can have 4 or 5 members.
10 Weekly Homework (10 weeks * 1.5%/week = 15%).
CP3.18b book review + solve certain written exercises + update the lecturer, 1.5%.
Scoring scheme: 0% = no submission, 0.5% = poor, 1% = default score, 1.5% superb.
Solve problem B of last week's mini contest at home, on your own pace, by next Mon 05.15pm (closed by the time Robin's consultation hour is over), if you fail to solve it during the live Mini Contest. Simply submit your code to Mooshak, TA will check your last submission @ Mooshak.
Scoring scheme:
0% = not AC in the actual mini contest and not attempted after one more week.
1% = managed to solve problem B during mini contest itself or before deadline.
There is no additional marks for solving problem C at home (for CS3233R students).
We use Kattis@NUS for this semester.
Steven selects ten targeted Kattis problems related to CS3233 topic of that week. To get 1% per week, student has to solve at least three (of any preferred difficulty level as indicated in Kattis) of the selected problems within the stipulated deadline (Monday night 09:00:00pm SGT of that week until Monday 05:29:59pm SGT of the following week).
One star = 1%, most achievements are manual entry: