At its best, computer science is an exciting blend of programming, mathematics, and problem solving. This course will introduce an interesting variety of subjects in programming, algorithms, and discrete mathematics though puzzles and problems which have appeared in the International ACM Programming Contest and similar venues.

The prerequisites for this course will be a course in data structures (CSE 214 or equivalent) or consent of the instructor. I hope to get a mix of students from sophomores to seniors.

This course is based on the book Programming Challenges: The Programming Contest Training Manual by Steven S. Skiena and Miguel A. Revilla, Springer-Verlag, New York, 2003.

Stony Brook teams have a good history of ACM ICPC activity, winning the Greater New York Regional contest to reach the World Finals in 2006 and 2009.

Course Documents

• Course syllabus with lecture schedule
• Homework Assignment Schedule
• 100 Problem Read Assignment
• Here are the complete set of lecture slides used for this semester's course.
• Online video from when I taught a similar course in Hong Kong in Spring 2009. This defeats the point if you are taking a live version at Stony Brook, put should be of use to those at other institutions.
• The grading of class assignments will be done by the www.programming-challenges.com robot judge. Students are urged immediately to go the site and register for our course section on this site, Stony Brook -- Spring 2012.
• Our backup judge will be the Univ. de Valladolid robot judge http://online-judge.uva.es/. Students are also urged to go the site and register as a new member (use your real name). Several of the assigned problems are regretably testable only with the UVa judge, so do them there.
• Following link is a sample solution for 3n+1 problem in Java. http://online-judge.uva.es/problemset/data/p100.java.html

  From the top page (http://uva.onlinejudge.org/), the sample code can be reached from following procedure: "Additional Information" (in left menu) -> Submission Specification (in left menu under "Additional Information") -> sample Java code (under Java Specification header).

  This code is almost in the same format as a template from programming-challenges.com. Here are some points and tips that students should take care about when they submit their code in Java.

  • Use a class named "Main" and place "public static void main(String args[])" method inside of Main class (it works as int main() function in C++). Then students can call another method in main method, as shown in the sample code).
  • Use "static String ReadLn (int maxLg)" method to read input. This is to recognize eof value so that the method will return null. Due to the reason above, the input should include eof if students want to test their code. On second thought this may not be an issues.
  • Use StringTokenizer, as shown in the sample code. I initially used split(" ") method to divide the string, but it actually contains some special characters (such as \r). StringTokenizer will ignore such special characters.
  • When the code throws runtime exceptions, programming-challenges.com only shows a message "Wrong Answer," whereas the result of uva.onlinejudge.org was "Runtime Error." It means that uva.onlinejudge.org gives the students more hints to find out their problems. However, it happened that when I submitted my code for "Minesweeper," uva.onlinejudge.org indicated it as "Wrong Answer" even though I got "Solved" at programming-challenges. In short, I recommend students to submit their code on both websites.
• Challenge Post is a nice collection of Tech Challenges. Maybe we should go for one as a class?
• Tunedit presents an interesting collection of real-world programming/scientific competitions.

Other Resources

• I taught this course at the Hong Kong University of Science and Technology in Spring 2009 as course COMP 300X.
• The complete programs from the book in C and in Java for download! (Java programs thanks to Derek Hu)
• Old lecture notes (in both pdf and html) with online audio are available from a 2003 version of the course.
• An interesting symposium on Perspectives on Computer Science Competitions for (High School) Students was held at Schloss Dagstuhl, January 22-27, 2006. Papers on several aspects of programming contests are available at this site.
• I was the featured presenter at the TopCoder Collegiate Challenge Finals, March 10-11, 2005, at the Marriott hotel in Santa Clara, CA. Watch/listen to my presentation in four parts: Part 1, Part 2, Part 3, and Part 4. Also see my reactions to the event.

  Finally, see Jennifer Jacobson's article about the event: Code Warriors: Young computer programmers battle for fame, money, and the love of algorithms , which appear in the Chronicle of Higher Education, April 8, 2005.

• Very old course notes (from the Spring 2001 edition of the course) for week 1, 2, including examples of C language string IO using getchar, gets, and scanf, 3, 4, 5, 6, 7 8, 9, 10 (see an alternate approach to dynamic programming), 11, 12, and 13
• Examples of ugly C code generated in student solutions.
• A good article on preparing for the ACM International Collegiate Programming Contest (ICPC) is here.
• Beginning January 11, 2010, acmqueue is offering an online programming competition based on the 2009 ACM International Collegiate Programming Competition (ICPC) Challenge.

  The Queue ICPC Challenge applies the rules used in the ACM ICPC Challenge, however the Queue competition is open to all acmqueue readers and not just university students.

  The 2010 Queue ICPC Challenge problem is a simple game called Capture. Participants code "players" in C++, C# or Java, and then submit them to compete in a tournament with other players.

  For more information on how to participate, go to the Queue ICPC Challenge page

• The USA Computing Olympiad for high school students also has an on-line training course. The US team competes in the International Olympiad in Informatics (IOI).
• Earn money for participating in programming contests from topcoder.com! See a nice TopCoder-oriented review of Programming Challenges.
• Other online judges / programming contests include the Ural State University judge, the Internet Problem Solving Contest, and the Peking University JudgeOnline.
• Similiar courses are taught at Duke University
• Jon Bentley's Programming Pearls site has lots of interesting information about algorithmic programming.
• See our photo gallery of ACM programming teams posed with the book.
• See book reviews for Programming Challenges: The Programming Contest Training Manual
• The books is now available in Korean Russian, Polish, Spanish, and Chinese translations.

Join the Stony Brook Computer Science Society!