Organization
- Lectures: Prof. Dr. Stefan Funke (Raum 1.111)
- Tutorials: Filip Krumpe, Thomas Mendel, Martin Seybold
Time and Location of Lectures/Tutorials:
| Time | Location | Starting | |
|---|---|---|---|
| Di | 09:45-11:15 | 0.457 | 11.04 |
| Mi | 15:45-17:15 | 1.140 | 12.04 |
Übungsblätter
| Nummer | Anmerkungen | Termin |
| Blatt 1 | saarland.graph, stuttgart_regbez.graph, bw.graph | |
| Blatt 2 | saarland.ch, stuttgart_regbez.ch, bw.ch | |
| Blatt 3 | Hawaii, Aachen | |
| Blatt 4 | movies | |
| Blatt 5 |
Small Java program for visualizing line segments on an OSM map here.
OpenGL viewer for larger graphs here (unpack; mkdir build; cmake ../; make) with a sample file
stutt.gl.bz2 (view with ./simple -opengl3 -gf stutt.gl).
Individual Project (Optional)
If you plan to conduct an individual project, please prepare a few slides (~5 minutes) before you start with your project, in particular addressing the following issues:
- problem description
- main challenges
- available data sets
- how can solution be evaluated
Tentative date for discussion about topics: July, 5th, tentative date for presentations: July, 11th.
Scribe Notes
The lecture will be accompanied by scribe notes (under preparation, current version here (updated 31.07.2017, more updates soon :))).
Contents (tentative)
In Algorithmics, one is interested in developing and designing algorithms which can solve a given problem as efficient as possible. For a theoretical computer scientist, this normally means to settle the computational complexity of the problem (Computable? NP-hard? PSPACE-hard? in P, NP, co-NP?) and then search for algorithms which are provably efficient, that is, comping up with fixed bounds on the time and space consumption by a rigorous mathematical analysis. And the less the resource consumption, the better the algorithm. But for real-world problems, as e.g. coming up with the best tours for a fleet of mail delivery vehicles, the algorithm with the best theoretical runtime is not automatically the most suitable algorithm. Here, it is more important, that the algorithm is actually implementable, produces quick and good solutions for the relevant instances and is flexible in case something new has to be considered. The scope of Algorithm Engineering is to design algorithms which work in both worlds. So we still aim for theoretical performance (and solution quality) guarantees, but equally important is the actual performance of the algorithm on real-world data, which makes implementation and evaluation mandatory. Note that AE is not the same as heuristic problem solving, where often optimality or even completeness is compromised in order to get some fast solution. Heuristics are typically not thoroughly analyzed but their validation is purely empirical.
Literatur
Manuscript about a theoretical analysis of speed-up techniques.
Survey about route planning in transportation networks.