Proseminar Algorithmentechnik

  • Typ: Proseminar
  • Lehrstuhl: Prof. Dr. Peter Sanders
  • Ort:

    SR 236, Geb. 50.34 (Informatikhauptgebäude)

  • Zeit:

    Freitag, 9.45-11.15

  • Beginn: 25.10.2011
  • Dozent:

    Peter Sanders
    G. Veit Batz
    Timo Bingmann
    Christian Schulz

  • SWS: 2
  • ECTS: 3
  • LVNr.: 24050
  • Prüfung:

    nein

Termine und Regeln

Die Vorbesprechung fand am Dienstag, den 25.10.2011 um 9:45 im Seminarraum 301 statt. Die Teilnahme an der Vorbesprechung war verpflichtend. Um Kollisionen mit anderen Veranstaltungen zu vermeiden, wurden alle weiteren Termine außer der Vorbesprechung nach Absprache festgelegt.

Alle weiteren Seminartermine finden Freitags um 9:45 im Seminarraum 236 statt.

Die Slides zur Vorbesprechung enthalten alle verbindlichen Regelungen zur Durchführung des Seminars und sind in den Dokumenten verfügbar.

Inhalt

Behandelt werden ausgewählte Themen aus dem Buch "Algorithm Design" von J. Kleinberg und E. Tardos. Mögliche Themen sind z.B. folgende (Änderungen vorbehalten):

1 Introduction: Some Representative Problems
1.1 Stable Matching

4 Greedy Algorithms
4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead
4.2 Scheduling to Minimize Lateness: A More Complex Exchange Argument
4.7 Clustering
4.9 Minimum Cost Arborescences: A Multi-Phase Greedy Algorithm

5 Divide and Conquer
5.4 Finding the Closest Pair of Points
5.6 Convolutions and the Fast Fourier Transform

6 Dynamic Programming
6.1 Weighted Interval Scheduling:
6.3 Segmented Least Squares: Multi-way Choices
6.5 RNA Secondary Structure: Dynamic Programming over Intervals
6.6 Sequence Alignment

11 Approximation Algorithms
11.2 The Center Selection Problem
11.3 Set Cover: A General Greedy Heuristic

13 Randomized Algorithms
13.7 Finding the Closest Pair of Points

 

Studiengänge

Das Seminar richtet sich an Studierende des Bachelorstudienganges Informatik. Studierende anderer Studiengänge können nur nach Absprache teilnehmen.

Organisatorisches

Die Teilnahme an der Vorbesprechung ist verpflichtend. Dort findet auch die endgültige Anmeldung und die Zuteilung der zu bearbeitenden Themen statt.