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.
Some students may go on to participate in the ACM ECNA regional event (which occurs in the fall) and possibly even the World Finals (which occurs in the spring).
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:20pm, GHC 4307
Instructor: Danny Sleator <sleator@cs.cmu.edu>, Office: Gates 8113, Phone: 412-268-7563
Teaching Assistant: Ashish Vasava <avasava@andrew.cmu.edu>
Google 15-295 Group: http://groups.google.com/group/15-295 (Required)
Codeforces 15-295 Group: http://codeforces.com/group/KIrM1Owd8u/contests (Required)
Name List: Put your names here (Required)
Grade Spreadsheet: Tabulation of Scores
For more information on how to join these groups, etc, see the Logistics section below.
Most problem sets will have a theme announced in advance, along with links so you can learn about the material before class if you want. There may be an occasional "mini-lecture" in the classroom from 6 to 6:30, before the contest starts. The mini-lecture will cover the theme topic for the contest, and be announced via email in advance.
The weekly contests will take place on Codeforces. They are classified under a "Codeforces Group" called 15-295. Click on this link to see a list of contests for this course and to participate in it.
The point values of the problems for each weekly contest are tabulated below, along with a solutions page which is based on contributions from students and staff in the class.
Current Contest
#14 May 01: Point values:1,1,1,2,3,3,3 Problems Contest Link Solutions
Finished Contests
#13 Apr 24: Point values:1,1.5,2,2.5,3,3 Problems Contest Link Solutions
#12 Apr 17: Point values:.5,1,2,2,2.5,3 Theme: Games Problems Contest Link Solutions
#11 Apr 10: Point values:1,1.5,1.5,2,2.5 Theme: Data Structures Problems Contest Link Solutions
#10 Apr 03: Point values:.5,.5,1,1,2,2 Theme: Counting and Probability Problems Contest Link Solutions
#09 Mar 27: Point values:1,2,2,3,3,3 Theme: Geometry Problems Contest Link Solutions
#08 Mar 20: Point values:1,2,2,3,3,3,3 Theme: String Algorithms Problems Contest Link Solutions
#07 Mar 06: Point values: 1,2,1,2,3,3,3 Theme: Number Theory Problems Contest Link Solutions
#06 Feb 27: Point values: 1,2,2,3,3,3 Theme: Trees Problems Contest Link Solutions
#05 Feb 20: Point values: 1,1,1.5,2,1.5,3 Theme: Flows and matchings Problems Contest Link Solutions
#04 Feb 13: Point values: .5,.5,1,2,1.5,3,3 Theme: DFS in Graphs Problems Contest Link Solutions
#03 Feb 06: Point values: 1,2,1,3,3,2,3 Theme: Shortest Paths Problems Contest Link Solutions
#02 Jan 23: Point values: .5,.5,.5,.5,1,2,2,3 Theme: Dynamic Programming Problems Contest Link Solutions
#01 Jan 16: Point values: 1,1,2,3,3,3 Problems Contest Link Solutions
Potential contest themes:
Dynamic Programming
Greedy Algorithms
Binary Search
Shortest Paths
Depth-First Search and Strong Components
Flow (Max Flow, Min Cost Flow, Matchings)
Trees -- properties and how to exploit them
Impartial Games
Bit Operations
Counting
Data structures (Disjoint Sets, SegTrees, FenwickTrees, Link-Cut trees)
String Algorithms (KMP, Z-algorithm, Karp-Rabin, Suffix Arrays)
Number Theory (GCD, Factoring, Primality Testing, Arithmetic mod p)
Geometric Algorithms (Geometric primitives, Sweep Line, Canonical Form)
FFT (over Complex Numbers, over Finite Fields)
Linear Algebra (Linear Programming, Gaussian Elimination)
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. (This site run rated contests approximately every two weeks.)
Let me be more specific. Each problem that we give has some number of points between 0.5 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. (Y only counts problems B, C, etc. (NOT A, they're too easy, and not Div 3) solved during rated contests. Virtual contests are not rated.) Your score in the course is X + X'/2 + Y.
Here is how your grade is determined:
score ≥ 25: A
score ≥ 15: B
score ≥ 10: C
score ≥ 5: D
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.
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.)
To join the 15-295 codeforces group, first create your codeforces account. Then go to this 15-295 Codeforces Group page. On this page you should see a list of the contests created for this course.
After you've logged in with your codeforces account and clicked the link above to get to the group page, toward the right side of the page click on the link to join the group. (You only have to join once.) Then a "Register" link should appear next to the contest. Click on this link to register for the contest. After that another "Enter" link should be available for you to join the contest (if it has already started).
As we proceed through the semester we will tabulate your results and put them into the grades document mentioned above.
If you have a laptop bring it to class. If you don't you will have to work in one of the clusters.
In case you're unfamiliar with how to deal with standard input and standard output, here is a link to a document showing the solution to a problem in several different languages.
The Competitive Programmer's Handbook by Antti Laaksonen covers (perhaps somewhat superficially) many topics that come up in competitive programming.
The E-Maxx Algorithms in English is a great source on many algorithms. It includes algorithm descriptions, analysis and code in C++.
Last semester's course has links to the topics for each of those contests, as well as solutions to many of the problems.
A way to get started and to improve is via the USACO training site. They've developed a series of lessons along with corresponding problems. It will take you from a beginner to a strong contest programmer.
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.
You can also do old problems on codeforces. Just go to codeforces.com/contests and click "enter" on any of the contests. You can then try solving problems. You can also go to the scoreboard of the contest and click on other people's solutions to see their code. This is a great way to learn.
Feel free to contact (email or stop by) the instructor or the TA any time to discuss problems, including during class.
Here are a few tutorials about important algorithms:
A segment tree implementation and tutorial.
Range Trees (AKA Fenwick Trees)
Lecture Notes about min cost flow, along with an implementaiton.
Union-Find Lecture Notes.
Link-Cut Trees (See detailed comments in this codeforces submission.)
Impartial Games (i.e. Nim-like games), Sums of Games
The Z Algorithm for Strings
Long Blog Post on Graph Algorithms
TODO: Add to this list