No class on 11 Nov. Contest #3 on 10 Nov, 9-12noon.
Homework 12 (due 11 Nov, 8 am)
Counting and Computation Geometry
Homework 11 (due 4 Nov, in class)
- Solve the three problems discussed in class:- (i) min cost PH assignment (ii) minimum forest clearance, and (iii) prove relationshop between MST/all-pair maximum bottleneck paths.
Homework 10 (due 28 October, 8am)
MST, Union-Find and Max Flow
Homework 9 (due 21 October, 8am)
Numbers and Big Numbers
Homework 8 (due 21 October, 8am)
Finish off problems for Contest 2 and Homework 7.
Contest 2 (7 October, 2-5pm)
Homework 7 (due 7 October, 8am)Please try 251 first so we can discuss during tutorial next Tue.
Homework 6 (due 30 September, 8am)Have a nice break!
Homework 5 (due 15 September, 8am)Please try to think about both questions before Tues so that we can discuss it during tutorial.
Homework 4 (due 9 September, 8am)Please try to finish up 10154 before Tues so that we can discuss it during tutorial.
- Roopak, Kin Fuai: 348, 10130, 10154.
- Bang, Chinh, Hoang: 10130, 10154, 10269.
- Son: 348, 10130, 10154, 10269.
Contest 1 (on 2 September)
Homework 3 (due 31 August, 8am)
- Chinh: 10003, 10069
- Bang: 10069, 10131
- Roopak: 10003, 10131
- Kin Fuai: 10003, 10131
- Hoang: 10069, 10131
- Son: 10003, 10069, 10131
Homework 2 (due 23 August, 8am)
- Written assignment: count number of mismatches (aka inversions). -- taken from cs1102 final, 2002/03 semester 1. (due in class)
- Programming assigment (same for everyone) 10487, 10037, 10026
Homework 1 (due 18 August, 8am)
- Chinh: 10267, 10142, 843
- Roopak: 100, 10267, 843
- Ren Yuan: 100, 10267, 843
- Bang: 10267, 10189, 843
- Kin Fuai: 100, 10267, 843
- Hoang: 10267, 10142, 843
- 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: Monday 10am - 12noon, 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).