CS3233: Competitive Programming

Announcement

No class on 11 Nov. Contest #3 on 10 Nov, 9-12noon.

Homework 12 (due 11 Nov, 8 am)

Counting and Computation Geometry

• 10065, 10157, 10173, 10247.

Homework 11 (due 4 Nov, in class)

Written assignment

• 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

• 10034, 10330, 10507.

Homework 9 (due 21 October, 8am)

Numbers and Big Numbers

• Roopak, Kin Fuai, Son: 701. 10018, 10220.
• Bang, Chinh, Hoang: 701. 10202, 10220.

Homework 8 (due 21 October, 8am)

Finish off problems for Contest 2 and Homework 7.

Contest 2 (7 October, 2-5pm)

• 10465, 10285, 10506.

Homework 7 (due 7 October, 8am)

Please try 251 first so we can discuss during tutorial next Tue.

• Roopak, Kin Fuai, Bang: 251, 10278. 10457.
• Son, Chinh, Hoang: 251, 10278. 10537.

Homework 6 (due 30 September, 8am)

Have a nice break!

• Roopak, Kin Fuai: 10160, 10004.
• Bang, Chinh, Hoang: 10160, 705.
• Son: 10160, 705, 10004.

Homework 5 (due 15 September, 8am)

Please try to think about both questions before Tues so that we can discuss it during tutorial.

• Everyone: 10032, 10160.

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)

• 10154, 10696

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

About CS3233

• 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.

Assessment

• 50% Homework (3-4 programming problems per week)
• 40% Contest (4 contests over the semester)
• 10% Presentations (present solution in class)

Textbook

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).