Skip to content

Latest commit

 

History

History
64 lines (56 loc) · 20.4 KB

README.md

File metadata and controls

64 lines (56 loc) · 20.4 KB

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