Uni Wien:Algorithmen und Datenstrukturen UE (Wanek, Polaschek)

Diese LVA wird nicht mehr von dieser Person angeboten, ist ausgelaufen, oder läuft aus und befindet sich daher nur noch zu historischen Zwecken im VoWi.

Daten

• LV-Kürzel: PI.ADS.AD.UE
• im Modul enthalten: Algorithmen und Datenstrukturen VO
• Übungsleiter: Dipl.-Ing. Helmut Wanek, Univ. Ass. Dr. Martin Polaschek
• ECTS: 2 (SWS: 1)
• Empfohlenes Semester: 2
• HP der LVA: HP mit Allem Notwendigen
• Institut: Institute of Scientific Computing
• Vorlage:521

Inhalt

Ziele

Die Studierenden erlangen Kenntnisse über Aufwandsabschätzungen, Komplexitätsmaße, grundlegende Datenstrukturen, Such- und Sortierverfahren und grundlegende Graph- und Optimierungsalgorithmen. Sie werden dadurch befähigt Algorithmen und geeignete Datenstrukturen für gegebene Problemstellungen zu entwerfen oder auszuwählen und das Leistungsverhalten zu beurteilen.

(zit. nach: Studienplan)

Themen

Implementieren eines Sortieralgorithmus und einer Datenstruktur bei einer gegebenen abstrakten Klasse in C++. Mögliche Datenstrukturen:

• B+-Baum
• Heap mit Heapsort
• Double Hashing
• Separate Chaining
• Extendible Hashing
• Linear Hashing

Mögliche Sortierverfahren:

• Heapsort
• Insertionsort
• Mergesort
• Quicksort
• Radixsort
• Selectionsort
• Shellsort
• Bucketsort

Zwischentest

In einem Zwischentest wird überprüft, inwieweit man die gewählte Datenstruktur verstanden hat. Der Test dauert etwa 60 Minuten, 20 Punkte sind zu erreichen. Je nach gewählter Datenstruktur sehen die Fragen etwa wie folgt aus:

• Fügen Sie die Werte 24, 8, 14, 25, 22, 1, 2, 9, 6, 4 nacheinander in eine Hashtabelle der Größe 10 ein (Hashfunktion %10) und zeichnen Sie die Tabelle nach jedem Schritt.
• Wann ist es sinnvoll, die Tabelle zu vergrößern?
• Löschen Sie die Werte 14, 1 und 2 aus der Tabelle. Zeichnen Sie die Tabelle nach jedem Schritt.

Ablauf

• Seit dem SS08 ist die Lehrveranstaltung in Einzelarbeit zu erledigen. Man bekommt ein Thema zugeteilt. Tutoriums-Termine, bei denen man erfährt, was wie und bis wann zu machen ist. Da die Folien online gestellt werden, muss man sich auch nicht zu so früher Stunde ins Tutorium bewegen, wenn man meint, die Forderungen auch so zu verstehen.
• Verpflichtend anwesend muss man nur bei einer Abgabe sein. 1. Implementierung der Datenstruktur ist online abzugeben, 2. Implementierung der Datenstruktur und des Sortieralgorithmus online abzugeben, und 3. Abgabe des ganzen Projekts bei einem Abgabegespräch. Zu den Abgabeterminen muss man sich termingerecht auf der Homepage anmelden, man ist also auch hier relativ flexibel.
• Sehr elegant finde ich das Testskript der Homepage (von einem Tutor erstellt AFAIK), das die Basis für eine positive Beurteilung bildet (SUCCESS, WARNING, FAILED sind die 3 möglichen Stati für die Implementierung). Man lädt seine .c und seine .h-Datei hoch. Es werden sowohl die Funktionalität als auch die vorgegebenen Definitionen und Richtlinien (Klassendefinition, Dateistruktur, etc) überprüft.
• Genaueres findet sich auf der Homepage.
• Der hohe Freiheitsgrad bei der Erfüllung des Zieles dieser Lehrveranstaltung hat mir sehr gefallen. So stelle ich mir eine wirkliche UE oder ein PR in einer Universität vor.
• Oben steht, man lädt seine .c und .h Datei hoch, das ist eine veraltete Information. Es wird lediglich eine .h-Datei hochgeladen, z.B. "ContDoubleHashingShellSort.h". Die Lücke zwischen EPROG und AlgoDat ist sehr groß, sie sollten aufbauend sein. Es gibt sehr viele Eigenheiten des Unittests, die man erst nach mehrmaligem Testen herausfindet. Das einzige, was meiner Meinung nach, excellent (1+) aussieht, sind die "Performance Charts". Diese Lehrveranstaltung würde ich mit Schulnote 2+ bewerten.

Benötigte/Empfehlenswerte Vorkenntnisse

• EPROG oder zumindest erweiterte Kenntnisse in C++ (Klassen)
• Update: September 2012 - EPROG reicht für Algodat nicht ganz, erweiterte OOP + Templating-Kenntnisse sind notwendig. TeilnehmerInnen der LV Algodat (neuerdings heißt es ADS) würde ich das Buch "Moderne C++ Programmierung" von "Ralf Schneeweiß" ans Herz legen. Hier sind die wichtigsten Datenstrukturen verständlich und in Beispielen erklärt.

Literatur

• Gründsätzlich nur das VO-Skriptum, das es zum Selbstkostenpreis von 6 EUR gebunden an der Informatik-Servicestelle zu kaufen gibt.
• Zusätzlich kann man sich noch ein bisschen mit einschlägigen AlgoDat-Lehrbüchern beschäftigen, falls man eine nette Implementierung für einen Sortieralgorithmus braucht oder einfach nur zum Vergleich. Für eine positive Note ist dies aber nicht zwingend erforderlich.

Zeitaufwand

Ich würde sagen, dass man für die Implementierung schon zweieinhalb Tage (1. Tag Schreiben, 2. Tag Fehler und Bugs suchen und beheben, 3. Halbtag Forderungen des Testskriptes auf der Homepage erfüllen ) einplanen sollte. Wenn man in EPROG ohnehin noch nicht so gut war, eventuell noch mehr. Zurzeit ist die Abgabe in 3 Teile geteilt: 1) Grundlegender Funktionsumfang (Add-Methode) 2) Gesamte Implementierung 3) Optimierung. Für jeden Teil hat man mehrere Wochen Zeit, es empfiehlt sich trotzdem, früh genug anzufangen und regelmäßig das Forum aufzusuchen, da dort aktuelle Neuigkeiten ausgetauscht werden.

Leistungsbeurteilung

Sehr fair, wenn man die Deadlines und Richtlinien einhält, das Programm selbst schreibt und sich vor dem Abgabegspräch (wo man als Einzelperson seine Struktur erklärt) ein klein wenig vorbereitet. Für den erfolgreichen Abschluss der Übung sind zumindest 50 von 100 möglichen Punkten zu erreichen. Die Punkte werden wie folgt vergeben:

• 20 Punkte für den schriftlichen Test
• 10 Punkte für den fristgerechten Abschluss der ersten Projektphase
• 10 Punkte für den fristgerechten Abschluss der zweiten Projektphase
• XX Punkte für das Projekt, das in einem Abgabegespräch bewertet wird (60 für B+-Baum, 45 für Extendible- und Linear Hashing, 30 für den Rest)
• 10 Punkte für die Qualität der Implementierung im Vergleich zu den anderen Studierenden (bezüglich Performance und Speicherplatzbedarf)

Die LV-Leiter - wenn sie es auch zum Teil persönlich genommen haben - haben nun die Übung weitesgehend optimiert. In der letzten Version, dürfen TeilnehmerInnen die gewünschte Implementierung selbst auswählen.

• >= 87,5 sehr gut (1)
• >= 75 gut (2)
• >= 62,5 befriedigend (3)
• >= 50 genügend (4)
• < 50 nicht genügend (5)

Wo gibts Hilfe?

• Das auf der Homepage eigens eingerichtete Forum war bei uns relativ gut frequentiert, nicht nur von Studenten, auch von Tutoren und Übungsleitern, allen voran Prof. Wanek, der auch um 03 Uhr morgens noch bereit war, sein Wissen zu vermitteln, was mich immer wieder erstaunte, als ich ins Forum schaute.
• Prinzipiell gibt es auch abseits der 3 Tutoriumstermine, die die Vorschriften und Richtlinien für das Drehbuch, die Implementierung und die Evaluation vorstellen, gewöhnliche Tutoriumsterimine, an denen man Fragen stellen und Schwierigkeiten ausmerzen kann.
• https://www.facebook.com/groups/algodat.univie/

Materialien

Diese Seite hat noch keine Anhänge, du kannst aber neue hinzufügen.