This repo contains my solutions for the weekly exercise problems given in the course Algorithms Lab at ETH ZÅ«rich, which I attended during Autumn Semester 2021. The repo also contains @tarqluca's solutions.
In this course students learn how to solve algorithmic problems given by a textual, story-like description. We assume knowledge of elementary algorithms and data structures as they are typically taught on the Bachelor level. In tutorials we introduce more advanced algorithms and the usage of some standard libraries for combinatorial algorithms. Students practice their skills by solving weekly exercises. For that they have to understand the problem setting, find an appropriate modeling, choose suitable algorithms, and implement them using C/C++, BGL, and CGAL. The evaluation of the correctness and efficiency of their solutions will be performed by an online-judge which compiles the submitted source-code and runs it on a set of test instances.
In this section, problems are gouped by corresponding exam. The following list is by no means complete, but could be helpful if you're looking for a general glance on the topics examined.
| Theme | Problem | Topics |
|---|---|---|
| Harry Potter | Severus Snape | dynamic programming |
| Dean Thomas | triangulation | |
| Ludo Bagman | min cost max flow | |
| Hagrid | DFS, greedy | |
| Game of Thrones | Fighting Pits of Meereen | dynamic programming |
| Lannister | linear programming | |
| Hand | clustering with triangulation, union-find | |
| The Iron Islands | sliding window, partial sums, maps | |
| Sherlock Holmes | The Great Game | dynamic programming |
| Surveillance Photographs | flow | |
| Lestrade | triangulation, LP | |
| Clues | triangulation, union-find, graph coloring | |
| Around the World in Eighty Days |
India | maximum flow, binary search |
| Hong Kong | triangulation | |
| San Francisco | DP | |
| London | maximum flow, characters tricks | |
| Suez | linear programming | |
| The Adventures of Astérix | Asterix the Gaul | greedy, binary search, split&list |
| Asterix in Switzerland | maximum flow | |
| Asterix and the Roman Legions | LP | |
| Asterix and the Chariot Race | DFS | |
| Idefix | triangulation, union-find | |
| Star Wars |
Phantom Menace | minimum cut (flows) |
| Return of the Jedi | graph problem, union-find | |
| James Bond | From Russia with Love | dynamic programming |
| Octopussy | greedy, binary trees | |
| Casino Royale | max flow min cost | |
| Golden Eye | triangulation | |
| On Her Majesty's Secret Service | shortest paths, binary search, capacity scheduling |