| Semester | |
| Module # | INF-STD-18, INF-STD-20 |
| Event # | INF-ALG-019, INF-ALG-029 |
| Programmes | Computer Science Master, Business Information Systems Master, Computer and Communication Systems Engineering Master |
| IBR Group | ALG (Prof. Fekete) |
| Type | Seminar |
| Lecturer | |
| Assistants | Dr. Victor Alvarez Ehemaliger Wissenschaftlicher Mitarbeiter Dr. Phillip Keldenich Wissenschaftlicher Mitarbeiter keldenich[[at]]ibr.cs.tu-bs.de +49 531 3913112 Room 317 |
| Credits | 5 |
| Hours | 0+2 |
| Prerequisites | Voraussetzungen für die Bearbeitung der einzelnen Themen sind jeweils individuell aufgeführt. Sind diese in Klammern gesetzt, sind sie zwar hilfreich, aber keine Voraussetzung. |
| Certificates | Schriftliche Ausarbeitung und erfolgreicher Seminarvortrag. Die Note wird abhängig von der aktiven Teilnahme am Seminar sowie der Qualität des Vortrages und der Ausarbeitung bestimmt. |
| Registration | Anmeldung zentral (über StudIP). Die Vorbesprechung für das Seminar erfolgt am 24.10.2016 um 13:00 Uhr im Besprechungsraum der Abteilung Algorithmik (IZ313). |
| Content | Das Seminar Algorithmik beschäftigt sich dieses Semester mit einer Reihe von aktuellen Artikeln sowie Ausschnitten aus Büchern. Die genauen Themen sowie eine Abstract sind weiter unten aufgeführt. |
| Schedule | 24.10.2016, 13:00 Kickoff-Meeting (IZ313) 09.01.2017 Peer-Review 16.01.2017 Feedback 23.01.2017 Final Version 27.01.2017 Erste Vortragsversion 06.02.2017 Vorträge (IZ313) |
| References | Literaturrecherche: Ausarbeitung und Vortrag: |
HinweiseTeilnehmerzahlEs werden 4 Plätze für Studierende auf Masterniveau angeboten.AusarbeitungDie Ausarbeitung soll etwa 8-10 Seiten lang sein. Generell interessiert uns, dass Sie da eine selbstverfasste Zusammenfassung eines selbst verstandenen Artikels abgeben. Wesentlich mehr als die genannte Seitenzahl sollte es nicht werden, immerhin geht es hier um die Kunst des Zusammenfassens. Wir erwarten, dass Sie selbstständig zusätzliche Quellen recherchieren. VortragIhr Vortrag soll etwa 30 Minuten (reine Vortragszeit) dauern. Anschließend wird es eine kurze Diskussionsrunde mit Fragen geben. Das Medium ist frei, Sie können also Whiteboard, Overhead-Projektor, Beamer mit PowerPoint, Beamer mit PDF, oder was auch immer Sie für sinnvoll erachten, einsetzen. Natürlich sollten Sie bei exotischen Wünschen diese erstmal mit dem Betreuer klären, und unbedingt auch Programm-, Programmversions- und sonstige Kompatibilitätsfragen besprechen. Themen für MasterstudentenGrundsätzlich ist es im Masterbereich möglich, an aktuellen Forschungsthemen aus der Algorithmik zu arbeiten. Falls kein spezielles Thema gewünscht ist, wird nach Rücksprache mit dem Teilnehmer ein Thema aus einer Liste von Themen zugewiesen. Die Themen dieses Semesters sind: Gomory-Hu TreesThe network flow problem was first introduced by Ford Fulkerson who introduced the basic concept of flow, cut, etc. and provided the main tool, the maximum-flow minimum-cut theorem. Ford and Fulkerson wrote about the flow between two special points, the source and the sink. Mayeda then took up the multi-terminal problem, where flows are considered between all pairs of nodes in a network. In the discussed paper of Gomory and Hu it is continued with the multi-terminal problem, giving results on realizability, analysis and synthesis.The Geometric Maximum Traveling Salesman ProblemThe classical Traveling Salesman Problem asks for a tour through a given set of vertices such that the total distance of this tour is minimized. Instead of minimizing the total length, one can also asks for a maximum total tour length. It can be shown that such an optimal tour can be computed in time O(n) if distances are determined by the Manhatten metric, while it is NP-hard under Euclidean distances.Algorithms for Ham-Sandwich CutsGiven disjoint sets P_1, P_2, ..., P_d in R^d with n points in total, a ham sandwich cut is a hyperplane that simultaneously bisects the P_i. There is an algorithm for finding ham-sandwich cuts in every dimension d>1. When d=2, the algorithm is optimal, having complexity O(n). For dimension d>2, the bound on the running time is proportional to the worst-case time needed for constructing a level in an arrangement of n hyperplanes in dimension d-1.Generalizing Ham-Sandwich Cuts to Equitable SubdivisionsGiven gn red points and gm blue points in the plane in general position, there exists an equitable subdivision of the plane into g disjoint convex polygons, each of which contains n red points and m blue points.This is a generalization of the Ham Sandwich Theorem for the plane. There is also an efficient algorithm for constructing such equitable subdivisions. | |