2013/2014, Semester 2

School of Computing (Computer Science)

Modular Credits: 4

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.

Week | Contest Topics | Lecture Topics |
Self Reading from CP3 (Semi Flipped Classroom) |
Homework (due Wed, 14.00) |

-2/-1/0 | N/A | N/A |
As many pages from CP3 At least from preface up to the end of Chapter 2 |
Set up UVa account Solve one problem in UVa Then as many (easy) UVa problems for warming up |

1 15 Jan |
Mock 0 Ad Hoc |
Let's Talk CPIntroduction Brief Course Admins Clicker System (everyone has to loan it, compulsory system) Some "Wow" MomentsMock/Preview Contest (not graded, but has high standard) *Steven is away on 16-20 Jan 2014* |
Preface to Chapter 1 (all pages) Plus Section 9.4 (Bracket Matching), 9.14 (Inversion Index), 9.15 (Josephus), 9.19 (Magic Square), 9.27 (Postfix), 9.28 (Roman Numerals), and 9.34 (Towers of Hanoi) |
N/A |

2 22 Jan |
Mini 1 Linear Algorithms |
*Steven is away on 16-20 Jan 2014*Be A LibrarianMastery of Libraries (C++ STL & Java API) Mastery of Bit ManipulationBinary Indexed Tree(Decision to Drop CS3233 without penalty by the end of Week 02) |
Chapter 2 Focus on Section 2.2 (Bitmask) and 2.4.4 (BIT) Read the rest of Chapter 2 by yourself |
HW1 due uHunt series #1 due |

3 29 Jan |
Mini 2 Libraries |
Searching for AnswersIterative Techniques Recursive Backtracking State-Space Search (harder form of SSSP, Graph modeling + BFS/Dijkstra's)Meet in the Middle (Bidirectional Search) (CNY holiday during Friday and Saturday of Week03) |
Chapter 3, 4, and 8 Focus on Section 3.1-2, 4.2.2, 4.4.2-3, and 8.1-8.2 Read Divide and Conquer (Section 3.3)and Greedy (Section 3.4) by yourself |
HW2 due Solve Mini 1, prob B/C uHunt series #2 due |

4 05 Feb |
Mini 3 Search |
Don't Forget to Take NoteDynamic Programming (round 1, easier) Review of CS2010/CS2020 Dynamic Programming Materials DP and DAG, discussion of more DP examples. |
Chapter 3 and 4 But focus on Section 3.5-3.7 and 4.7-4.7.1 |
HW3 due Solve Mini 2, prob B/C uHunt series #3 due |

5 12 Feb |
Mini 4 DP1 (much easier) |
The Art of StenographyDynamic Programming (round 2, more challenging) Formulating non trivial DP states + transitionsDP on Math Problems, DP on String Problems, various DP tricks, DP speed up. |
Focus on Section 5.4, 5.6, 6.5, and 8.3, Plus Section 9.3 (Bitonic TSP), 9.5 (Chinese Postman Problem), 9.10 (Graph Matching), 9.20 (Matrix Chain Multiplication), and 9.21 (Matrix Power) |
HW4 due Solve Mini 3, prob B/C uHunt series #4 due |

6 19 Feb |
Mid-semester Team Contest Week01-05 stuffs 6-9.45pm (3h 45m) |
No new lecture topic |
Wk1-5 reading materials, Ch9, and CS1020/2010/2020Read "standard" graph topics by yourself(Section 4.1 to 4.5) Note: All these have been covered in CS2010/20 |
HW5 due Solve Mini 4, prob B/C uHunt series #5 due |

- | - |
Recess week(Decision to Drop CS3233 with 'W' grade by the end of recess week/02 Mar 2014) |
- |
uHunt series #6 due (DO NOT FORGET) |

7 05 Mar |
Mini 5 DP2 (harder) |
How to (Theoretically) Prevent Flood?Graph (round 1): Network Flow and applicationsMax Flow: Ford Fulkerson's, Edmonds Karp's Applications: Bipartite Matching with Capacity, Min Cut, Multi Sources/Sinks, Vertex Capacities, Independent Paths, Edge-Disjoint Paths, Min Cost Max Flow Flow Graph Modeling skill NOI 2014: (Competition, Sat 8 March 2013) |
Focus on Section 4.6 Plus Section 9.7 (Dinic's Algorithm), 9.13 (Independent and Edge-Disjoint Paths), and 9.23 (Min Cost (Max) Flow)) |
HW6 (special) due uHunt series #7 due |

8 12 Mar |
Mini 6 Graph1 Network Flow |
Social Development NetworkGraph (round 2): Graph Matching and applicationsUnweighted MCBM: Max Flow, Augmenting Path, Hopcroft Karp's, G + Aug Path Unweighted MCM: Edmonds's Matching Algorithm Weighted MCBM: Min Cost Max Flow (overview only) Weighted MCM: DP with Bitmask (only for small graph) Applications: Matching with Capacity, Vertex Cover, Independent Set, Path Cover |
Focus on Section 4.7.4 Plus Section 9.5 (Chinese Postman Problem), 9.10 (Graph Matching), 9.12 (Hopcroft Karp's Algorithm), and 9.24 (Min Path Cover on DAG) |
HW7 due Solve Mini 5, prob B/C uHunt series #8 due |

9 19 Mar |
Mini 7 Graph2 Matching |
NUMB3RSMathematics, Overview Focus on Java BigInteger, Combinatorics, Number Theory, a bit of Cycle-FindingNOI 2014: (Prize Giving Ceremony, 22 March 2014) |
Chapter 5 Focus on Section 5.3-5.5 Read the rest of the chapter by yourselfplus Section 9.8 (Formulas or Theorems), 9.9 (Gaussian Elimination), 9.21 (Matrix Power), and 9.26 (Pollard's rho) |
HW8 due Solve Mini 6, prob B/C uHunt series #9 due |

10 26 Mar |
Mini 8 Mathematics |
A Glance at BioinformaticsString Processing Focus on SuffixTrie, Suffix Tree, and Suffix Array |
Chapter 6 But focus on Section 6.6 Read the rest of the chapter by yourself |
HW9 due Solve Mini 7, prob B/C uHunt series #10 due |

11 02 Apr |
Mini 9 String |
Inside Video Games(Computational) Geometry Focus on Algorithms Points, Lines, and Polygon |
Chapter 7 But focus on Section 7.2 (Points+Lines) and 7.3 Read the rest of the chapter by yourself |
HW10 due Solve Mini 8, prob B/C uHunt series #11 due |

12 09 Apr |
Mini 10 (Comp) Geometry |
The Last Lecture |
Something from Chapter 8 and something not found in CP3 |
HW11 due Solve Mini 9, prob B/C uHunt series #12 due |

13 16 Apr |
Final team contest Week01-12 stuffs 6-9.45pm (3h 45m) |
No new lecture topic(Good Friday and Easter Sunday this week) |
The entire book and beyond |
Solve Mini 10, prob B/C uHunt series #13 due |

- | - |
Reading week No final exam |
- | HW12 (special) due |

The programming languages used in this course are C/C++ (main) and Java (secondary). It is much better if you are a multi-lingual programmer.

The 2 hours lecture, 1 hour tutorial, and 0 hour lab are combined into 3 hours lecture + hands-on session

Each class usually starts with 75 minutes top-coder individual programming contest, followed by 15 minutes break / discussion of past contests.

Each contest contains: 1 (very?) easy + 1 easy-medium problems that have been taught in previous week(s) + 1 medium-hard problem that can also be from previous week(s) or just simply "out of topic", usually harder/more creative (this one for CS3233R).

Then, the course material will be delivered via lectures.

On most weeks, classes will end by

For weekly homeworks (3+3 = 6 hours++), students are expected to read "Competitive Programming 3" textbook and attempt some written and programming exercises...

Students have to do

A.1. 10 Weekly Individual Contests (10 weeks x (3%+0.5%+0.5%)/week = 40%, three problems in 75 minutes)

A-very easy/easy: 1%

B-medium, 2%

C-usually very hard and from topics not taught in class, for CS3233R students, bonus 0.5% for CS3233/R students who can get this AC

Ocassionally (on some weeks), we may open problem D (or even E) which is (are) the easier form of problem A/B/C.

A.2. 1 Mid-Semester

A.3. 1 Final

Bonus 0.5% for top 3 in each individual contest (or top 3 teams in mid and final contest)

Binary grading (Accepted or not Accepted: Wrong Answer, Time Limit, Memory Limit, Runtime Error, etc)

Team = team of three students.

B.1. 12 Weekly Homework (12 weeks * 1.5%/week = 18%)

CP3 book review + solve designated written exercises + weekly update with the lecturer (details after each lecture), 1.5%

Scoring scheme: 0% = no submission, 0.5% = poor submission, 1% = default score, 1.5% superb submission

B.2. Solve problem B/C of last week's mini contest at home,

Scoring scheme: 0% = not AC in the actual mini contest, not attempted after one more week, 1% = managed to solve B at home before deadline, no additional marks for solving C at home (this is for CS3233R)

B.3. Set of "Achievements" (24%++)

One star = 1%, three stars = 3 %

1*.**Let it begins:** Solve any 1st UVa problem by Wednesday, 15 January 2014, 23:59 (this is after the introduction lecture)

2*.**Quick starter: **Solve a total of at least **40** UVa problems (from any category) by the end of Week02

We use http://uhunt.felix-halim.net/series for this semester.

Steven will select ten targetted UVa problems related to CS3233 topic of that week.

To get 1% achievement point, student has to solve three out of those ten problems within the stipulated deadline (Wednesday night 9pm of that week until Wednesday night 6pm of the following week).

Out of this 10, Steven will highlight one (or two) that is (are) "highly recommended" to be tried at home, but you can generally solve any 3 out of 10.

3*. Week #1, Ad Hoc

4*. Week #2, Data Structures and Libraries

5*. Week #3, Complete Search

6*. Week #4, Dynamic Programming 1

7*. Week #5, Dynamic Programming 2

8*. Week #6, Graph 1 (Basics) -- intersect NUS recess week

9*. Week #7, Graph 2 (Shortest Paths) -- during NUS recess week and intersect NUS Week 07

10*. Week #8, Graph 3 (Network Flow)

11*. Week #9, Graph 4 (Matching)

12*. Week #10, Mathematics

13*. Week #11, String Processing

14*. Week #12, Computational Geometry

15*. Week #13, Mix and Match

Total percentage so far: 15%

Awarded by TA:

16*.**High determination**: Objective title for student who always diligently solve problem B (solve = eventually AC) of all 10 weekly contests, be it during contest time or as homework assignment

Total percentage so far: 16%

Awarded by Lecturer: Steven

17*.**Surprise us**: Managed to surprise the teaching staffs by giving a better/more elegant solution/pinpoint bug in lecture, etc anytime during the semester (max claim: 1 time/student)

18*.**Active in class**: Subjective title for student who participated well during **various class activities** (answering in-lecture questions, asking questions, consultations, active in uHunt series, etc), awarded by Steven from Week 10 onwards

19***.**Bookworm**: *Subjective title* for student who diligently study and review CP3 book by the end of Week07 and by the end of Week13, awarded by Steven

20***.**UVa apprentice**: min(3%, 8 * X / 1774 * 3%), this is a comparison between what you manage to solve in UVa online judge (X) by the end of the semester (**Saturday, 10 May 2014**) compared to Steven's at the start of semester (1774 AC problems), multiplied by a scaling factor of 8 =)... or approximately 222 AC problems in one semester (it is possible for student to reach this number in 4 months of CS3233, proof: light_yang (Yang Mansheng, ex CS3233 student)).

Total percentage so far: 24%

We use Coursemology for maintaining the near-live scores of all CS3233 students week by week.

The level is capped to Level 100.

**No final exam, "no" Bell's curve, "easy to score", and a "very fun" course :)**

To get at least B+, student must score**at least 60 out of 100** from the assessment scheme shown above.

**Almost all** students in the past 5 years of CS3233 (2009, 2010, 2011, 2012, 2013) managed to achieve B+ or more.

One star = 1%, three stars = 3 %

1*.

2*.

We use http://uhunt.felix-halim.net/series for this semester.

Steven will select ten targetted UVa problems related to CS3233 topic of that week.

To get 1% achievement point, student has to solve three out of those ten problems within the stipulated deadline (Wednesday night 9pm of that week until Wednesday night 6pm of the following week).

Out of this 10, Steven will highlight one (or two) that is (are) "highly recommended" to be tried at home, but you can generally solve any 3 out of 10.

3*. Week #1, Ad Hoc

4*. Week #2, Data Structures and Libraries

5*. Week #3, Complete Search

6*. Week #4, Dynamic Programming 1

7*. Week #5, Dynamic Programming 2

8*. Week #6, Graph 1 (Basics) -- intersect NUS recess week

9*. Week #7, Graph 2 (Shortest Paths) -- during NUS recess week and intersect NUS Week 07

10*. Week #8, Graph 3 (Network Flow)

11*. Week #9, Graph 4 (Matching)

12*. Week #10, Mathematics

13*. Week #11, String Processing

14*. Week #12, Computational Geometry

15*. Week #13, Mix and Match

Total percentage so far: 15%

Awarded by TA:

16*.

Total percentage so far: 16%

Awarded by Lecturer: Steven

17*.

18*.

19***.

20***.

Total percentage so far: 24%

We use Coursemology for maintaining the near-live scores of all CS3233 students week by week.

The level is capped to Level 100.

To get at least B+, student must score