# Algorithms Lab

## Overview

### Structure

In this course you will code a lot of programs to solve different tasks.

You will be given 3-4 problems a week and you'll have to write programs in C++ which solve those problems. Your program is to be sent to a judge (a machine which compiles and runs your program) where it will be tested against a huge collection of testdata and you will get (very little) feedback whether your program was good. Basically you will get one of {yes, no, too slow, did not compile}.

The course is structured in 3 big parts.

• STL part - those problems should be solvable without any of the latter two libraries and you should basically implement algorithms from scratch.
• BGL part - BGL is a graph library with functions like finding a maximum matching in a graph or finding the shortest path from vertex A to vertex B.
• CGAL part - CGAL is a geometric library with functions like triangulate a set of points or calculate the intersection of two objects.

### Exercises

Those can take up a lot of time. Basically the lecture is only a collection of hints for how to solve the exercises with a few pieces of knowledge added here or there (like a short introduction to BGL or how to use valgrind to see where your program spends most of its time).

There are exercise sessions where you will get a lot of help on debugging your program or receiving small hints pushing you towards a good algorithm.

The exercises are creatively formulated descriptions of well-known problems (ranging from how many burgers Homer Simpson can eat over how to safely land an airplane to how to sweep the corridors of the unseen university in Ankh-Morpork). For example you will have to solve the [n queens puzzle] and output a valid positioning of n queens for the input n.

### Exam

The exam is exactly like the exercises. You will be given 6 problems and you have 12 hours to come up with 6 solutions. The exam will be split in two parts, so there are two exam days, each with 3 problems and 6 hours time.

You are not allowed to bring anything.

## Hints

There are various GitHub Repos that have solutions for the problems of the previous years (the problems are mostly the same as they are old exam problems). I would recommend that if you are stuck on a problem for 4+ hours without finding a solution it might be worth to look a possible solution, understand it and try to learn from it.

Github Solutions HS14 (many solutions originate from here)

Obviously, you always want to go for the fastest algorithm (aim for ${\displaystyle O(log(n))}$ or ${\displaystyle O(n*log(n)}$), but it's not always easy to see if you're optimal yet. A rule of thumb is that one calculation should take about ${\displaystyle 1000000}$ computation steps, so if you have only ${\displaystyle 1000}$ elements, an ${\displaystyle O(n^{2})}$-algorithm might be fine.

Have a (mental) checklist of known solution attempts:

• Binary search
• Dynamic programming
• DFS/BFS of a graph
• Shortest path in a graph
• Maximum matching in a graph
• Maximum flow in a graph
• Planarity test of a graph
• Delaunay-Triangulation of a set of points
• Linear programming (CGAL has a linear program solver)

Don't despair if you have failed in the first half of the exam. Despair after the second part! ;)