Softwarepraktikum: Algorithmen und Datenstrukturen

Prof. Dr. Stefan Näher

Praktikum im Grundstudium über 4 SWS

Abgabe-Termine:

Abgabe der fertigen Programme bis Donnerstag 08.02.2007 an taphorn@uni-trier.de
Präsentation der Ergebnisse: Donnerstag, 15.02.2007 im CIP-Pool (H523) ab 08:30 Uhr

Inhalt

Implementierung von Algorithmen und Datenstrukturen in C++ unter Verwendung der
LEDA-Klassenbibliothek und der C++-Standardbibliothek.

Vorkenntnisse

Kenntnisse aus der Vorlesung "Algorithmen und Datenstrukturen (Info II)"

Dokumentation und Installation von LEDA

Online-Manual fr LEDA 5.1 pdf-Version
LEDA Guide
LEDA Book
sollten trotzdem noch Probleme auftreten: taphorn@uni-trier.de.

Übung

Abgabe der Übungen immer bis Dienstags an taphorn@uni-trier.de.
50% der erreichbaren Punkte berechtigen zur Teilnahme am Praktikum.

Übung 1: Implementierung von Heap-Sort auf C-Feldern
Übung 2: (1) Implementierung von Quicksort auf C-Feldern und Laufzeitvergleich mit Heap-Sort

Übung 3: Implementierung und Visualisierung von BFS und DFS, wie in Info II.

Übung 4: (1) Implementierung und Visualisierung des vorgestelleten Spanning-Tree Algorithmus

Übung 5: Implementierung des vorgestellten inkrementellen Algorithmus zur Berechnung der konvexen Hlle einer Punktemenge

Übung 6: Implementierung des Divide and Conquer Algorithmus zur Berechnung der konvexen Hlle einer Punktemenge

Punkte

MatrNr.	Übung 1 (10)	Übung 2 (15)	Übung 3 (15)	Übung 4 (15)	Übung 5 (20)	Übung 6 (15)	Gesamt (90)
687194	10	15	8	15	20	0	68
778187	8	15	15	15	20	0	73
790369	10	15	15	15	20	0	75
799968	9	2	0	0	0	0	11
842655	10	15	15	15	20	10	85
843155	7	15	11	15	12	5	65
843234	10	3	15	15	15	5	63
844196	10	5	15	15	10	0	55
847847	10	15	6	15	20	0	66
850974	10	13	0	15	10	0	48
861960	10	15	15	10	20	0	70
877396	10	10	15	15	20	10	80
833988	0	15	15	15	13	5	63
855923	0	0	0	0	17	10	27

Literatur

B. Stroustrup:
Die C++ Programmiersprache, Addison Wesley, ISBN 3-8273-1660-X

K. Mehlhorn, S. Näher:
LEDA - A platform for combinatorial and geometric computing, Cambridge Press, ISBN 0-521-56329-1

T. H. Cormen, C. E. Leiserson, R. L. Rivest:
Introductions to Algorithms, MIT Press, ISBN 0-262-03141-8

N. M. Josuttis:
The C++ Standard Library, Addison Wesley, ISBN 0-201-37926-0

E. Gamma, R. Helm, R. Johnson, J. Vlissides:
Design Patterns - Elements of Reusable Object-Oriented Software, Addison Wesley, ISBN 0-201-63361-2

Termin

Donnerstag

08 - 12 Uhr

H 523