Algorithms Lab - Fall 2023

Code Expert exercises from the Algorithms Lab course at ETH Zürich.

Setup

A modified version of the algolabVS.sh script is used for my specific setup, hence no portability is guaranteed. The script is meant to be used as specified by its documentation.

Problem Set

Solution	Week	Type
build_the_sum.cpp	Week 1	---
dominoes.cpp	Week 1	---
even_pairs.cpp	Week 1	Combinatorics
even_matrices.cpp	Week 1	Combinatorics
deck_of_cards.cpp	POTW 2	SW
burning_coins.cpp	Week 2	DP
beach_bars.cpp	Week 2	SW
the_great_game.cpp	Week 2	Minimax + DP
lord_voldemort.cpp	Week 2	DP + Precompute
james_bond_sovereigns.cpp	POTW 3	DP
first_steps_bgl.cpp	Week 3	Dijkstra + MST
buddy_selection.cpp	Week 3	Maximum Matching
important_bridges.cpp	Week 3	Biconnected Components
ant_challenge.cpp	Week 3	Dijkstra + Prim MST
iron_islands.cpp	POTW 4	SW
hit.cpp	Week 4	CGAL geometry
first_hit.cpp	Week 4	"Smarter" Hit
antenna.cpp	Week 4	Min Circle
hiking_maps.cpp	Week 4	Orientations
planet_express.cpp	POTW 5	SCC + Dijkstra
moving_books.cpp	Week 5	Greedy
asterix_the_gaul.cpp	Week 5	Split&List + BS
severus_snape.cpp	Week 5	Greedy + DP
boats.cpp	Week 5	Greedy
motorcycles.cpp	POTW 6	CGAL geometry
tiles.cpp	Week 6	MaxFlow
london.cpp	Week 6	MaxFlow
coin_tossing_tournament.cpp	Week 6	MaxFlow
knights.cpp	Week 6	MaxFlow
octopussy.cpp	POTW 7	Greedy + DFS
bistro.cpp	Week 7	Delaunay
germs.cpp	Week 7	Delaunay
h1n1.cpp	Week 7	Delaunay + PrioQueue
goldeneye.cpp	Week 7	Delaunay + UF (EMST-like)
kingdom_defence.cpp	POTW 8	Supply/Demand MaxFlow
what_is_the_maximum.cpp	Week 8	CGAL LP
suez.cpp	Week 8	CGAL LP
inball.cpp	Week 8	CGAL LP + LinAlg
diet.cpp	Week 8	CGAL LP
idefix.cpp	POTW 9	Delaunay + UF + BS
canteen.cpp	Week 9	MinCostMaxFlow
placing_knights.cpp	Week 9	Bipartite MaxIS
real_estate_market.cpp	Week 9	MinCostMaxFlow
algocoon.cpp	Week 9	MinCut
lannister.cpp	POTW 10	CGAL LP
san_francisco.cpp	Week 10	DP
rubeus_hagrid.cpp	Week 10	Greedily Sorted DFS
surveillance_photograph.cpp	Week 10	MaxFlow
clues.cpp	Week 10	CC + Bipartite
india.cpp	POTW 11	MinCostMaxFlow + BS
asterix_chariot_race.cpp	Week 11	DP
dean_thomas.cpp	Week 11	Delaunay + PrioQueue
legions.cpp	Week 11	CGAL LP + LinAlg
phantom_menace.cpp	Week 11	MinimumCut
pied_piper.cpp	POTW 12	DP
new_york.cpp	Week 12	SW + PrioQ
return_of_the_jedi.cpp	Week 12	2nd-best MST
rumpelstitskin.cpp	Week 12	Max Weighted Matching
world_cup.cpp	Week 12	CGAL LP + Delaunay
schneewittchen.cpp	POTW 13	CGAL LP + DFS
augean_stables.cpp	Week 13	BS + LP (85/100)
casino_royale.cpp	Week 13	MinCostMaxFlow
dhl.cpp	Week 13	DP
fighting_pits_of_meeren.cpp	Week 13
on_her_majesty_secret_service.cpp	POTW 14	Dijkstra + BS + MaxFlow

Exam

These are my solutions for the exam problems. Since from the exam paper I was only able to retrieve the sample tests, there is no correctness guarantee on these rewrites. The original versions scored full points, save for Croquet for which I can only guarantee a 75/100 score.

Overall, the exam was much simpler than the general course content, and on top of the guaranteed repeat problems, MadTeaParty was also a near clone of PlacingKnights. The most challenging problem was by far Croquet, although it was possible to pick up a lot of points through individual cases.

Part 1

Solution	Type
croquet.cpp	Delaunay + Dijkstra
queen_of_hearts.cpp	Dijkstra + MinimumCut
down_the_rabbit_hole.cpp	RubeusHagrid Clone

Part 2

Solution	Type
rabbit_clan.cpp	DP
mad_tea_party.cpp	Bipartite MaxIS
chronosphere.cpp	Legions Clone

Previous Years

This is a collection of problems for the previous years I used to prepare for the exam.

2022

Solution	Type
asterix_in_switzerland.cpp	MaxFlow
car_sharing.cpp	MinCostMaxFlow
empire_strikes_back.cpp	CGAL LP + Delaunay
evolution.cpp	BS
fleet_race.cpp	MinCostMaxFlow
light_the_stage.cpp	BS + Delaunay
ludo_bagman.cpp	MinCostMaxFlow
marathon.cpp	MultiPath Dijkstra + MF
revenge_of_the_sith.cpp	BS(really cool) + UF
the_hand_tourney.cpp	BS + UF (hardcoded ifs)
tracking.cpp	Dijkstra