- Modular credits: 4
- Workload: 2-1-0-3-3
- Prerequisites: At least grade A- in CS1102 or special permission. Mathematical aptitude and good CS1231 (Discrete Maths) background will help.
- Instructor: Ooi Wei Tsang. email: ooiwt.
- When and Where: Thurs 12noon-2pm, SR1.
This module aims to prepare students in competitive problem solving. It covers techniques for attacking and solving challenging computational problems. Fundamental algorithmic solving techniques covered include divide and conquer, greedy, dynamic programming, backtracking and branch and bound. Domain specific techniques like number theory, computational geometry, string processing and graph theoretic will also be covered. Advanced AI search techniques like iterative deepening, A* and heuristic search will be included. The module also covers algorithmic and programming language toolkits used in problem solving supported by the solution of representative or well-known problems in the various algorithmic paradigms.
To see if this module is suitable for you, explore around the Spanish Judge site and try out some of the easier problems there.
- 50% Homework (3-4 programming problems per week)
- 40% Contest (4 contests over the semester)
- 10% Presentations (present solution in class)
S. Skiena and M. Revilla, Programming Challenges: The Programming Contest Training Manual, Springer-Verlag, 2003.
As far as I know, this book is not available in Singapore. We will order in bulk from Amazon.com (US$28.67 + S&H).