- Introduction
- What is this course about?
- How is it erogated?
- Outline
- My Perspective
- What Will You Find in This Repo?
- Solutions per Week
- Solutions per Topic
- General Advices
- My Notes
- How to Compile or Run
- Disclaimer on Problem Statements
- Credits
- License
This repository contains my personal solutions and explanations for the Algorithms Lab (Algolab 2024). The course is taught in a style similar to the International Olympiad in Informatics (IOI), focusing on solving algorithmic problems from textual and story-like descriptions.
The main objective of the course is to learn how to solve algorithmic problems that require:
- Dynamic Programming (DP)
- Greedy Algorithms
- Basic Graph Algorithms (MST, Shortest Path, Matching, etc.)
- Flow Graph Algorithms (MaxFlow, MinCut, MinCostMaxFlow, etc.)
- Geometry (Delaunay triangulations, advanced computational geometry)
- Linear Programming (LP)
- and more!
Over time, the level of difficulty ramps up—toward the end, you must determine which strategy (Greedy, DP, LP, MaxFlow, etc.) is most efficient.
-
Weekly Format:
Each week, there are 4 problems closely related to the topic introduced that week. Additionally, there is a Problem of the Week (POW) that simulates exam conditions (limited time, hidden tests, etc.). -
From Week 10:
The final four weeks present more challenging problems where it’s not just about coding a known algorithm but also figuring out which approach is correct.
This course was very fun and interesting, and it boosted my problem-solving skills significantly. It also helped me improve coding-interview skills.
However, if you do not have a competitive programming background (as in my case), be prepared to work very hard. I personally put in about three times the usual effort for an 8-ECTS course.
Of course, this can vary from person to person, but I believe doing all the exercises and understanding deeply the solutions should be enough for passing the exam, regardless of the background you come from.
- Solutions per Week: Organized by weekly assignments, including the POW.
- Solutions per Topic: Organized by theme (DP, MST, Flow, etc.).
- General Advices: Tips for tackling problems and structuring your code.
- My Notes: Personal takes on topics like DP, geometry, network flow, etc.
For each problem, there is:
solution.cpp: The fully working code always scoring 100/100 points.explanation.md: A verbose explanation of my reasoning and approach.
Legend:
DP = Dynamic Programming | SW = Sliding Window | SP = Shortest Paths | MST = Minimum Spanning Tree | MM = Maximum Matching | SCC = Strongly Connected Components | GC = Computational Geometry |
GREEDY = Greedy Algorithms | S. & L. = Split and List | GREEDP = Greedy + DP | MF = Maximum Flow | MCMF = Min Cost Max Flow | LP = Linear Programming | UF = Union-Find | TRI = Triangulation | SW+ = Sliding Window + More | MC = Min-Cut
-
Keep a Standard Template
#include <bits/stdc++.h> using namespace std; // Additional typedefs, CGAL/BGL libraries, etc. void solve() { // The function containing the main logic of your solution } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while(t--) solve(); return 0; }
This lets you minimize repetitive code.
-
Practice with POWs
Each weekly POW is a great way to simulate the exam. Work on your time management and get comfortable with partial points. -
Get Familiar with BGL and CGAL
They may look intimidating initially, but you have code snippets and the full documentation available at the exam. Make sure you know how to read official docs for extra features not covered in the snippets. -
Partial Points
Don’t be afraid to go for partial solutions. Some test sets are easier and can give you a good chunk of points even if you don’t have the complete solution. -
Explore Additional Repositories
If you finish early, there are many repos of previous years containing extra practice problems (however due to the high volume of the exercises it's likely you will not have the time to do them).
- Introduction
- Dynamic Programming
- Greedy Algorithms
- Split and List
- Computational Geometry
- Proximity Structures
- Linear Programming
- Graph Theory
- Network Flow
- Advanced Flow
All solutions in this repository use C++ (usually C++17 or above). You can compile with any modern C++ compiler:
# Example: compile and run Dominoes problem from Week 1
cd src/week01/dominoes
g++ -std=c++17 solution.cpp -o dominoes
./dominoes < input.txtMake sure you have installed BGL and CGAL correctly installed on your system.
We are not allowed to share the official problem statements for each exercise. Therefore, the texts are not included in this repository. The solutions here refer to those statements, but I often included a quick summary or personal interpretation. If you want to solve these problems independently, please see the official course materials or other official references.
Algolab is a challenging course without always providing official solutions. The following repositories (and their authors) helped me a lot to come up with these solutions:
A huge thanks to them for sharing their work!
This project is licensed under the MIT License — see the LICENSE file for details.
Enjoy this fun course and Good Luck!
Whatever your starting point, you can do it.
-- Prof. John Ousterhout, Stanford University