Practical Course: Advanced Algorithms in Competitive Programming Problems
Content
We will examine a selection of interesting problems from competitive programming contests (e.g. ICPC, Advent of Code, Topcoder) focusing on solution techniques and effective implementations of algorithms and data structures commonly appearing in them. Students will attempt to solve the tasks individually, while the model solution will be presented a week later.
It is expected students are familiar with advanced algorithms and data structures, such as:
- BST trees;
- graph algorithms (shortest path, DFS trees, matchings and flows);
- dynamic programming;
- union/find.
Basic experience in a systems programming language (C++, Rust) is required.
Organization
Preliminary meeting: 31.01.2024, 15:00
We covered grading and the task A Journey to Greece from GCPC 2015. You can find it as 100753A at Codeforces.
Here you can access the meeting "slides".
Weekly meetings: Tuesdays, 10:00AM, 02.11.018
Meetings are hosted online (but not recorded) at BBB.
Change of place, 16.04: one time only we're moving to 02.09.014.
Previous Knowledge Expected
- Introduction to Informatics 1 (IN0001)
- Fundamentals of Programming (IN0002)
- Fundamentals of Algorithms and Data Structures (IN0007)
- Efficient Algorithms and Data Structures (IN2003)
- Advanced Algorithms (IN2360)
Objective
After the completion of this course students should:
- know the structure of a competitive programming contest, tasks, and judging platforms;
- be familiar with designing effective algorithmic solutions to competitive programming problems;
- know how to identify the time and memory complexity of an algorithm;
- be able to implement the advanced algorithms and data structures on their own in an efficient systems programming language;
- know how to present a solution and justify its correctness.
Recommended Reading
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022) [1990]. Introduction to Algorithms (4th ed.). MIT Press and McGraw-Hill. ISBN 0-262-04630-X