Algorithms Lab

This repo contains my solutions to the algorithms lab of ETH Zürich. The lab consists of problems every week that must be solved via an algorithm.

The primary language to solve the challenges is C++. I strive as much as possible to document my code and my algorithms. The description of the problems may be wonky, so I suggest that you give the associated PDF a read for a detailed explanation of the problem.

Overview

Week	Problem	Score	Solution
1	Even Pairs	100	Partial Sums
1	Build The Sum	100	Common Sense
1	Dominoes	100	Sliding over the dominoes
1	Even Matrices	70	Precomputation
PotW 1	Deck of Cards	100	Precomputation + sliding window
2	Burning Coins	100	Dynamic Programming
2	Beach Bars	100	Sliding Windowm & DP
2	The Great Game	100	Bottom Up Dynamic Programming
2	Search Snippets	75	Sliding Windowm
PotW 2	Magician and the Coin	100	Dynamic Programming & Memoization
3	Hit	100	CGAL intersection testing
3	First Hit	99	CGAL intersection testing
3	Antenna	100	CGAL Min Circle
3	Almost Antenna	100	CGAL Min Circle and Support Points
PotW 3	Defensive Line	100	Dynamic Programming
4	First Steps with BGL	100	MST and Dijkstra Shortest Paths
4	Ant Challenge	100	MST and Dijkstra Shortest Paths
4	Important Bridges	100	Biconnected Components
4	Buddy Selection	100	Set Intersection & Group Matching
4	Shortest Paths	100	Dijkstra
PotW 4	Hiking Maps	100	CGAL Predicate Testing & Sliding Window
5	Boats	100	Greedy Algorithm
5	Attack of the Clones	0	-
5	Light at the Museum	100	Split & List
5	Punch	0	-
5	High School Teams	0	-
PotW 5	Planet Express	100	Shortest Paths & Vertex Aggregation
6	Coin Tossing	100	Flow Computation
6	Shopping Trip	100	Flow Computation
6	Kingdom Defence	100	Flow Computation with min/max per edge
6	Tetris	100	Flow Computation & Vertex splitting
Potw 6	Octopussy	100	Greedy Algorithm
7	Maximum	100	CGAL LP/QP
7	Diet	100	QP
7	Portfolios	100	QP
7	Inball	100	CGAL LP - have to set up right LP
PotW 7	London	100	Flow Computation & Vertex Aggregation
8	Graypes	100	Delaunay Triangulation
8	Bistro	100	Delaunay Triangulagion
8	H1N1	80	Delaunay Triangulation + DFS
8	Germs	100	Delaunay triangulation
PotW 8	Suez	100	LP
8	Satellites	100	Min Vertex Cover
8	Algocoon	100	MinFlow-MaxCut
8	Real Estate Market	100	MaxCost-MaxFlow (using MinCostMaxFlow)
8	Canteen	100	MaxCost-MaxFlow
8	Marathon	20	MinCost-MaxFlow with precomp and binary search
PotW 9	GoldenEye	100	CGAL Proximity Structure (Vornoi)
9	New Tiles	0	DP with bitmatching (not implemented)
9	On Her Majesty’s Secret Service	100	Minimum bottleneck matching (minimizing edge weight
9	Light the Stage	100	CGAL Proximity Checking
9	Evolution	30	Naive path walk
9	Return of the Jedi	0	-
9	Poker Chips	0	DP with bitmatching
PotW 10	India
10	The Empire Strikes Back	100	LP + Delaunay triangulation precomputation
10	Planks	60	Basically bruteforcing (Correct is to use Split & List
10	Carsharing	100	MinCostMaxFlow
10	San Fransisco
PotW 11	New York
11	Light Pattern
11	Casino Royale	100	MinCostMaxFlow (same idea as carsharing)
11	Radiation
11	Hong Kong
PotW 12	World Cup
12	Bob’s Burden
12	Corbusier
12	Cantonal Courier
12	Clues	60	2-color BFS + Delaunay
12	Moving Blocks	100	Greedy + multiset
PotW 13	Fleetrace

Compilation and Running

STL/BGL Files

To compile the cpp files:

g++ -Wall -O3 filename.cpp -o filename.o

To run the file with a given input and redirect output to a file

./filename.o < testsets/test{i}.in > test{i}.out

To compare with the expected output, use `diff`

diff test{i}.out testsets/test{i}.out

Alternatively, you can do the previous in one line

diff <(./filename.o < testsets/test{i}.in) testsets/test{i}.out

CGAL

Compiling CGAL files is slightly different, it makes use of the cgal_create_cmake_script. In order to avoid to seperate the source code from compiled files, take advantage of an additional build folder. Compile as follows:

cgal_create_cmake_script
mkdir build && cd build
cmake ..
make

To run, the procedure is the same as for STL/BGL files.