|
|
Code: |
319650 |
|
Module title: |
Algorithms and Data Structures II |
|
Version: |
1.0 (11/2025) |
| Last update: |
4.12.2025 11:28:46 |
Person responsible for content: |
Prof. Dr. rer. nat. Batz, Gernot Veit
Veit.Batz@hszg.de |
|
| Semester according to timetable: | WiSe (winter semester)
|
| Module level: | Bachelor |
| Duration: | 1 semester |
| Language of Instruction: | German |
| Place where the module will be offered: | Görlitz |
|
| ECTS Credits: |
5 |
| Student workload (in hours): |
150 |
|
| Number of hours of teaching: |
total |
subdivided into |
| 4 |
2
Lecture |
1
Seminar/Exercise |
1
Laboratory work |
0
Other |
|
| Self study time (in hours): |
sum |
subdivided into |
| 105 |
90
Preparation of contact hours |
15
Preparation of exam |
0
Other |
|
| Learning and teaching methods: | Vorlesung
Seminar: Studierende bereiten Vorträge selbständig vor und halten diese
Übung: Vertiefen/wiederholen von Themen, Problemlösen
Praktikum: Implementieren, Performance-Messungen, Performancevergleiche
|
| Exam(s) |
| Minor exam | assessed assignment (confirmation of attendance) |
|
| Assessment | Major oral exam |
20 min |
100.0% |
|
| Syllabus plan/Content: |
- Tiefensuche und Breitensuche in Graphen
- Kürzeste Wege in Graphen
- Priority-Queues
- Minimale Spannbäume
- Union-Find-Strukturen
- Hashen mit linearer Suche
- Geometrische Anfragen
Optional weiterführende Themen soweit noch Zeit ist. Möglich sind z.B.:
- Flüsse in Netzwerken
- Perfektes Hashen
- Kürzeste Wege mit verallgemeinerten Kosten
- Weiterführendes dynamisches Programmieren
|
| Learning Goals |
| Subject-specific skills and competences: |
Die Absolventen/-innen besitzen solides Grundwissen im Bereich Algorithmen und Datenstrukturen.
Die Absolventen/-innen sind in der Lage, sich für sie neues Wissen in diesem Gebiet selbst anzueignen.
Die Absolventen/-innen haben zudem weitere Erfahrungen gesammelt mit dem dem lösen von algorithmischen Problemen und dem implementieren von algorithmischem Code.
Die Absolventen/-innen sind fähig, logische und algebraische Kalküle, graphentheoretische Notationen, formale Sprachen und Automaten zur Modellierung von Datenstrukturen und Algorithmen zu verwenden.
Dabei analysieren sie Problemstellung in verschiedenen Anwendungskontexten und identifizieren sie den algorithmischen Kern und entwerfen adäquate Datenstrukturen sowie Algorithmen unter Verwendung geeigneter Notationen nach passenden Lösungsmustern.
Anschließend verifizieren die Absolventen/-innen diese Entwürfe systematisch und bewerten den Ressourcenbedarf umfassend.
Weiterhin entwerfen die Absolventen/-innen Modelle auf verschiedenen Abstraktionsebenen und verifizieren diese eingehend, beispielsweise durch eine Simulation.
Sie zerlegen, verfeinern und konkretisieren die Modelle iterativ, wodurch ein durchgängiger und effizienter Modellierungsprozess von der Konzeption bis zur Implementierung gewährleistet wird. |
| Generic competences (Personal and key skills): |
Die Absolventen/-innen haben Erfahrungen mit dem selbständigen Vorbereiten und Halten eines Vortages. Dies schließt auch Erfahrungen mit dem selbständigen Lesen und Verstehen nicht-trivialer Fachlitaratur ein.
|
|
| Prerequisites: |
keine |
| Optional: |
- Kenntnisse aus der Mathematik, insbes. Mengenlehre, Induktionsbeweise und Wahrscheinlichkeitsrechung.
- Modul "Algorithmen und Datenstrukturen I", dort insbesondere asymptotische Laufzeitanalyse, grundlegende Datenstrukturen (wie verkettete Listen und dynamische Arrays) und Randomisierung.
|
|
| Literature: |
- P. Sanders, K. Mehlhorn, M. Dietzfelbinger, R. Dementiev,
"Sequential and Parallel Algorithms and Data Structures - The basic Toolbox",
Springer, 2019.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein
"Introduction to algorithms",
The MIT Press, Third edition, 2009
|
