Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Programmierwettbewerb
zur Vorlesung
Effiziente Algorithmen und Datenstrukturen

Begleitend zur Vorlesung gab es einen Programmierwettbewerb. Gestellt waren drei Aufgaben; bei jeder sollte ein Programm in C++ (übersetzbar mit g++) geschrieben werden.

Bei jeder der drei Programmieraufgaben war für das erste korrekte Programm, das auf vorgegebenen Test-Eingaben schneller lief als ein bereits existierendes, ebenfalls vorgegebenes, Programm und vor Behandlung der entsprechenden Algorithmen in der Vorlesung eingereicht wurde, ein Preis von einer Flasche Sekt ausgesetzt.

Die drei Aufgaben waren:

1. Alphabetisches Sortieren von ASCII-Strings
   Aufgabe war es, eine Liste von ASCII-Strings alphabetisch (also so, wie sie in einem Lexikon stehen würden) zu sortieren.
   Diese Aufgabe wurde von Herrn Peter Breitling gelöst.

2. Finden des Medians (mittleren Elementes) in einem Feld ganzer Zahlen
   Aufgabe war es, in einem Feld von ganzen Zahlen den Median zu finden; das ist das Element, das in der Mitte stünde, wäre das Feld sortiert (bei einer geraden Anzahl von Elementen soll es das kleinere der beiden mittleren sein).
   Diese Aufgabe wurde von Herrn Daniel Frey gelöst.

3. Finden eines kürzesten Pfades zwischen zwei vorgegebenen Knoten in einem gerichteten Graphen
   Aufgabe war es, in einem gerichteten Graphen mit nicht-negativ gewichteten Kanten die Länge eines kürzesten Pfades zwischen zwei vorgegebenen Knoten zu finden. (Die Länge eines Pfades ist die Summe der Gewichte seiner Kanten.)
   Diese Aufgabe wurde von Herrn Daniel Frey gelöst.