Veranstalter
Allgemeines
In diesem Seminar sollen ausgewählte Themen
aus verschiedenen Gebieten der Algorithmik bearbeitet und vorgestellt werden.
Im Zentrum des Seminars steht die theoretische Analyse von Algorithmen
bezüglich ihrer Korrektheit, Laufzeit und Güte.
Die Themenauswahl berücksichtigt insbesondere
die praktische Relevanz der vorgestellten algorithmischen Konzepte.
Jedes Thema wird von zwei Personen bearbeitet. In Gruppenarbeit werden Sie einen Vortrag von 90 Minuten Dauer (ca. 45 Minuten je Teilnehmer) zu ihrem Thema ausarbeiten. Der Inhalt sollte möglichst verständlich präsentiert werden. Der Vortrag sollte dabei nicht vornehmlich die Seminarleiter ansprechen, sondern insbesondere Ihre Komilitonen.
Termine
- Mittwoch 11. Juli, 17:15 Uhr, Raum 4017: Themenvergabe
- Mittwoch 17. Oktober, 15:30 Uhr, Raum 4017: Kurzpräsentationen (maximal 4 Minuten pro Teilnehmer)
- Freitag 26. Oktober: Abgabe der Ausarbeitungen (maximal 4 Seiten pro Teilnehmer)
- Ab Mittwoch 31. Oktober, jeweils 15:30 Uhr, Raum 4017: Vorträge (45 Minuten pro Teilnehmer, inklusive Diskussion)
Vorlage für die Ausarbeitung
Themen
- Randomisierte Clusterwahl [AV07]
Betreuer: Matthias Westermann
- Spannbäume mit beschränktem Grad [Goe06] und [SL07]
Betreuer: Matthias Westermann
- Randomisierte Approximation von Metriken [FRT04]
Betreuer: Matthias Englert
- Umsortierpuffer für allgemeine Metriken [ERW07]
Betreuer: Matthias Westermann
- Primzahltest in Polynomialzeit [AKS04]
Betreuer: Matthias Englert
- Analyse von 2-Opt für das TSP-Problem [ERV07]
Betreuer: Matthias Englert
- Union-Find mit Pfadkompression [HR00]
Betreuer: Matthias Englert
Literatur
- [AKS04]: Manindra Agrawal, Neeraj Kayal und Nitin Saxena. PRIMES is in P. Annals of Mathematics 160(2):781-793, 2004.
- [AV07]: David Arthur und Sergei Vassilvitskii. k-means++: The Advantages of Careful Seeding. In Proc. of the 18th ACM-SIAM Symposium on Discrete Algorithms (2007), 1027-1035.
- [ERV07]: Matthias Englert, Heiko Röglin und Berthold Vöcking. Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP (full version). In Proc. of the 18th ACM-SIAM Symposium on Discrete Algorithms (2007), 1295-1304.
- [ERW07]: Matthias Englert, Harald Räcke und Matthias Westermann. Reordering Buffers for General Metric Spaces. In Proc. of the 39th ACM Symposium on Theory of Computing (2007), 556-564.
- [FRT04]: Jittat Fakcharoenphol, Satish Rao und Kunal Talwar. A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics. Journal of Computer and System Sciences, 69(3):485-497, 2004.
- [Goe06]: Michel Goemans. Minimum Bounded Degree Spanning Trees. In Proc. of the 47th Annual IEEE Symposium on Foundations of Computer Science (2006), 273-282.
- [HR00]: Gregory Harfst und Edward Reingold. A Potential-Based Amortized Analysis of the Union-Find Data Structure. ACM SIGACT News 31(3):86-95, 2000.
- [SL07]: Mohit Singh und Lap Chi Lau. Approximating Minimum Bounded Degree Spanning Tress to within One of Optimal. In Proc. of the 39th ACM Symposium on Theory of Computing (2007), 661-670.