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

Problem	Solution	Week	Type
Build the Sum	build_the_sum.cpp	Week 1	---
Dominoes	dominoes.cpp	Week 1	---
Even pairs	even_pairs.cpp	Week 1	Combinatorics
Even Matrices	even_matrices.cpp	Week 1	Combinatorics
Deck of Cards	deck_of_cards.cpp	POTW 2	SW
Burning Coins	burning_coins.cpp	Week 2	DP
Beach Bars	beach_bars.cpp	Week 2	SW
The Great Game	the_great_game.cpp	Week 2	Minimax + DP
Lord Voldemort	lord_voldemort.cpp	Week 2	DP + Precompute
JamesBondSovereigns	james_bond_sovereigns.cpp	POTW 3	DP
FirstStepsBGL	first_steps_bgl.cpp	Week 3	Dijkstra + MST
BuddySelection	buddy_selection.cpp	Week 3	Maximum Matching
ImportantBridges	important_bridges.cpp	Week 3	Biconnected Components
AntChallenge	ant_challenge.cpp	Week 3	Dijkstra + Prim MST
IronIslands	iron_islands.cpp	POTW 4	SW
Hit	hit.cpp	Week 4	CGAL geometry
FirstHit	first_hit.cpp	Week 4	"Smarter" Hit
Antenna	antenna.cpp	Week 4	Min Circle
HikingMaps	hiking_maps.cpp	Week 4	Orientations
PlanetExpress	planet_express.cpp	POTW 5	SCC + Dijkstra
MovingBooks	moving_books.cpp	Week 5	Greedy
AsterixTheGaul	asterix_the_gaul.cpp	Week 5	Split&List + BS
SeverusSnape	severus_snape.cpp	Week 5	Greedy + DP
Boats	boats.cpp	Week 5	Greedy
Motorcycles	motorcycles.cpp	POTW 6	CGAL geometry
Tiles	tiles.cpp	Week 6	MaxFlow
London	london.cpp	Week 6	MaxFlow
CoinTossingTournament	coin_tossing_tournament.cpp	Week 6	MaxFlow
Knights	knights.cpp	Week 6	MaxFlow
Octopussy	octopussy.cpp	POTW 7	Greedy + DFS
Bistro	bistro.cpp	Week 7	Delaunay
Germs	germs.cpp	Week 7	Delaunay
H1N1	h1n1.cpp	Week 7	Delaunay + PrioQueue
GoldenEye	goldeneye.cpp	Week 7	Delaunay + UF (EMST-like)
KingdomDefence	kingdom_defence.cpp	POTW 8	Supply/Demand MaxFlow
WhatIsTheMaximum	what_is_the_maximum.cpp	Week 8	CGAL LP
Suez	suez.cpp	Week 8	CGAL LP
Inball	inball.cpp	Week 8	CGAL LP + LinAlg
Diet	diet.cpp	Week 8	CGAL LP
Idefix	idefix.cpp	POTW 9	Delaunay + UF + BS
Canteen	canteen.cpp	Week 9	MinCostMaxFlow
PlacingKnights	placing_knights.cpp	Week 9	Bipartite MaxIS
RealEstateMarket	real_estate_market.cpp	Week 9	MinCostMaxFlow
Algocoon	algocoon.cpp	Week 9	MinCut
Lannister	lannister.cpp	POTW 10	CGAL LP
SanFrancisco	san_francisco.cpp	Week 10	DP
RubeusHagrid	rubeus_hagrid.cpp	Week 10	Greedily Sorted DFS
SurveillancePhotograph	surveillance_photograph.cpp	Week 10	MaxFlow
Clues	clues.cpp	Week 10	CC + Bipartite
India	india.cpp	POTW 11	MinCostMaxFlow + BS
AsterixChariotRace	asterix_chariot_race.cpp	Week 11	DP
DeanThomas	dean_thomas.cpp	Week 11	Delaunay + PrioQueue
Legions	legions.cpp	Week 11	CGAL LP + LinAlg
PhantomMenace	phantom_menace.cpp	Week 11	MinimumCut
PiedPiper	pied_piper.cpp	POTW 12	DP
NewYork	new_york.cpp	Week 12	SW + PrioQ
ReturnOfTheJedi	return_of_the_jedi.cpp	Week 12	2nd-best MST
Rumpelstitskin	rumpelstitskin.cpp	Week 12	Max Weighted Matching
WorldCup	world_cup.cpp	Week 12	CGAL LP + Delaunay
Schneewittchen	schneewittchen.cpp	POTW 13	CGAL LP + DFS
AugeanStables	augean_stables.cpp	Week 13	BS + LP (85/100)
CasinoRoyale	casino_royale.cpp	Week 13	MinCostMaxFlow
DHL	dhl.cpp	Week 13	DP
FightingPitsOfMeeren	fighting_pits_of_meeren.cpp	Week 13
OnHerMajestySecretService	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

Problem	Solution	Type
Croquet	croquet.cpp	Delaunay + Dijkstra
QueenOfHearts	queen_of_hearts.cpp	Dijkstra + MinimumCut
DownTheRabbitHole	down_the_rabbit_hole.cpp	RubeusHagrid Clone

Part 2

Problem	Solution	Type
RabbitClan	rabbit_clan.cpp	DP
MadTeaParty	mad_tea_party.cpp	Bipartite MaxIS
Chronosphere	chronosphere.cpp	Legions Clone

Previous Years

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

2022

Problem	Solution	Type
AsterixInSwitzerland	asterix_in_switzerland.cpp	MaxFlow
CarSharing	car_sharing.cpp	MinCostMaxFlow
CeryneianHind	ceryneian_hind.cpp
EmpireStrikesBack	empire_strikes_back.cpp	CGAL LP + Delaunay
Evolution	evolution.cpp	BS
FleetRace	fleet_race.cpp	MinCostMaxFlow
LightTheStage	light_the_stage.cpp	BS + Delaunay
LudoBagman	ludo_bagman.cpp	MinCostMaxFlow
Marathon	marathon.cpp	MultiPath Dijkstra + MF
NewTiles	new_tiles.cpp
RevengeOfTheSith	revenge_of_the_sith.cpp	BS(really cool) + UF
SearchSnippets	search_snippets.cpp
ShoppingTrip	shopping_trip.cpp
TheHandTourney	the_hand_tourney.cpp	BS + UF (hardcoded ifs)
TheNemeanLion	the_nemean_lion.cpp
Tracking	tracking.cpp	Dijkstra