Algorithms Lab

Aus VISki
Version vom 1. Oktober 2019, 09:04 Uhr von Anklinv (Diskussion | Beiträge) (Hints: Add github repos)

(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Wechseln zu: Navigation, Suche

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 HS18

Github Solutions HS16

Github Solutions HS14 (many solutions originate from here)


Obviously, you always want to go for the fastest algorithm (aim for or ), but it's not always easy to see if you're optimal yet. A rule of thumb is that one calculation should take about computation steps, so if you have only elements, an -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! ;)