Algorithmen und Datenstrukturen

Wintersemester 2011/2012

Carsten.Schneider@risc.uni-linz.ac.at



Erster Termin: Do   6.10.2011   08:30 - 10:00  Raum: T111

Es werden Algorithmen und Datenstrukturen vorgestellt, mit deren Hilfe grundlegende mathematische Objekte in einem Computer repräsentiert und bearbeitet werden können. Im Idealfall können dann diese Algorithmen/Datenstrukturen kombiniert werden, um komplexere mathematische Probleme algorithmisch zu lösen. Für die Auswahl von geeigneten Algorithmen/Datenstrukturen ist hierbei die Kostenanalyse in Bezug auf Laufzeit und Speicherplatz entscheidend. <

Schriftliche Prüfung: 9.02.2012. 10:00-11:30. HS 4

Inhalt der Lehrveranstaltung:


Die Vorlesung wird sich hauptsächlich an dem Buch
Datenstrukturen und Algorithmen: Güting
orientieren. Als Begleitbücher empfehle ich
Algorithmen und Datenstrukturen: Wirth,
und
The Design and Analysis of Algorithms: Aho, Hopcroft und Ullman.


Jede Art von Fragen sind willkommen.

Übunsaufgaben

Besprechnung: Donnerstag 13:30-14:15 (Raum S2Z75) oder Donnerstag 16:15-17:00 (Raum MZ 005A)
Übungsleiter: Patrick Wijerama (patrick.wijeramaATgmailDOTcom)

Aufgabe 1 (20.10.2011)

Implementieren Sie die in der Vorlesung vorgestellen Algorithmen contains, contains_2 und contains_3 in C++.
Testen Sie Ihre Implementierungen mit den Beispielzahlen IntegerWerte.txt.
Wie verhalten sich die Implementierungen zeitlich, wenn Sie 300000 Aufrufe mit zufaellig ausgewaehlten Zahlen hintereinander ausführen?

Aufgabe 2 (27.10.2011)

 Achtung: Ausnahmsweise wird das Tutorium (13:30-14:15) nicht im Raum S2Z75 so dern im Hoersaal HS13 stattfinden.

Implementieren Sie die Datenstruktur Stack mit Hilfe eines Arrays. Benutzen Sie anschließend diese Implementierung zum Auswerten von arithmetischen Ausdrücken
(Zum Einlesen genügt es, ganze Zahlen zu lesen und die Gundoperationen +,*,- zu berechnen).

Aufgabe 3 (3.11.2011)

Implementieren Sie Algebra List2 mit Hilfer einer doppelt verketteten Liste. Es genügt die Funktionen empty, insert und find zu implementieren.
Erzeugen Sie damit die Liste l=<2,4,6,...,100> und rufen Sie anschließend find(l,50) und find(l,51) auf.

Aufgabe 4 (10.11.2011)

Implementieren Sie die Algebra Set mit geordneten verketteten Listen. Es genügt empty, insert und intersection zu implementieren.
Testen Sie anschlißend ihre Funktion an Hand von geeigneten Tests.

Aufgabe 5 (17.11.2011)

Implementieren Sie die Datenstruktur Binärer Suchbaum mit den Funktionen empty, member und insert.

Aufgabe 6 (24.11.2011)

Vervollstä:ndigen Sie Ihre Implementieren Binärer Suchbaum mit der Funktion delete.

Aufgabe 7 (1.12.2011)

Implementieren Sie die Datenstruktur AVL Baum mit den Funktionen empty, member und insert.

Aufgabe 8 (15.12.2011)

A) Implementieren Sie die Addition und Multiplikation von zwei Polynomen aus Z[x] in dense representation welche mit Hilfe von verketten Listen representiert sind. B) Implementieren Sie die Addition (Bonusproblem: Multiplikation) von zwei Polynomen aus Z[x] in sparse representation welche mit Hilfe von verketten Listen representiert sind.

Aufgabe 9 (12.1.2012)

Implementieren Sie den Algorithmus MergeSort, welcher ein Integer Array in ein sortiertes Array umwandelt. Testen sie das Programm mit den Beispielzahlen sortdaten.txt.

Aufgabe 10 (19.1.2012)

Implementieren Sie den Algorithmus QuickSort, welcher ein Integer Array in ein sortiertes Array umwandelt. Testen sie das Programm mit den Beispielzahlen sortdaten.txt.