In this course you will learn the techniques and skills needed to solve algorithmic programming contests problems such as those that appear on the International Collegiagte Programming Contest (ICPC), Codeforces, DMOJ, and AtCoder. Much of your time will be spent writing programs on your own to solve problems. (If you are interested in participating in the ICPC see this page.)
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. You will also become highly fluent in a programming language of your choice. These skills will be of great value in your other classes, in your job interviews, and in your future work, not to mention the satisfaction you will get from solving these problems.
Basic Information
Weekly Problems
Rules and Academic Integrity
Grading
Logistics
Training Resources
Learning Material Diversity, Equity and Inclusion
The regular weekly contests will take place Wednesdays beginning at 7pm in Posner Hall 151, and last 2 hours (you don't have to stay the whole time.) Most contests will have a theme, and will be preceeded by a lecture on the theme of the contest. The lecture will begin at 6:30 in the same room. The theme will be listed with the contest, along with links to tutorials or background materials. During the contests, the instructor and/or TA will be available for help in the classroom, or via Discord.
- Instructors: Danny Sleator <sleator@cs.cmu.edu> Thomas Draper <tradper@cs.cmu.edu>
- Teaching Assistant: William Tsin <wtsin@andrew.cmu.edu>
- Class Meetings: Wednesdays from 6:30 to 9:00, POS 151
- Discord server: join link
- Codeforces 15-295 Group (REQUIRED: Join This Group!)
- Name List (REQUIRED: Add Your Info!)
For more information on how to join these groups, etc, see the Logistics section below.
Our contest today has no theme, but it does feature an easy geometry problem (A) and a hard original problem by William (F)
Contest Link: Here
Solutions: For Editing For Viewing
For this contest, you are allowed to use the geometry library linked here. And here are some lecture notes from 15-451.
Contest Link: Here
Solutions: For Editing For Viewing
This week, we will explore even more graph algorithms. In particular, we will be looking at applications of maximum network flow.
For this contest, feel free to use one of these flow templates (Push-Relabel Dinic's Alternative Dinic's implementaiton) if you do not have your own.
For some of the problems it will be useful to understand how to set up the "Project Selection" problem as min cut problem. Here are some notes on it.
Lecture: Video
Lecture Notes: Basic Algorithms Advanced Algorithms Min-Cost-Flows
Contest Link: Here
Solutions: For Editing For Viewing
This weeks contest features string algorithms. You will find problems for which Karp-Rabin, KMP, and Suffix Arrays are useful. Other problems are ad-hoc and will feature more general ideas like DP, or binary search.
For the lecture, I'll explain how to solve the following problem: Given a string s of length n, find the longest prefix of s which is also a suffix of s. This can be done with the KMP algorithm in O(n) time, with Karp-Rabin fingerprinting in O(n) time (with high probability).
If there is time I will also discuss an elegant solution to this problem: Isomorphic Strings
The KMP Algorithm Link
Karp-Rabin Fingerprinting: Basic Tutorial The Oracle Method
The Suffix Array and Longest Common Prefix (LCP) Array Link
The Z Algorithm LinkContest Link: Here
The theme for today's contest is GAMES. I put up a link to a video lecture as well as some wrtten material about games here. Understanding NIMBERS, GAME SUMS, and the MEX RULE is required to solve some of the problems on tonight's contest.
Lecture: Video
Written Materials: Impartial Games (i.e. Nim-like games) Sums of Games and the MEX rule
Contest Link: Here
Solutions: For Editing For Viewing
The problems of this contest are generally focused on preprocessing a tree such that queries about the tree can be efficently answered. Some notes on Range-Min-Queries and Least-Common-Ancestor queries: From 451, From 295
Contest Link: Here
Contest Link: Here
Solutions: For Editing For Viewing
In the lecture we'll discuss the basics of how segment trees work, to, for example support an array that allows assignments and range sums in O(log n) time. We'll also discuss lazyness, which would allow you to support bulk-assignments (assign all elements in a range with indices in a range [i,j] to some constant c) while supporting lookups, and preserving the O(log n) time per operation.
For this contest, feel free to reference and use code from the articles below on segment trees (simpler to reason about, more versatile) or Fenwick trees (easier to implement, better constant factor).
Lecture Notes from 451 Here
CP-Algorithms notes on Seg Trees Here
Contest Link: Here
This week we will learn how to count things! This often involves factorials, binomial coefficients and recurrences. Many contest problems require you to compute the answer modulo a prime. So it's therefore often necessary to compute factorials and binomial coefficients modulo a prime, and there are some tricks to doing that as well.
The pre-class lecture will be about computing factorials and binomial coefficients and a few example problems:
https://cp-algorithms.com/combinatorics/binomial-coefficients.html
https://cp-algorithms.com/combinatorics/starsandbars.html
https://en.wikipedia.org/wiki/Lattice_path
https://cp-algorithms.com/algebra/factorial-modulo.html
https://codeforces.com/contest/57/problem/CContest Link: Here
Solutions: For Editing For Viewing
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. Mastering 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!
For today's lecture about dynamic programming, I plan to go over three cp-algorithms pages: intro to DP, knapsack, LIS. If there is time I will do some example problems from Atcoder DP Tasks.
Contest Link
Solutions: For Editing For Viewing
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 (breadth first search and depth first search), and shortest path algorithms.
Today's lecture explores the following links:
DFS: CP-Algorithms Page Additional Notes A practice problem
BFS: CP-Algorithms Page Additional Notes A Practice Problem
Dijkstra: 451 Lecture NotesContest Link: Here
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. This technique comes up in surprising ways. Today's lecture was based on the content of the CP Algorithms site on binary search, linked below.
CP Algorithms Binary Search Site: cp-algorithms.com/nummethods/binarysearch.html
Contest Link: Here
Solutions: For editing For Viewing
This week has no particular algorithmic theme. Instead, we will go over the basics of competitive programming and do our first contest on Codeforces.com. Please make sure you have a Codeforces account ready to go and understand how to upload your solutions to the problems.
If you don't know how to read from standard input and write to standard output, here's a tutorial showing how to do it.
Contest Link: Here
Solutions: For editing For viewing
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 are allowed to use any code you have written, at any time in the past, for any purpose. However, you should not search for or make use of code written by others to solve the specific assigned problem.
So to summarize, each student should write his or her own code. If you're stuck on a problem, you are welcome to discuss it with another student in the class, or the course staff. But you cannot copy another student's code.
The violations described above are regarded as an academic integrity violation, and -- depending on the severity -- will result in penalties and/or be reported to the appropriate university authorities.
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:
The differences between 15-195 and 15-295 are: Students enrolled in 15-295 will not get credit for problems A and B of the weekly contests, but 15-195 students can. A student can take 15-195 only once, but 15-295 can be taken repeatedly.
Here is how your grade is determined:
score ≥ 25: A
score ≥ 15: B
score ≥ 10: C
score ≥ 5: D
Everyone in the class and/or on any programming team should be in this Discord workspace. This is one way we communicate with the class. Here is the join link.
Everybody in the class is required to have a Codeforces account. We will be running our weekly contests on that judge.
Add your name along with your Codeforces handle name and other information to this spreadsheet. (It's the same one in Basic Information list above.)
To join the 15-295 codeforces group, first create your codeforces account, and login to it. Then go to this 15-295 Codeforces Group page. On this page you should see a list of the contests created for this course. Now, 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 this NOT SET UP YET document.
This semester Richard Peng is teaching 15495, Topics in Algorithmic Problem Solving. It's Tuesday and Thursday 2 to 3:20PM in Porter Hall 126A. Many techniques that are useful for contest solving will be covered.
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:
If you are a beginner looking for resources to learn the various topics that appear in typical contests, some good sources are:
We must treat every individual with respect. We are diverse in many ways, and this diversity is fundamental to building and maintaining an equitable and inclusive campus community. Diversity can refer to multiple ways that we identify ourselves, including but not limited to race, color, national origin, language, sex, disability, age, sexual orientation, gender identity, religion, creed, ancestry, belief, veteran status, or genetic information. Each of these diverse identities, along with many others not mentioned here, shape the perspectives our students, faculty, and staff bring to our campus. We, at CMU, will work to promote diversity, equity and inclusion not only because diversity fuels excellence and innovation, but because we want to pursue justice. We acknowledge our imperfections while we also fully commit to the work, inside and outside of our classrooms, of building and sustaining a campus community that increasingly embraces these core values.
Each of us is responsible for creating a safer, more inclusive environment.
Unfortunately, incidents of bias or discrimination do occur, whether intentional or unintentional. They contribute to creating an unwelcoming environment for individuals and groups at the university. Therefore, the university encourages anyone who experiences or observes unfair or hostile treatment on the basis of identity to speak out for justice and support, within the moment of the incident or after the incident has passed. Anyone can share these experiences using the following resources:
- Center for Student Diversity and Inclusion: <csdi@andrew.cmu.edu>, (412) 268-2150
- Report-It online anonymous reporting platform: reportit.net username: tartans password: plaid
All reports will be documented and deliberated to determine if there should be any following actions. Regardless of incident type, the university will use all shared experiences to transform our campus climate to be more equitable and just.