CSE 392 - Programming Challenges

Spring 2012

Course Time: 3:50-5:10PM Tuesday-Thursday
Place: ESS 069
Instructor: Steven Skiena

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