Competition Programming and Problem Solving

15-295 Spring 2020

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), the ACM ICPC North America Championship (which occurs early in the spring), and possibly even the ACM ICPC World Finals (which occurs later 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
Weekly Problems
Grading
Rules
Logistics
Training Resources
Learning Material

Basic Information

We have optional lectures on Monday evening at 6:00pm, and regular weekly meetings on Wednesdays at 6:30pm. The lectures will cover introductory content aimed at beginners of competitive programming. Although attendance to the lectures is optional, it is strongly encouraged for beginners.

Lectures (optional): Mondays from 6:00pm - 7:00pm, NSH 4305
Class Meetings: Wednesdays from 6:30-9:00pm, GHC 4307
Instructor: Danny Sleator <sleator@cs.cmu.edu>, Office: Gates 7205, Phone: 412-268-7563
Teaching Assistant: Daniel Anderson <dlanders@cs.cmu.edu>, Office: Gates 7001
Administrative Assistant: Tony Mareino <amareino@andrew.cmu.edu>, Office Gates 7227
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 Problems

THIS WEEK -- Shortest Paths in Graphs

This week, we will continue the theme of graph algorithms and talk about shortest path problems in graphs. The fundamental algorithms that you will need to learn to solve these kinds of problems are breadth-first search and Dijkstra's algorithm. Other algorithms, such as Bellman-Ford and Floyd-Warshall may also come in handy, but are far less common.

Practice Problems: Link
Contest Link: Here
Problem Set: Here
Solutions: Here

Week #5: Graph Traversal

This week we will talk about graph algorithms. This is a topic that will probably span multiple weeks as we cover things like shortest paths, minimum spanning trees, and network flows. For this week, we will focus on the fundamentals, and cover things like how to represent graphs and how to implement graph traversal algorithms.

Practice Problems: Link
Contest Link Here
Problem Set: Here
Solutions: Here

Week #4: Dynamic programming

This week, we will practice the use of dynamic programming (DP) as a technique to solve programming competition problems. DP is quite possibly the most frequently occuring algorithmic technique used in competitions, with every ICPC contest always featuring at least one, if not several problems that require it. Masting this technique is key to becoming a strong competitive programmer. DP revolves around two key concepts, optimal substructure, which means that a problem can be solved by breaking it into smaller versions of itself (much in the same way as divide and conquer), and memoization of overlapping subproblems, which means to cache the solutions to the smaller problems in case they need to be solved multiple times. Of all topics in competitive programming, it probably requires the most practice in order to master, so get started!

Practice Problems: Link
Contest Link: Here
Problem Set: Here
Resources: 451 Notes

Week #3: Binary Search

This week, we will solve problems that use the binary search technique. You might think of binary search as an algorithm for finding an element in a sorted list, but it is actually a much more general technique than that, and can be used to solve a wide range of problems. Essentially, binary search allows you to solve problems where you must minimize or maximize some quantity subject to some contraint, as long as that constraint is monotone. A constraint is monotone if it is true/false for all values of x up to some value, and then becomes false/true after that value. Binary search allows us to efficiently find this partition point, and hence solve the corresponding optimization problem. The practice problems this week should help you to learn to apply this powerfull technique.

Practice Problems: Link
Contest Link: Here
Problem Set: Here
Solutions: Here

Week #2: Fundamental Data Structures

This week, we will focus on the most commonly used and fundamental data structures in competitive programming. Specifically, we will review and practice using arrays, binary search trees, hashtables, and priority queues. Knowing and understanding how to use these data structures in your favourite programming language is crucial to being able to quickly implement solutions to problems. We will mainly use C++ to demonstrate, but the ideas should be applicable to any language that supports these data structures.

The three practice problems should give you some practice using binary-search-tree-based data structures (set and map in C++, or TreeSet and TreeMap in Java) and priority queues (priority_queue in C++, or PriorityQueue in Java). As always, remember to register for the practice contest via this page.

Practice Problems: Link
Contest Link: Here
Problem Set: Here
Solutions: Here

Week #1: Introduction

This week has no particular algorithmic theme. Instead, we will go over the basics of competitive programming and do our first contest on Codeforces. Please make sure you have a Codeforces account ready to go and understand how to upload your solutions to the problems. You should do some practice problems to get the hang of writing and submitting solutions to the Codeforces system.

We have created a practice contest to do just that. So go to this page and (1) join the group (right side) (2) register for the contest and (3) enter the contest. Then you will find three problems you can try to solve. The are: Lights in the Morning, Deconstructed Password and Fine-tuned Resistance.

Practice Problems: Link
Contest Link: Here
Problem Set: Here
Solutions: Here

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

To be more specific, you can earn points from the following sources:

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

Training Resources

There are many online resources available for you to train with if you intend to become a serious competitive programmer. You can find thousands of practice problems for you practice and improve your skills. Some good places to find practice problems include:

Learning Material

If you are a beginner looking for resources to learn the various topics that appear in typical contests, some good sources are:


Danny Sleator
Last modified: Wed Feb 19 21:58:16 2020