Institute of Operating Systems and Computer Networks
- News
- About us
- Connected and Mobile Systems
- Distributed Systems
- Algorithms
- Microprocessor Lab
- Education
- Services
- Spin-Offs
- Research Cooperations
  - IST.hub

Seminar Algorithmik

Semester	Summer 2009 Summer 2023 Winter 2022/2023 Summer 2022 Winter 2021/2022 Summer 2021 Winter 2020/2021 Summer 2020 Winter 2019/2020 Summer 2019 Winter 2018/2019 Summer 2018 Winter 2017/2018 Summer 2017 Winter 2016/2017 Summer 2016 Winter 2015/2016 Summer 2015 Winter 2013/2014 Summer 2013 Winter 2012/2013 Summer 2012 Winter 2011/2012 Summer 2011 Winter 2010/2011 Winter 2009/2010 Winter 2008/2009
Module #	INF-ALG-019
Event #	INF-ALG-019
Programmes	Diplom Informatik, Computer Science Master, Business Information Systems Master, Computer and Communication Systems Engineering Bachelor, Computer and Communication Systems Engineering Master, Electrical Engineering Bachelor, Electrical Engineering Master
IBR Group	ALG (Prof. Fekete)
Type	Seminar
Lecturer	Prof. Dr. Sándor P. Fekete Abteilungsleiter s.fekete[[at]]tu-bs.de +49 531 3913111 Room 335
Assistants	Dr. Christiane Schmidt Ehemalige Wissenschaftliche Mitarbeiterin Dr. Tom Kamphans Ehemaliger Wissenschaftlicher Mitarbeiter
Credits	4
Hours	0+2
Time & Place	Die Vorbesprechung findet am 15.04.2009 in Room 262A statt. ACHTUNG NEU: In einer Blockveranstaltung am 26.06.2009 von 9 - 12 Uhr in Room 262A werden die Vorträge gehalten. Die Vortragsreihenfolge lautet: Marcus Apel, Marc Jandt, Bessem Medimagh, Zhiwei Chen. ACHTUNG NEU: Die Abgabe der Ausarbeitungen muss bis zum 12.06.2009 erfolgen.
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. Vortrag: Ihr Vortrag sollte ca. 40 Minuten dauern. Das Medium ist frei, Sie können also Tafel, Overhead-Projektor, Beamer mit PowerPoint, Beamer mit PDF, oder was auch immer Sie sinnvoll finden, 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. Ausarbeitung: Schreiben Sie eine Ausarbeitung, die Sie zwei Wochen vor dem Vortrag abgeben. Die Ausarbeitung soll ca. 5 Seiten lang sein. Generell interessiert uns aber, dass Sie da eine selbstverfasste Zusammenfassung eines selbst verstandenen Artikels abgeben. Mehr als zehn Seiten sollten es dennoch nicht werden, immerhin geht es hier um die Kunst des Zusammenfassens.
Content	Das Seminar Algorithmik im Sommersemester 2009 beschäftigt sich mit einer Reihe von aktuellen Artikeln, die relativ wenig an Vorwissen erfordern. Unten beschrieben sind die Originalauszüge der Autoren zu den eigenen Artikeln, die jeweils auf englisch erschienen, aber von überschaubarer Länge sind.
Thema 2: Searching for the Centre of a Circle Consider the problem of an agent or robot searching for the centre of a circle. The robot has only a limited number of capabilities. It can detect whether it is inside the circle or not. It can mark the point which it occupies. It can move in a straight line, possibly towards a mark which it made previously. It can make 90 an 180 degree turns. It can move to the middle of a line segment determined by two marked points, if it is on the line segment. The searcher starts at the edge of the circle. The objective is for the searcher to move to the centre of the circle as quickly as possible. Thema 3: Searching for the Center of an Ellipse Biedl et al. first posed the problem of finding the center of a circle, starting from a point on the boundary, using a limited number of operations. We solve an open problem, presented in their work: finding the center of the ellipse and provide results of experiments showing how these algorithms perform under the introduction of errors. Thema 7: Optimal Constraint Graph Exploration We address the problem of exploring an unknown graph G = (V; E) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both varaitations of the problem, the robot can only move along the edges of the graph, i.e, it cannot jump between non-adjacent vertices. In the tethered robot case, if the tether (rope) has length l, then the robot must remain within distance l from the start node s. In the second variation, a fuel tank of capacity C forces the robot to return to s after traversing C edges. The eciency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present an algorithm for a tethered robot which explores the graph in Theta(\|E\|) edge traversals. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a Theta(\|E\|) algorithm. This improves on the previous best known bound of O(\|E\| + \|V\| log^2 \|V\|) in [4]. Since the lower bound for the graph exploration problems is \|E\|, our algorithm is optimal, thus answering the open problem of Awerbuch, Betke, Rivest, and Singh [3]. Thema 8: Touring a Sequence of Polygons Given a sequence of k polygons in the plane, a start point s, and a target point, t, we seek a shortest path that starts at s, visits in order each of the polygons, and ends at t. If the polygons are disjoint and convex, we give an algorithm running in time O(kn log(n/k)), where n is the total number of vertices specifying the polygons. We also extend our results to a case in which the convex polygons are arbitrarily intersecting and the subpath between any two consecutive polygons is constrained to lie within a simply connected region; the algorithm uses O(nk^2 log n) time. Our methods are simple and allow shortest path queries from s to a query point t to be answered in time O(k log n + m), where m is the combinatorial path length. We show that for nonconvex polygons this "touring polygons " problem is NP-hard. The touring polygons problem is a strict generalization of some classic problems in computational geometry, including the safari problem, the zoo-keeper problem, and the watchman route problem in a simple polygon. Our new results give an order of magnitude improvement in the running times of the safari problem and the watchman route problem: We solve the safari problem in O(n^2 log n) time and the watchman route problem (through a fixed point s) in time O(n^3)