Proseminar Algorithmentechnik

  • Type: proseminar
  • Chair: Prof. Dr. Peter Sanders
  • Semester: WS2011/12
  • Location:

    SR 301, Geb. 50.34 (Informatikhauptgebäude)

  • Time:

    Dienstag, 9.45-11.15

  • Start: 18.10.2011
  • Lecturer:

    Peter Sanders
    Veit Batz
    Timo Bingmann
    Christian Schulz

  • SWS: 2
  • Lv-No.: 24050
  • Exam:

    nein

Termine

Um Kollisionen mit anderen Veranstaltungen zu vermeiden, werden alle weiteren Termine außer der Vorbesprechung nach Absprache festgelegt.

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 Aquares: 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 Vorbesprechung findet am Dienstag, den 25.10.2011 um 9:45 im Seminarraum 301 (Gebäude 50.34) statt. Die Teilnahme an der Vorbesprechung ist verpflichtend. Dort findet auch die endgültige Anmeldung und die Zuteilung der zu bearbeitenden Themen statt.