2009/2010, Semester 2
School of Computing (Computer Science)
Modular Credits: 4
This module aims to prepare students in
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.
At least 'A-' grade in CS1102/C/S or special permission from instructor (e.g. had participated and did well in national or international level programming contest(s) like NOI, IOI).
Note: This semester, NUS students will also be accompanied by several NOI/IOI 2010 trainees from various top schools in Singapore. Arrangements have been made to respective school coordinators to make this happen.
Information for next year (Jan-Apr 2011):
Module registration will also be done
If you passed the basic pre-req, please bid via CORS.
If you are a 1st year student who has not taken CS1102/C/S or obtained less than 'A-' grade in that module,
e-mail the instructor (firstname.lastname@example.org)
to request for module pre-req waiver, then bid again via CORS.
Week 1: Introduction, Summary, Compressing CS1101/C/S and CS1102/C/S materials frequently appear in programming contests.
Week 2: C++ STL/Java Libraries and Advanced Data Structures: Union-Find, Segment Tree.
Week 3-5: Complete Search; Divide & Conquer; Greedy Algorithms, and Dynamic Programming (2 weeks).
Mid-semester break (+ Chinese New Year holiday)
Week 6-9: Graph (+ Mid-semester team contest on week 7, 1 week AFTER CNY break).
Week 10-12: Other computational problems frequently appear in programming contests: Mathematics, String Processing, (Computational) Geometry.
Week 13: Final team contest.
See "Lesson Plan" for more details.
Weekly + Mid-Semester + Final Contests (60%)
See contest.pdf in "Rules and Regulations" folder in IVLE Workbin
Weekly Homework (15%)
See homework.pdf in "Rules and Regulations" folder in IVLE Workbin
Term Assignment (25%)
See term_assignment.pdf in "Rules and Regulations" folder in IVLE Workbin
No final exam, No Bell's Curve, and "easy to score"
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.
Each contest contains: 1 easy + 1 medium problems that have been taught in previous weeks, and 1 hard problem that will be taught that week (or in future weeks).
Then, integrated hands-on lectures+tutorials will cover some of the materials tested in that week.
There is also a term assignment where student has to tackle 5 recent ACM ICPC problem sets (of about 8-10 problems each) over 1 semester.
All these imply that students are expected to do
programming problems per week in class (or as homework) plus another
problems per week as term assignment.