CS3233
CS3233 Competitive Programming
Course Information
Instructor: Andrew Lim (S16 #0805, 8746891, alim)
Lab Assistants:
Fu Zhao Hui (fuzhaohu)
Andy Kurnia (andykurn)
Course Web: www.comp.nus.edu.sg/~cs3233
When and Where (Tentative)
Lecture: Saturday 0900  1100 hrs in S16 202 (Tutorial Room 2)
Labs/Tutorial: Saturday 1100  1300 hrs
Exam: There will be no exam.
Textbooks
Below are some recommendations:
Introduction to Algorithms.
Thomas H. Cormen, Charles E. Leiserson, and Ronald L.Rivest.
The MIT Press / McGrawHill, 1990.
The Practice of Programming
Brian W. Kernighan, Rob Pike. AddisonWesley, 1999.
The Algorithm Design Manual.
Steven S. Skiena. SpringerVerlag, 1998.
Algorithms.
Robert Sedgewick. AddisonWesley. Many versions.
Aims:
 To prepare students in competitive problem solving in computing  covering techniques for attacking, solving, and writing computer programs for challenging computational problems.
 To prepare students for research work in experimental aspects of problem solving and algorithms.
Target Students:
 Interested in problem solving
 Interested in programming and experimentation
 Interested in advanced development work and data structures and algorithms
Prerequisites: CS1102 or experience in NOI/IOI related activities
How does CS3233 differ from CS3230 or CS6204?
 Handon
 Broader Scope
 Lesser Theoretical Stuff
 Much more handson programming
 More sweat and fun
How does CS3233 differ from the rest of the courses in SoC?
 40% is enough to get a good grade (B+ or higher)
 A prize for the topstudent
 Chance to represent National University of Singapore in the Annual ACM International Intercollegiate Programming Contest.
 Free trip to Kyoto, Japan, December 14, 1999 and Orlando, USA, March 1519 + allowances
 Possible Prize Money from the contests.
Grading (Tentative)*
Programming Tests [PT]
Weekly Short Programming Tests (12 hrs) and
2 Long Programming Contests (35 hrs) 
50 points 
Graded Homework [GH]
(Written and Programming Assignments) 
50 points 
Score = PT*GH 
2500 points 
BONUSES!!!!
 Online Judge Practice Questions
Each Question is worth K points. If a question is solved by X students, each student will get K/X points. K is the number of students in the course
 Grand Challenge Questions
Each is worth between 300 to 1000 points.
Details will be provided later.
Syllabus
TECHNIQUES 
APPLICATIONS 
 Data Structures and Sorting
 Greedy Method
 Divide and Conquer
 Dynamic Programming
 Backtracking
 Branch and Bound
 Graph Algorithms
 Heuristic Methods
 NPCompleteness  Recognizing that a problem is NPComplete

 Number Theoretic Problems
 Combinatorial Problems
 Graph Problems
 Geometry Problems
 Set and String problems

IOI
A subset of this course is taken by our International Olympiad in
Informatics XI representatives. See here for
details.
Back