| Carl-Friedrich-Gauß-Fakultät | Department Informatik

Algorithm Engineering

Modulnummer INF-ALG-05
VeranstaltungsnummerINF-ALG-009, INF-ALG-010
StudiengängeMaster Informatik, Master Wirtschaftsinformatik
IBR GruppeALG (Prof. Fekete)
PhotoDr. Victor Alvarez
Ehemaliger Wissenschaftlicher Mitarbeiter
PhotoDr. Victor Alvarez
Ehemaliger Wissenschaftlicher Mitarbeiter
Ort & Zeit Lecture: Wednesday, 13:15 - 14:45 hrs., PK 3.1

Tutorial: Tuesdays, 15:00 - 16:30 hrs., IZ 161, bi-weekly
Small Tutorial: Tuesdays, 15:00 - 16:30 hrs., IZ 161, bi-weekly.

Beginn First Lecture: Wednesday, 13.04.2016
First Tutorial: Tuesday, 26.04.2016
First Small Tutorial: Tuesday, 03.05.2016
VoraussetzungenBasic knowledge of analysis of Algorithms and Data Structures (AuD), and Graph Algorithms (NWA). Elementary knowledge of probability is useful but not required.
ScheinerwerbHomework assignments during the semester (=Studienleistung) and one exam at the end.

Algorithm Engineering has recently emerged as an interesting field of research. Traditionally, an algorithm is regarded efficient whenever its running time is polynomial in its input size (polynomial-time algorithm). Furthermore, when speaking about running times of algorithms, we tend to speak in terms of O-notation — which not only ignores lower-degree terms, but also ignores the constants preceding the terms. This situations tend to produce certain degree of doubt among practitioners as they cannot be sure whether a (theoretical) algorithm is usable at all in practice. This discrepancy produces a gap between theory and practice that Algorithm Engineering tries to bridge by designing algorithms that indeed exhibit fast execution times, but for which theoretical guarantees regarding performance can be proven. That is, Algorithm Engineering lives at the amazing intersection between Theoretical and Practical Computer Science.

In this course we will cover topics regarding:

  1. Sorting
  2. Hash tables
  3. Tree-based searching data structures
  4. Geometric optimization
  5. Shortest paths in graphs
  6. Geometric algorithms

Literatur/Links The course will be mostly based on recent research papers. All references will be given at the appropriate time. However, the following two books are excellent references about Algorithm Engineering:

General Information

  • Schedule of all lectures, tutorials, and home assignments: PDF [06.04.2016]
  • There is a mailinglist. We will distribute the homework sets and other announcements via this list, so, please subscribe!

aktualisiert am 13.04.2016, 16:15 von Dr. Victor Alvarez