| Carl-Friedrich-Gauß-Faculty | Computer Science

Algorithm Engineering

Semester Summer 2016 [ Other terms: · Sommer 13 · Sommer 11 · Sommer 09 ]
Module # INF-ALG-05
Event # INF-ALG-009, INF-ALG-010
Programmes Master Informatik, Master Wirtschaftsinformatik
IBR Group(s) ALG (Prof. Fekete)
Type Vorlesung/Übung
Photo Dr. Victor Alvarez
Ehemaliger Wissenschaftlicher Mitarbeiter
Photo Dr. Victor Alvarez
Ehemaliger Wissenschaftlicher Mitarbeiter
Credits 5
Hours 2+1+1
Time & Place 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.

Start First Lecture: Wednesday, 13.04.2016
First Tutorial: Tuesday, 26.04.2016
First Small Tutorial: Tuesday, 03.05.2016
Prerequisites Basic knowledge of analysis of Algorithms and Data Structures (AuD), and Graph Algorithms (NWA). Elementary knowledge of probability is useful but not required.
Language English
Certificates Homework 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

References 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!

last changed 2016-04-13, 16:15 by Dr. Victor Alvarez