2010/2011, Semester 2

School of Computing (Computer Science)

Modular Credits: 4

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 2: C++ STL & Java API and discussion of one Advanced Data Structures:

Week 3: Complete Search; Divide & Conquer; and Greedy Algorithms.

Week 4: Dynamic Programming (basic). (CNY holiday during Week04;

Week 5: Graph (basic): DFS/BFS/MST (MST skipped).

Week 6: Graph (basic): Shortest Paths + Special Graph 1 (Tree/DAG) - Euler Graph skipped.

Mid-semester break

Week 7: Mid-semester team contest. Week01-06 stuffs.

Week 8: Dynamic Programming (medium): DP on General Graph/Tree/DAG/String, formulating non trivial DP states+transitions

Week 9: Graph (medium): Max Flow + Special Graph 2 (Bipartite Graph).

Other computational problems frequently appear in programming contests:

Week 10: Mathematics: Overview of various mathematics-related problem + tips.

Week 11: String Processing: Basic string processing skills, Ad Hoc string problems, Suffix Tree/Array.

Week 12: (Computational) Geometry.

Week 13: Final team contest. Week01-12 stuffs.

Some teaching material is available in this public website: https://sites.google.com/site/stevenhalim/home/material

The programming languages used in this course are C/C++ (main) and Java (secondary).

1 Mid-Semester Team Contest (10%)

1 Final Team Contest (30%)

Weekly Homework (18%)

Term Assignment (22%)

See cs3233_rules_regulations.pdf in IVLE Workbin.

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

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

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

See cs3233_rules_regulations.pdf in IVLE Workbin.

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

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 easy + 1 medium problems that have been taught in previous week(s) + 1 hard problem that can be from any source.

Then, the course material will be delivered via lectures.

On most weeks, classes will end by 9-9.15pm.

For weekly homeworks, students are expected to:

a. read the corresponding sections in the

b. do

c. continue attempting mini contest

There is also a term assignment where student has to

Students have to do lots of programming in this course.

No |
CS3233 Staffs |
UVa |
LA |
TopCoder |
Contests |
Homework |
TC |
LA |
All |

1 | Steven Halim | 32900 | 20648 | stevenhalim | |||||

2 | Victor Loh Bo Huai | 8764 | 3326 | roticv | |||||

3 | Felix Halim | 339 | felix_halim | ||||||

4 | Ngo Minh Duc | 2224 | Duc | 3: mini contest 10 | Wk11 (ch6/string) - not graded yet | ||||

5 | Su Zhan | stugrammer | 20: final contest | Wk7 (be a problem setter) - not graded yet | |||||

No |
NUS Students |
UVa |
LA |
TopCoder |
Contests (Max 37 So Far) |
Homework (Max 12 + bonus So Far) |
TC |
LA |
All |

1 | Koh Zi Chun | 69534 | zichun | 24.5 (3 to TermAsg) | 9.6 (good technical contribution) | 3 | 3.3 | 40.4 | |

2 | Harta Wijaya | 30959 | Harta | 21.0 | 11.6 (very good book review; technical side) | 3 | 3.3 | 38.9 | |

3 | Chen Juncheng | 57516 | 22734 | Juncheng | 16.0 (3 to TermAsg) | 11.5 (very good book review: presentation side) | 2 | 8.7 | 38.2 |

4 | Yuan Yuan | 83993 | 27268 | littlepox | 17.0 (3 to TermAsg) | 11.0 (very good book review; technical side) | 4 | 3.3 | 35.3 |

5 | Sim Wenlong Russell | 81587 | 27063 | RussellSim | 12.5 (3 to TermAsg) | 10.9 (good book review) | 1 | 8.7 | 33.1 |

6 | Raymond Hendy Susanto | 81816 | 27065 | raymondhs | 14.5 | 9.9 | 2 | 5.4 | 31.8 |

7 | Aldrian Obaja Muis | 22972 | 26986 | justhalf | 15.5 | 7.8 | 3 | 5.4 | 31.7 |

8 | Bach Ngoc Thanh Cong | 84038 | 27069 | kenthanhcong | 17.0 (3 to TermAsg) | 8.6 | 2 | 3.9 | 31.5 |

9 | Tran Cong Hoang | 82241 | 27162 | sunredoc | 17.0 (3 to TermAsg) | 6.4 | 3 | 3.9 | 30.3 |

10 | Hassan Ali Askari | 35554 | 27070 | sunnybd | 13.0 | 7.2 | 1 | 8.7 | 29.9 |

11 | Hong Dai Thanh | 60556 | 27080 | nhahtdh | 13.0 | 11.0 (good book review; lots of UVa contribution) | 2 | 3.9 | 29.9 |

12 | Ding Mingzhe | 54667 | 27071 | blackgoldtimes | 13.0 | 10.9 (good book review; lesson summary) | 2 | 3.3 | 29.2 |

13 | Peter Phandi | 80375 | 27067 | ChsHymme | 12.5 (3 to TermAsg) | 8.1 | 2 | 5.4 | 28.0 |

14 | Tan Hiang Tat | 80866 | 27072 | truewt | 11.5 (3 to TermAsg) | 10.8 (good book review; presentation side) | 1 | 3.3 | 26.6 |

15 | Lee Ying Cong | 50461 | 27066 | akirap | 11.0 (6 to TermAsg) | 5.3 | 8.7 | 25.0 | |

16 | Fikril Bahri | 82576 | 27285 | fikr | 10.0 | 7.9 | 2 | 3.9 | 23.8 |

17 | Devendra Goyal | 84907 | 27251 | devness | 08.0 (3 to TermAsg) | 7.8 | 3.3 | 19.1 |

Note: This ranklist was correct before mini contest #10 and will no longer be updated to keep the final grade secret :)

Separate ranklist for IOI 2011 trainees:

http://algorithmics.comp.nus.edu.sg/wiki/training/ioi_workshop