Algorithms Lab 2021

These are my solutions for the problems posed during the Algorithms Lab of 2021 at ETH Zurich. You will be able to find the problem descriptions with a quick online search.

Marked in bold are the harder problems (in my optinion).

Week	Topic	Problem of the Week	Problem 1	Problem 2	Problem 3	Problem 4
1	partial sums, sliding window		Build the Sum	Dominoes	Even Pairs	Even Matrices
2	dynamic programming	Deck of Cards	Beach Bars	Burning Coins	The Great Game	Defensive Line
3	geometry	From Russia with Love	Hit	First Hit	Antenna	Hiking Maps
4	graphs	Fighting Pits of Mereen	First Steps with BGL	Ant Challenge	Buddy Selection	Important Bridges
5	greedy, split & list	Motorcycles	Boats	Moving Books	Severus Snape	Asterix the Gaul
6	linear programming	Planet Express	What is the Maximum?	Diet	Inball	Lannister
7	flows	Octopussy	Shopping Trip	Knights	Coin Tossing Tournament	London
8	proximity structures	Suez	Bistro	Germs	H1N1	Light the Stage
9	cuts, cost flows	Kingdom Defence	Real Estate Market	Placing Knights	Algocoön Group	Canteen
10		GoldenEye	Worldcup	Asterix in Switzerland	Asterix and the Chariot Race	Evolution
11		The Phantom Menace	Idefix and the Mansions of the Gods	Return of the Jedi	Asterix and the Roman Legions	The Iron Islands
12		San Francisco	On Her Majesty's Secret Service	Hong Kong	Carsharing	Bonus Level
13		Clues	Rubeus Hagrid	Punch	Hand	Ludo Bagman
14		India

Topics

Binary Search

• Asterix the Gaul
• Evolution
• On Her Majesty's Secret Service
• India

Disjoint-Sets

• GoldenEye
• Idefix and the Mansions of the Gods
• Return of the Jedi
• Hand

Partial Sums

• Even Pairs
• Even Matrices

Sliding Window

• Deck of Cards
• Beach Bars
• Hiking Maps
• The Iron Islands

Two Pointers

• Buddy Selection

Dynamic Programming

• Burning Coins
• The Great Game
• Defensive Line
• From Russia with Love
• Fighting Pits of Mereen
• Severus Snape
• The Iron Islands
• San Francisco
• Bonus Level
• Punch

Geometry

Intersections

• Hit
• First Hit

Minimum Enclosing Circle

• Antenna

Triangles

• Hiking Maps

Triangulations

• Bistro
• Germs
• H1N1
• Light the Stage
• GoldenEye
• Worldcup
• Idefix and the Mansions of the Gods
• Hong Kong
• Clues
• Hand

Graphs

Depth-first Search

• Asterix and the Chariot Race
• Evolution
• Rubeus Hagrid

Shortest Paths

• First Steps with BGL
• Ant Challenge
• Planet Express
• On Her Majesty's Secret Service

Minimum Spanning Tree

• First Steps with BGL
• Ant Challenge
• Return of the Jedi

Maximum Cardinality Matching

• Buddy Selection
• Placing Knights
• On Her Majesty's Secret Service

Maximum Independent Set

• Placing Knights

Connected Components

• Planet Express
• Clues

Biconnected Components

• Important Bridges

Bipartite

• Clues

Flows

• Shopping Trip
• Knights
• Coin Tossing Tournament
• London
• Kingdom Defence
• Algocoön Group
• Asterix in Switzerland
• Ludo Bagman
• India

Minimum Cuts

• Algocoön Group
• The Phantom Menace

Cost Flows

• Real Estate Market
• Canteen
• Carsharing
• Ludo Bagman
• India

Greedy

• Motorcycles
• Boats
• Moving Books
• Severus Snape
• Octopussy
• H1N1
• Asterix and the Chariot Race
• Hong Kong
• Rubeus Hagrid

Split & List

• Asterix the Gaul

Linear Programming

• What is the Maximum?
• Diet
• Inball
• Lannister
• Suez
• Worldcup
• Asterix and the Roman Legions