CS3233

CS3233 Competitive Programming

Course Information

Instructor: Andrew Lim (S16 #08-05, 874-6891, 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 2-02 (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 / McGraw-Hill, 1990.

The Practice of Programming
Brian W. Kernighan, Rob Pike. Addison-Wesley, 1999.

The Algorithm Design Manual.
Steven S. Skiena. Springer-Verlag, 1998.

Algorithms.
Robert Sedgewick. Addison-Wesley. 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

Pre-requisites: CS1102 or experience in NOI/IOI related activities

How does CS3233 differ from CS3230 or CS6204?

• Hand-on
• Broader Scope
• Lesser Theoretical Stuff
• Much more hands-on 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 top-student
• Chance to represent National University of Singapore in the Annual ACM International Inter-collegiate Programming Contest.
• Free trip to Kyoto, Japan, December 1-4, 1999 and Orlando, USA, March 15-19 + allowances
• Possible Prize Money from the contests.

Grading (Tentative)*

Programming Tests [PT] Weekly Short Programming Tests (1-2 hrs) and 2 Long Programming Contests (3-5 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 NP-Completeness - Recognizing that a problem is NP-Complete	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