Universität Wien

051024 VU Algorithms and Data Structures 1 (2020W)

6.00 ECTS (4.00 SWS), SPL 5 - Informatik und Wirtschaftsinformatik
Continuous assessment of course work
CEWebs

Registration/Deregistration

Note: The time of your registration within the registration period has no effect on the allocation of places (no first come, first served).

Details

max. 100 participants
Language: German

Lecturers

Classes (iCal) - next class is marked with N

Die Vorbesprechung findet am 12.10.2020 um 9:45 online als Collaborate Sitzung statt. Der Link zu dieser Sitzung wird auf der Lehrplattform CEWebS bekanntgegeben.

  • Monday 12.10. 09:45 - 11:15 Digital
  • Thursday 10.12. 11:30 - 14:45 PC-Unterrichtsraum 2, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 3, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 4, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 5, Währinger Straße 29 2.OG
    PC-Unterrichtsraum 6, Währinger Straße 29 2.OG
  • Thursday 10.12. 15:00 - 18:15 PC-Unterrichtsraum 2, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 3, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 4, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 5, Währinger Straße 29 2.OG
    PC-Unterrichtsraum 6, Währinger Straße 29 2.OG
  • Monday 14.12. 08:30 - 10:30 Hörsaal 1, Währinger Straße 29 1.UG
  • Thursday 21.01. 11:30 - 14:45 PC-Unterrichtsraum 2, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 3, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 4, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 5, Währinger Straße 29 2.OG
    PC-Unterrichtsraum 6, Währinger Straße 29 2.OG
  • Monday 25.01. 08:30 - 10:30 Hörsaal 1, Währinger Straße 29 1.UG
    PC-Unterrichtsraum 1, Währinger Straße 29 1.UG
  • Thursday 11.02. 11:30 - 14:45 PC-Unterrichtsraum 2, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 3, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 4, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 5, Währinger Straße 29 2.OG
    PC-Unterrichtsraum 6, Währinger Straße 29 2.OG
  • Monday 15.02. 10:00 - 12:00 Hörsaal 1, Währinger Straße 29 1.UG

Information

Aims, contents and method of the course

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.

In der Lehrveranstaltung im Wintersemester entfällt der Vorlesungsteil. Zur selbstständigen Erarbeitung des Stoffes stehen die Unterlagen und aufgezeichneten Streams aus vorangegangenen Sommersemestern zur Verfügung.

Im Laufe des Semesters muss eine auszuwählende Datenstruktur implementiert werden.

Folgende Stoffinhalte sind neben den Fähigkeiten, die für die Programmierung der Datenstruktur notwendig sind, relevant:
0. Einführung (Programmstrukturen )
1. Algorithmen (Paradigmen, Analyse)
2. Datenstrukturen (Allgemeiner Überblick)
3. Listen (Lineare Speicherstrukturen, Stack, Queue)
4. Bäume (Suchstrukturen)
5. Vektoren (Sortieren, Hashing)
6. Graphen (Optimierungsalgorithmen)
Diese Inhalte werden im Rahmen einer theoretischen Prüfung am Ende des Semesters geprüft.

Assessment and permitted materials

Für den Praktikumsteil (Projekt) sind mehrere Teilleistungen zu erbringen. Im Laufe des Semesters ist ein schriftlicher Test zu absolvieren, sowie ein Projekt mit einer aus einer Liste möglicher Themen gewählten Aufgabenstellung zu realisieren. Für einzelne Teilleistungen werden Punkte vergeben. Die maximal erreichbaren Punkte sind - abhängig vom Aufwand/Schwierigkeitsgrad - je nach Thema unterschiedlich. Das Projekt wird mit einer Klausurarbeit abgeschlossen, in deren Rahmen die eigene Implementierung zu erweitern ist. Diese Klausur wird als Präsenztermin im Rechnerlabor durchgeführt. Es sind keine Hilfsmittel erlaubt.

Der schriftliche Test im Praktikumsteil findet online statt. Es werden die grundlegenden Operationen (Einfügen/Löschen/Suchen) auf der für das Projekt ausgewählten Datenstruktur geprüft. Als Hilfsmittel sind nur die auf der Webseite der LV zur Verfügung gestellten Unterrichtsmaterialien zulässig.

Insgesamt können für den Praktikumsteil bis zu 100 Punkte erreicht werden (80 für das Projekt, 20 für den schritlichen Test).

Für die theoretische Prüfung am Ende des Semesters werden ebenfalls bis zu 100 Punkte vergeben. Die Prüfung findet als Präsenztermin statt, es sind keine Hilfsmittel zugelassen.

Minimum requirements and assessment criteria

Für den erfolgreichen Abschluss sind zumindest jeweils 45 Punkte bei der Vorlesungsprüfung und beim Praktikumsteil erforderlich. Die Note ergibt sich aus der erreichten Punkteanzahl wie folgt:

>=175 Punkte Sehr gut
<175 Punkte und >=150 Punkte Gut
<150 Punkte und >=125 Punkte Befriedigend
<125 Punkte und >=100 Punkte Genügend
<100 Punkte Nicht genügend

Examination topics

Die Prüfung zum Vorlesungsteil umfasst den gesamten in der Vorlesung im vorangehenden Sommersemester vorgetragenen Stoffinhalt (Folien des Vortrags sind auf der Webseite verfügbar).

Prüfungsstoff im Praktikumsteil ist das gewählte Thema und der für dessen Implementierung erforderliche Sprachumfang von C++17.

Reading list

R. Sedgewick, Algorithmen in C++ (Teil 1-4), Addison Wesley, 3. überarbeitete Auflage, 2002.
Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms, published by MIT Press and McGraw-Hill. (First published in 1990.)
Steven Skiena, The Algorithm Design Manual, 2nd Edition, Springer
Donald E. Knuth, The Art of Computer Programming (Vol 1-3), Addison Wesley.

Bjarne Stroustrup, Einführung in die Programmierung mit C++, Pearson Studium.
Bjarne Stroustrup, Programming Principles and Practice Using C++, Addison Wesley.
Bjarne Stroustrup, The C++ Programming Language, Addison Wesley.

Association in the course directory

Module: ADS UF-INF-09

Last modified: Fr 12.05.2023 00:13