In this course you will learn the techniques and skills needed to solve algorithmic programming contests problems such as those that appear on the ACM ICPC, Codeforces, and Topcoder. Most of your time will be spent writing programs on your own to solve problems.
But the skills you will pick up from the course are far more valuable than just enabling you to win contests. Many of the algorithms and techniques are classic ones that every computer scientist should know. You will also learn to think about algorithms in a deeper way, because many of the problems require you have to devise a new algorithm, not just apply a classic one. These skills will be of great value in your other classes, in your job interviews, and in your future work.
Class Meetings: Wednesdays from 6:30-9:30pm, GHC 4307
Instructor: Danny Sleator <sleator@cs.cmu.edu>, Office: Gates 8113, Phone: 412-268-7563
Additional Help Available From:
Jason Li <jmli@andrew.cmu.edu>
Google Group: http://groups.google.com/group/15-295 (Required)
Name List: Put your names here (Required)
Grade Spreadsheet: Tabulation of Scores
To enter the on-line judge for one of these contests, click here then click the "Enter" button on the appropriate contest.
Solutions to problems of January 20, 2016
Solutions to problems of January 27, 2016
Solutions to problems of February 3, 2016
Solutions to problems of February 17, 2016
Solutions to problems of February 24, 2016
Solutions to problems of April 27, 2016
Here are a few of the problem sets used for team training this spring:
NEERC Moscow Subregional 2015
NEERC Northern Subregional 2015
This course is 5 units. Each week you will be given several problems to try to solve during class. You will be allowed (for half credit) to solve these problems during the week after the contest ends. You can also get credit for solving problems during rated contests on Codeforces and Topcoder. (These sites run rated contests approximately every two weeks.)
Let me be more specific. Each problem that we give has some number of points between 1 and 3. Let X be the total number of points of the problems you solve in class. Let X' be the total number points of the problems you solve in the week after class. Let Y be the number of Codeforces problems you solve and let Z be the number of topcoder problems you solve. (Y and Z only count problems solved during rated contests.) Your score in the course is X + X'/2 + Y + Z.
Here is how your grade is determined:
score ≥ 25: A
score ≥ 15: B
score ≥ 10: C
score ≥ 5: D
When you do a Codeforces or TopCoder rated contest, please email me that you have done it so that I can incorporate that into your grade. For Codeforces problems in Div 2, problems A and B are 1 point and the rest are 2 points. For Codeforces Div 1 and TopCoder all problems are 2 points.
There's one more twist to the system. If you've taken the class before, then you will not get credit for 1 point problems. You can still do them for fun, but you should be focusing on the harder problems.
You can make use of generic on-line resources while solving problems. These include things like language documentation, API documentation, algorithm descriptions, terminology, etc. You should not search for or make use of code written by others to solve the specific assigned problem.
If you're stuck on a problem, you are welcome to discuss it with another student in the class, or the course staff. Keep the level down so as not to disturb those around you.
During the selection rounds (see below), discussion with classmates is not allowed. Clarifications can be obtained from the course staff.
Everyone in 15-295 and/or on any programming team should be in http://groups.google.com/group/15-295. This is how we communicate with the class.
Everybody in the class is required to have a Codeforces account. We will be running our weekly contests on the Codeforces website via a mechanism called "mashups". If you do not already have an account on Codeforces, please create one. And add your name along with your Codeforces handle name to this google doc. (It's the same one in Basic Information list above.)
As we proceed through the semester we will tabulate your results and put them into this document.
If you have a laptop bring it to class. If you don't you will have to work in one of the clusters.
If there is demand we may also set up a piazza page for the course.
There are a number of excellent tutorials on the algorithms and techniques needed to solve these kinds of contest programs on Topcoder's Data Science Tutorials web site.
Feel free to contact (email or stop by) the instructor or the TA any time to discuss problems, including during class.
Basics, like reading from standard in
A segment tree implementation and tutorial.
Lecture Notes about min cost flow, along with an implementaiton.
Union-Find Lecture Notes.
We typically send five teams of three to the ACM ECNA regional event. This year it will take place on Saturday October 31 (Halloween). We drive to Youngstown on Friday afternoon, stay in a hotel, do the contest on Saturday, and return in the early evening on Saturday night.
The teams will be selected based on the results of two contests which will take place during regular class times on September 16th and September 23rd. I am only considering undergraduate students who are eligible to go to the World Finals (you can't go to the world finals more than two times). The World Finals will take place in Bangkok Thailand, May 15-20, 2016. If you are interested in trying to be on a team, it is imperitive that you participate and do well in the two selection rounds on Sept. 16th and 23rd.