This repo contains my solutions to the problems from the Algorithms Lab course at ETH Zurich from the FS24 semester.
For each problem, you'll find:
- 🧠 Problem Description: Clear explanation and summary of the problem statement.
- 💡 Hints: Multiple hints that guide you step-by-step. Each hint reveals progressively more information, designed to help you come up with the solution yourself.
- 🔄 (Intermediate Solutions): Intermediate solutions that pass only some test sets, showing the evolution and the thought process of coming up with the final solution.
- ✅ Solutions: A solution that passes all test sets with comprehensive explanation of the approach, and detailed code comments.
All hints and solutions are collapsed in toggles by default to prevent spoilers. You can expand them to view the content. Initially, only the problem description is visible.
In addition to the problems there are also some general tips and algorithm specific tips that can help you approach the problems more effectively.
Many of these tips might seem obvious or trivial, but having an overview of all of them can help you remember them when you're stuck on a problem.
-
Think before coding: Take some time before starting to code. I would recommend to only start coding once you have an idea that you believe should work. Nothing is more annoying than coding up a solution and have it fail on you. If you dive right in, it makes it harder to distinugish between a coding error and a conceptual error.
-
Solve examples: Start out by first solving the example inputs given in the problem statement by hand. This gives you a better understanding of the problem and can help you find patterns or edge cases that need to be handled.
-
Take input constraints into account: The size of the input already tells you what complexity you should aim for. This can greatly reduce the amount of algorithms you need to consider.
-
Go test-set-by-test-set: Often it is helpful to first consider the first test set. This will often be much easier than the entire problem and lead you on the right track. This is not always the case, but it is a good heuristic.
Boost Graph Library (BGL)
- Boost can be very rough at first. Don't feel bad if you need to look at the solution for the actual code. Finding the correct algorithm/approach will be more important in the long run.
Computational Geometry Algorithms Library (CGAL)
Sliding Window
- Whenever you need to maximize a contiguous segment you probably need to use a sliding window.
Dynamic Programming
- Begin by trying to formulate the recurrence relation. If you don't have it, there is no point in coding.
Split & List
Greedy
- If you want to try a greedy approach you will probably need to sort (part of) your input first to then choose greedily.
Geometry
Delaunay Triangulation
- As soon as the problem asks for some notion of distance or proximity, you will probably need to usea Delaunay Triangulation, as it is just super cheap to do.
- You often will want to store information at each vertex in the Delaunay Triangulation. Most elementary one would be its index to reference later. For this you can use the following setup (see code example provided in AlgoLab docs for more details).
typedef std::size_t Index;
typedef CGAL::Triangulation_vertex_base_with_info_2<Index,K> Vb;
typedef CGAL::Triangulation_face_base_2<K> Fb;
typedef CGAL::Triangulation_data_structure_2<Vb,Fb> Tds;
typedef CGAL::Delaunay_triangulation_2<K,Tds> Delaunay;
typedef std::tuple<Index,Index,K::FT> Edge;
typedef K::Point_2 Point;
typedef std::pair<Point,Index> IPoint;
...
Index idx = vertex->info();Linear Programming
-
If the problem asks you to "round to the nearest integer", it is probably a linear programming problem. This is a very ad-hoc tip, but you would be surprised how often this is the case.
-
CGAL creates all intermediate variables, e.g. if you create variable 1000 but the previous highest you had was 100, all 900 variables in between are also created, greaetly impacting run time.
Graphs
Max Flow/Min Cut
Max Flow Min Cost
- In Max Flow Min Cut problems the intuitive way of modeling it often involves negative costs. This then works for the first few test sets, but for the last one you need to rescale it to be non-negative to use the faster,
- This repo is intended as a study and reference resource. If you're currently taking the course, I recommend attempting the problems yourself before looking at the solutions.
- Feel free to open issues or pull requests if you spot any errors or have suggestions.
All explanations and writeups are based on personal notes I took throughout the semester while working on each problem. These notes were later revised using Gemma 3 27B Instruct and Gemini 2.5 Pro, and then revised one more time by me. This cycle was done twice to ensure that the solutions and hints are accurate and (hopefully) helpful. The script that was used for the LLM revision can be found in the src directory.