15-295: Competition Programming and Problem Solving, Spring 2018

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.

Basic Information

Class Meetings: Wednesdays from 6:30-9:20pm, GHC 4307

Instructor: Danny Sleator <sleator@cs.cmu.edu>, Office: Gates 8113, Phone: 412-268-7563

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.

Weekly Problem Sets

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.

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.

#01 Jan 17: Dynamic Programming
#02 Jan 24: Shortest Paths Dijkstra Bellman-Ford and Floyd-Warshall
#03 Jan 31: Binary Search
#04 Feb 07: Disjoint Sets Read through page 3 of these notes.
#05 Feb 14: SegTrees Read section 2 and section 4 of these notes.
#06 Feb 21: Trees Laaksonen book chapters 14 and 18, Tree properties, e.g. center diameter, DP on trees, LCA, More LCA
#07 Feb 28: Games Sleator 251 lectures: Impartial Games Sums of Games, Laaksonen book chapter 25, Jaehyun Park's slides on basic game theory, Nimbers in competitive programming
#08 March 07: Geometry TopCoder Part I, TopCoder Part II, TopCoder Part III, Chapter 29 and 30 of Laaksonen Book
#09 March 21: Counting
#10 March 28: Number Theory: Laaksonen book chapter 21, Factoring (Pollard Rho Algorithm)
#11 April 04: Network Flows. Basic flows Min-cost flows
#12 April 11: No Theme.
#13 April 18: Strings. Some Class Notes, Chapter 26 of Laaksonen, Suffix automata, Aho-Corasick algorithm

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.

#01 Jan 17, 2018: Point values: 1,1,1.5,2,3,2  Problems  Contest Link  Solutions
#02 Jan 24, 2018: Point values: 1,1,1,1,2,2  Problems  Contest Link  Solutions
#03 Jan 31, 2018: Point values: 1,1,1,1.5,2,2,3  Problems  Contest Link  Solutions
#04 Feb 7, 2018: Point values: 1,2,1.5,2,3,3  Problems  Contest Link  Solutions
#05 Feb 14, 2018: Point values: 1,1,3,2,2,3  Problems  Contest Link  Solutions
#06 Feb 21, 2018: Point values: 1,2,2,2,3,3  Problems  Contest Link Solutions
#07 Feb 28, 2018: Point values: 1, .5, 2, 2, 2, 3, 3  Problems  Contest Link Solutions
#08 Mar 07, 2018: Point values: 1, 1.5, 1.5, 2, 2, 2, 2  Problems  Contest Link  Solutions
#09 Mar 21, 2018: Point values: .5, 1, 1, 2, 2, 3  Problems  Contest Link  Solutions
#10 Mar 28, 2018: Point values: 1, .5, 2, 2, 2, 2  Problems  Contest Link  Solutions
#11 Apr 04, 2018: Point values: 2, 2, 2, 2, 2  Problems  Contest Link  Solutions
#12 Apr 11, 2018: Point values: 1, 1, 2, 2, 2  Problems  Contest Link  Solutions
#13 Apr 18, 2018: Point values: .5, 1.5, 1.5, 1.5, 2, 2.5  Problems  Contest Link  Solutions
#14 May 02, 2018: Point values: .5, 1, 1.5, 2, 3, 3, 3   Problems  Contest Link 

Potential future topics:

Flow (Max Flow, Min Cost Flow, Matchings)
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)
Greedy Algorithms

Grading

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

Rules

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.

Logistics

Resources

A great 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.
Lecture Notes about min cost flow, along with an implementaiton.
Union-Find Lecture Notes.
Range Trees (AKA Fenwick Trees)
Link-Cut Trees (See detailed comments in this codeforces submission.)
Long Blog Post on Graph Algorithms


Danny Sleator
Last modified: Wed May 2 18:46:49 2018