README.md

Algolab 2021

My code for the problems given in the ETH course Algorithms Lab in Fall 2021. Problems descriptions and testcases not included. I did not put as much effort into this as this guy did, but I took some inspiration :) Also credits to the creators of the algolabVS.sh with which this stuff was done (+ Code Expert).

Code requires C++, CGAL, BGL. See https://cadmo.ethz.ch/education/lectures/HS21/algolab/technical.html.

E.g. on Ubuntu, run

sudo apt-get install build-essential libboost-all-dev libcgal-dev cmake cmake-data

Problems sorted by weeks

Week	Problem of the Week	1st problem	2nd problem	3rd problem	4th problem
1	-	Build the sum	Dominoes	Even Pairs	Even Matrices
2	Deck of Cards	Beach Bars	Burning Coins	The Great Game	Defensive Line
3	From Russia with Love	First Hit	Hit	Antenna	Hiking Maps
4	Fighting Pits of Meereen	First steps with BGL	Important Bridges	Buddy Selection	Ant Challenge
5	Motorcycles	Boats	Moving Books	Severus Snape	Asterix and the Gaul
6	Planet Express	Maximize it	Inball	Diet	Lannister
7	Octopussy	Shopping Trip	Knights	Coin Tossing	London
8	Suez	Bistro	Germs	H1N1	Light the Stage
9	Kingdom Defence	Real Estate Market	Placing Knights	Algocoon Group	Canteen
10	GoldenEye	Asterix and the Chariot Race	World Cup	Asterix in Switzerland	Evolution
11	Phantom Menace	The Iron Islands	Return of the Jedi	Idefix	Asterix and the Legions
12	San Francisco	Majesty's service	Hong Kong	Carsharing	Bonus Level
13	Clues	Hagrid	Punch	Hand	Ludo Bagman
14	India

!! SPOILERS AHEAD

(not completed yet)

Categorizing solutions, techniques, properties and algorithms

Properties, Technique, Data Structure, Algorithm	Problems
BFS
(Bi)connected Components	Clues, Hand
Binary Search	H1N1, Light the Stage, Idefix, GoldenEye, India, Majesty's service, The Iron Islands
CGAL Geometry	Hong Kong
CGAL::Gmpq/Gmpz, K::FT (Arbitrary Precision Types)	Hong Kong
DFS	Asterix and the Chariot Race, Return of the Jedi
Delaunay Triangulation	Idefix, GoldenEye, H1N1, Light the Stage, Clues, Hong Kong, Hand
Dijkstra	Hong Kong, H1N1, Majesty's service
Dynamic Programming	Beach Bars, Burning Coins , The Great Game, Defensive Line, Fighting Pits of Meereen, Severus Snape, San Francisco, Punch, From Russia with Love
Graph Duplication	Carsharing
Greedy	Severus Snape, Hagrid
Kruskal	Idefix, GoldenEye, Return of the Jedi, Hand
Linear Programming	Suez, Inball, Asterix and the Legions
Max-Flow-Min-Cost	Bonus Level, Carsharing, India, Ludo Bagman
Maximum Flow	Majesty's service
Maximum Matching	Majesty's service
Minimum Spanning Tree	Clues, Return of the Jedi, Hong Kong, Idefix, GoldenEye, H1N1, Hand
Prefix Sum	Even Pairs, Even Matrices, The Iron Islands, Deck of Cards
Randomization
Recursion	Asterix and the Chariot Race, Hagrid
Sliding Window	The Iron Islands, Deck of Cards
Sorting	The Iron Islands
Split and List	Asterix and the Gaul
Tree	Asterix and the Chariot Race, Hagrid
Union-Find	Idefix, GoldenEye, Hand