Uni Wien:Algorithms and Data Structures 2 VU (Hanauer, Goranci)
Daten[Bearbeiten | Quelltext bearbeiten]
| Vortragende | Kathrin Hanauer, Gramoz Goranci |
|---|---|
| ECTS | 3,00 / 2,00 |
| Aufgezeichnet | <Bitte ergänzen>„“ ist kein Wahrheitswert (wahr/falsch). |
| Letzte Abhaltung | 2024S |
| Sprache | English |
| Links | ufind:052100 |
Inhalt[Bearbeiten | Quelltext bearbeiten]
Die Vorlesung war in zwei Teile geteilt. Der erste wurde von Kathrin Hanauer vorgetragen, der zweite von Gramoz Goranci.
Im ersten Teil wurden folgende Themen behandelt:
- Wiederholung von Beweismethoden
- Induktion
- Dynamic Programming
- Fibonacci
- Longest common subsequence
- Longest path in DAG
- Maximum Flow
- Ford-Fulkerson-Algorithmus
- Edmonds-Karp-Algorithmus
- Dinitz-Algorithmus
- Maximum Bipartite matching
Im zweiten Teil wurden folgende Themen behandelt:
- Greedy Algorithms
- Interval scheduling problem
- Minimum spanning tree
- Kruskal-Algorithmus, Union-Find-Datenstruktur
- Dijkstra-Algorithmus, Fast-Dijkstra-Algorithmus
- Hashing
- perfect hashing
- Kollisionen und Kollisionsbehandlung
- Hashing with Chaining
- Open Addressing
- Linear Probing
- Quadratic Probing
- Double Hashing
- Handling Deletions in Hashtables
- Universal Hashing
Ablauf[Bearbeiten | Quelltext bearbeiten]
Es gab jede Woche eine Vorlesungseinheit, bei der es keine Anwesenheitspflicht gab (allerdings gab es Bonuspunkte für die Anwesenheit).
Es gab unter dem Semester 2 Aufgabenblätter, je eines pro Vorlesungsteil.
Es gab auch 3 Moodle-Quizzes, ein Intro Quiz und je ein Quiz pro Vorlesungsteil. Diese bestehen aus relativ einfachen Fragen zu den Inhalten und stellen eine gute Vorbereitungen für den Abschlusstest dar. Man kann das Quizz zu einem beliebigen Zeitpunkt innerhalb eines vorgegebenen Zeitintervalls von 24h durchführen und hat 20 Min. Bearbeitungszeit.
Zusätzlich bekommt man einen Vorlesungstermin zugewiesen, zu dem man ein Scribe anfertigen soll. Ein Scribe ist quasi eine Mitschrift dieser Vorlesungseinheit ergänzt durch zusätzliche Erklärungen, Visualisierungen, oder Ähnlichem.
Nach jeder Vorlesungseinheit gibt es auf Moodle eine Question of The Day, also eine (meist einfache) Frage, die die Inhalte der Einheit behandelt. Für die richtige Beantwortung gibt es einen Bonuspunkt. Man hat für die Bearbeitung dieser Frage immer 24h Ziet.
Am Ende des Semesters gibt es einen Abschlusstest, bei dem der gesamte Stoff aus beiden Teilen abgefragt werden. Dabei wird nicht nur das Wissen benötigt, sondern auch die Fähigkeit, während des Tests beispielsweise einen Algorithmus zur Lösung eines Problems zu formuliern, seine Korrektheit zu beweisen und ihn zu analysieren.
Benötigte/Empfehlenswerte Vorkenntnisse[Bearbeiten | Quelltext bearbeiten]
ADS1, grundlegende mathematische Beweismethoden, Grundlagen der Graphentheorie, (sehr) grundlegende Kenntnisse in Latex
Vortrag[Bearbeiten | Quelltext bearbeiten]
Beide Vortragenden erklären die Inhalte gut und verständlich und gehen gerne auf Fragen ein, auch außerhalb der Vorlesung per E-mail.
Übungen[Bearbeiten | Quelltext bearbeiten]
Bei den beiden Aufgabenblättern muss man selber Algorithmen entwickeln und analysieren (z.B. Laufzeitkomplexität), hauptsächlich geht es aber um mathematische Beweise, etwa um die Korrektheit der eigenen Algorithmen oder vorgegebene Theoreme zu beweisen.
Prüfung, Benotung[Bearbeiten | Quelltext bearbeiten]
Es gibt 100 reguläre Punkte und 20 Bonuspunkte. Diese sind wie folgt aufgeteilt:
- reguläre Punkte
- Quizzes: 2*10
- Aufgabeblätter: 2*15
- Scribe: 10
- Abschlusstest: 40
- Bonuspunkte
- mindestens 12 mal anwesend: 5
- Question of the day: 13*1
- Intro Quiz: 2
Um zu bestehen, reicht es, insgesamt 50 Punkte zu haben.
Dauer der Zeugnisausstellung[Bearbeiten | Quelltext bearbeiten]
noch offen
Zeitaufwand[Bearbeiten | Quelltext bearbeiten]
Die Hausaufgaben, vor allem jene von Kathrin Hanauer, können jeweils mehrere Tage in Anspruch nehmen. Es kann aber stark variieren, weil es bei Beweisen oft eine Weil dauern kann, bis man auf eine Idee kommt, aber es kann einem auch schnell einfallen. Wenn man die Vorlesung immer besucht, gut aufpasst und Fragen stellt, ist der Lernaufwand nicht sehr groß.
Unterlagen[Bearbeiten | Quelltext bearbeiten]
Die Folien wurden immer spätestens kurz nach der jeweiligen Einheit online gestellt. Manche Scribes sind im Discord zu finden.
Tipps[Bearbeiten | Quelltext bearbeiten]
noch offen
Verbesserungsvorschläge / Kritik[Bearbeiten | Quelltext bearbeiten]
noch offen