T-414-ÁFLV: A Competitive Programming Course
— Competitive Programming — 8 min read
I held a course about Competitive Programming at Reykjavik University on the fall semester of 2014. It was three-week long with a fresh lecture and problem set each day. There were almost 90 students registered and it turned out to be a big success, although some students complained about heavy workload. For me it was a very rewarding experience.
Below you may find the lecture slides (including LaTeX sources), the problem sets, and other supporting material. All problems are available on the Open Kattis online judge.
Note: The course material is now accessible on GitHub. Contributions are welcome.
Table of contents
- Lecture 1: Introduction
- Lecture 2: Data structures and libraries
- Lecture 3: Data structures
- Lecture 4: Problem solving paradigms
- Lecture 5: Greedy algorithms
- Problem session 1
- Lecture 6: Dynamic programming
- Lecture 7: Mathematics
- Lecture 8: Unweighted graphs
- Lecture 9: Graphs
- Lecture 10: Network flow
- Problem session 2
- Lecture 11: Strings
- Lecture 12: Geometry
- Final exam
Lecture 1: Introduction
Covers some basic things about the course, and then introduces competitive programming.
Material
Problems
Solve some of the following problems on Kattis. You need 5 points to get full score.
- Eight Queens (1 point)
- Toilet Seat (1 point)
- T9 Spelling (1 point)
- Rock-Paper-Scissors Tournament (2 points)
- Chess (2 points)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 2: Data structures and libraries
Reviews the most basic data types and data structures. Covers how to represent big integers, sets and graphs, and how to augment binary search trees.
Material
Problems
Solve some of the following problems on Kattis. You need 5 points to get full score.
- Hay Points (1 point)
- CD (1 point)
- I Can Guess the Data Structure (1 point)
- Phone List (2 points)
- Cookie Selection (2 points)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 3: Data structures
Reviews the Union-Find disjoint sets data structure, and covers range queries and Segment Trees.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Virtual Friends (1 point)
- Counting Subsequences (1 point)
- Kastenlauf (1 point)
- Almost Union-Find (1 point)
- Worst Weather Ever (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 4: Problem solving paradigms
Introduces problem solving paradigms, and covers complete search, backtracking, and divide & conquer. Covers binary search, and binary exponentiation.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Lifting Walls (1 point)
- Natjecanje (1 point)
- Arctic Network (1 point)
- Sylvester Construction (1 point)
- Welcome to Code Jam (Easy) (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 5: Greedy algorithms
Introduces greedy algorithms, and covers coin changing, interval scheduling, and scheduling to minimize lateness.
Material
- Lecture slides: PDF
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Virus Replication (1 point)
- Planting Trees (1 point)
- Watering Grass (1 point)
- Bank Queue (1 point)
- Moving Pianos (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Problem session 1
Teams of up to three students had to solve the following problems. They had three hours, and were only allowed to use a single computer.
Lecture 6: Dynamic programming
Introduces dynamic programming and goes over some examples.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Exact Change (1 point)
- Radio Commercials (1 point)
- Pebble Solitaire (1 point)
- Spiderman’s workout (1 point)
- Restaurant Orders (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 7: Mathematics
Covers some basic topics in mathematics, including number theory, combinatorics and game theory.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Ones (1 point)
- Sierpinski circumference (1 point)
- Bachet’s Game (1 point)
- Falling Mugs (1 point)
- Snapper Chain (Hard) (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 8: Unweighted graphs
Reviews basic graph theory. Covers depth-first search, breadth-first search, and applications.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Coast Length (1 point)
- Reactivity Series (1 point)
- Flip Five (1 point)
- Dominos (1 point)
- Dominoes 2 (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 9: Graphs
Covers minimum spanning trees, shortest paths, some graph theory, and some special types of graphs.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Freckles (1 point)
- Breaking Bad (1 point)
- Get Shorty (1 point)
- Fire Station (1 point)
- Shopping Malls (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 10: Network flow
Covers maximum flow, minimum cut, bipartite matching, and other applications.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Gopher II (1 point)
- Paintball (1 point)
- Maximum Flow (1 point)
- Minimum Cut (1 point)
- Minimum Cost Maximum Flow (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Problem session 2
Teams of up to three students had to solve the following problems. They had three hours, and were only allowed to use a single computer.
Lecture 11: Strings
Covers string matching, KMP, tries, suffix arrays, and applications.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Kemija (1 point)
- Peragrams (1 point)
- Power Strings (1 point)
- Clock Pictures (1 point)
- Dvaput (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 12: Geometry
Covers basic geometry, convex hulls, area of polygons, point in polygon, and closest pair of points.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Logo (1 point)
- Jabuke (1 point)
- Wrapping (1 point)
- Pesky Mosquitoes (1 point)
- White Water Rafting (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Final exam
At the end of the course there was a four-hour individual final exam. It was as follows.
Part 1 (30%)
Solve one of the following problems.
Part 2 (20%)
Solve one of the following problems.
Part 3 (20%)
Solve one of the following problems.
Part 4 (20%)
Solve one of the following problems.
Part 5 (20%)
Solve one of the following problems.
Part 6 (20%) (Bonus)
Solve one of the following problems.