Please disable Adblockers and enable JavaScript for domain CEWebS.cs.univie.ac.at! We have NO ADS, but they may interfere with some of our course material.

[Info][Unterlagen]

Ablauf

Leistungsbeurteilung

• Projektpunkte und Qualitätspunkte

• Positive Beurteilung

• Notenskala

• Berücksichtigung von Leistungen aus Algorithmen und Datenstrukturen VO und UE nach dem alten Curriculum

Ablauf

Die VU Algorithmen und Datenstrukturen 1 ist Bestandteil des Pflichtmoduls ADS Algorithmen und Datenstrukturen der Bachelorstudien Informatik und Wirtschaftsinformatik (Version 2016). In den Bachelorstudien Informatik und Wirtschaftsinformatik (Version 2011) sowie im Bachelorlehramtsstudium UF Informatik wird die VU Algorithmen und Datenstrukturen 1 anstelle der VO+UE Algorithmen und Datenstrukturen absolviert. Im Diplomlehramtsstudium wird die VU Algorithmen und Datenstrukturen 1 anstelle der VO+UE "Algorithmen, Datenstrukturen und Programmieren II" absolviert.

Die TeilnehmerInnen sollen die grundlegenden Algorithmen und Datenstrukturen kennenlernen und darüber hinaus in die Lage versetzt werden, die Komplexität und Qualität von Algorithmen und deren Implementierung zu bewerten.

Der Vorlesungsteil führt die grundlegenden Algorithmen und Datenstrukturen vor. Der vorgetragene Stoff bildet die Grundlage für die in den Übungen praktisch auszuarbeitenden Beispiele.

Die Vorlesung behandelt folgende Themenschwerpunkte:

Aufwandsabschätzungen
Komplexitätsmaße
Grundlegende Datenstrukturen
Such- und Sortierverfahren
Grundlegende Graph- und Optimierungsalgorithmen

Diese werden von Prof. Henzinger, Prof. Schikuta und DI Wanek vorgetragen.

Der Übungsteil wird in Form eines Projekts durchgeführt. Ziel des Projekts ist die Implementierung einer der in der Vorlesung behandelten Datenstrukturen. Die Studierenden können dabei aus einer Liste von Themen frei wählen. Die Themen sind unterschiedlich komplex, was später bei der Beurteilung berücksichtigt wird. Das Projekt wird im Anschluss an den Theoriekurs als Einzelarbeit durchgeführt.

und beginnt mit einem schriftlichen Test über die jeweils gewählte Datenstruktur (Einfügen, Suchen und Löschen anhand praktischer Fallbeispiele). Das Projekt selbst gliedert sich in drei Phasen: ## Erste Implementierung einer Datenstruktur (Einfügen und Suchen) ## Vollständige Implementierung (inklusive Löschen und Sortieren) ## Vergleich mit den Implementierungen anderer Studierender und Optimierungen ([CEWebS://themes/document/show&CEWebS_what=Themen|Themen]) >> Für jede Phase wird ein Abgabetermin festgelegt. Die Liste der gültigen Termine findet sich auf dieser Seite unter dem Tab [CEWebS://termine/document/show&CEWebS_what=Termine|Termine].

Für die Übung werden grundlegende Kenntnisse der objektorientierten Programmierung (im speziellen in C++) vorausgesetzt (i.e. die Inhalte der Lehrveranstaltung «Einführung in die Programmierung 1»).

Leistungsbeurteilung

Über den Vorlesungsteil wird eine schriftliche Klausurarbeit abgelegt. Die Klausurtermine werden auf dieser Webseite bekanntgegeben. Alte Prüfungsangaben sind online verfügbar. Insgesamt können in dieser Klausur maximal 100 Punkte erreicht werden.

Für den Übungsteil werden Punkte für die Arbeit im Projekt wie folgt vergeben:

0-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
0-xx Punkte für das Projekt (Maximalanzahl der Punkte abhängig vom gewählten Projekt zwischen 30 und 60). Das Projekt wird mit einer Klausur abgeschlossen, in deren Rahmen die eigene Implementierung zu erweitern ist.
- B+-Baum (60 Punkte)
- Statische Hashtabelle mit Separate Chaining (30 Punkte)
- Statische Hashtabelle mit Coalesced Chaining (40 Punkte)
- Extendible Hashing (50 Punkte)
- Linear Hashing (50 Punkte)
0-10 Punkte für die Qualität der Implementierung im Vergleich zu einer Referenzimplementierung (bezüglich Performance und Speicherplatzbedarf)

Projektpunkte und Qualitätspunkte

Zu jedem Thema werden die Leistungsdaten einer Referenzimplementierung zur Verfügung gestellt. Die Referenzimplementierung setzt keine Tricks oder Optimierungen ein und entspricht den Vorgaben in den Unterlagen. Die Leistungsdaten (Laufzeit, Speicherplatzbedarf) der Referenzimplementierung sollten daher in der Regel problemlos erreicht werden können.

Wenn die abgegebene Implementierung nicht den Vorgaben entspricht oder die Datenstrukturen bzw. Algorithmen nicht spezifikationskonform sind, dann werden Projektpunkte abgezogen. Bei schwerwiegend falschen Implementierungen kann dies eine positive Note verhindern. In einem solchen Fall muss auf jeden Fall nachgebessert werden (mit Projektpunkteabzug). Auch wenn die Leistungsdaten klar schlechter sind als jene der Referenzimplementierung weist dies auf eine falsche Implementierung hin und es werden Projektpunkte abgezogen. "Klar schlechter" bedeutet in der Ordnung schlechter oder um einen großen Faktor schlechter.

Die Projektpunkte können nur vergeben werden, wenn das Projekt im Rahmen der Abschlussklausur erfolgreich abgeschlossen wurde.

Wenn die Leistungsdaten der Implementierung klar besser sind als jene der Referenzimplementierung, dann werden dafür Qualitätspunkte vergeben. Die Leistungsdaten werden dabei immer im Gesamten betrachtet. Ein Leistungsvorteil in einem Aspekt darf dabei nicht durch einen Leistungsnachteil in einem anderen Aspekt "erkauft" werden. Auch hier geht es nicht um minimale Abweichungen bei der Laufzeit (dafür ist die Messmethodik zu ungenau) oder beim Speicherplatzbedarf, sondern um deutliche Unterschiede.

Positive Beurteilung

Voraussetzung für eine positive Beurteilung ist jedenfalls:

Die vorgegebenen Definitionen und Richtlinien (Klassendefinition, Dateistruktur, etc) werden eingehalten
Die Implementation ist in der Laborumgebung lauffähig
Die Implementation wird vom offiziellen Testscript ("Unit-Test") positiv evaluiert und absolviert den Performancetest ohne Fehler
Die Datenstruktur ist spezifikationskonform implementiert. Dies kann vom Testscript nicht überprüft werden und wird daher im Zuge der Beurteilung am Ende der Lehrveranstaltung überprüft. Es gelten die Vorgaben in den Vorlesungsfolien. Bei Abweichungen bitte vorher Rücksprache mit der LV-Leitung halten (im Forum).
Sowohl für den Vorlesungsteil, als auch für den Übungsteil werden jeweils mindestens 45 Punkte erreicht.

Notenskala

Punkte	Note
>= 175	sehr gut (1)
>= 150	gut (2)
>= 125	befriedigend (3)
>= 100	genügend (4)
< 100	nicht genügend (5)

Berücksichtigung von Leistungen aus Algorithmen und Datenstrukturen VO und UE nach dem alten Curriculum

Sollten Sie die Vorlesungsprüfung oder die Übung zu Algorithmen und Datenstrukturen nach dem alten Curriculum bereis erfolgreich (im selben Modus) absolviert haben, so braucht die entsprechende Teilleistung nicht nocheinmal erbracht zu werden. Wenn Sie dieses Angebot in Anspruch nehmen wollen, setzen Sie sich bitte per Mail mit «Helmut Wanek» in Verbindung. Geben Sie bitte das Datum der Vorlesungsprüfung bzw. das Semester, in dem die Übung absolviert wurde, an.