Universität Wien

052111 VU Advanced Algorithms (2022W)

6.00 ECTS (4.00 SWS), SPL 5 - Informatik und Wirtschaftsinformatik
Prüfungsimmanente Lehrveranstaltung
Moodle

An/Abmeldung

Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").

Details

max. 25 Teilnehmer*innen
Sprache: Englisch

Lehrende

Termine (iCal) - nächster Termin ist mit N markiert

Montag 03.10. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 04.10. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG
Montag 10.10. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 11.10. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG
Montag 17.10. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 18.10. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG
Montag 24.10. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 25.10. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG
Montag 31.10. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Montag 07.11. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 08.11. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG
Montag 14.11. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 15.11. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG
Montag 21.11. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 22.11. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG
Montag 28.11. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 29.11. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG
Montag 05.12. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 06.12. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG
Montag 12.12. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 13.12. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG
Montag 09.01. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 10.01. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG
Montag 16.01. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 17.01. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG
Montag 23.01. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 24.01. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG
Montag 30.01. 11:30 - 13:00 Seminarraum 7, Währinger Straße 29 1.OG
Dienstag 31.01. 15:00 - 16:30 Seminarraum 11, Währinger Straße 29 2.OG

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

We will study advanced topics in algorithms and data structures, such as:

- randomized algorithms
- advanced graph algorithms, e.g. for maximum flow and shortest paths
- advanced analysis techniques
- advanced data structures, e.g. heaps and Bloom filters
- online algorithms and competitive analysis
- approximation algorithms
- data stream algorithms
- linear programming

On successful completion of this course, you will have an in-depth knowledge and understanding of state-of-the-art algorithmic techniques in various areas.

The schedule consists of interactive lectures as well as homework discussions.

The course has a strong focus on theoretical understanding and mathematical precision and moves rather fast. It is highly recommended that you have successfully completed courses equivalent to the following:

- basics in discrete mathematics and linear algebra, e.g. 051110 VO Mathematical Foundations of Computer Science 1
- basic and intermediate topics in algorithms and data structures, e.g. 051024 VU Algorithms and Data Structures 1 and 052100 VU Algorithms and Data Structures 2
- basics in stochastics (probabilities), e.g. 051130 Introductory Statistics

If you are unsure whether you meet these prerequirements, please come and speak to us.

Art der Leistungskontrolle und erlaubte Hilfsmittel

A total of 100 regular points (100%) can be reached.

In each of the two halves of the semester, there will be
- 1 written exam (90 minutes) for up to 40 regular points,
- 2 homework sheets with several small problems each, one of them needs to be presented in class for up to 10 regular points,
resulting in 2 * (40 + 10) = 100 regular points.

Up to 22 bonus points can be reached:
- 5 bonus points if you miss at most 3 classes (-1 for every further missed class)
- up to 5 bonus points for participation on the Moodle forum
- up to 5 bonus points per semester half (= 2*5 in total) for solving one of the extra problems on a homework sheet
- up to 2 points for the prerequisites quiz on Moodle

Preliminary dates for the exams:
midterm exam: Monday, November 28, 2022
final exam: Tuesday, January 31, 2023

Mindestanforderungen und Beurteilungsmaßstab

If P is the sum of regular and bonus points received, your grade will be:

1, if P >= 89,
2, if P >= 76,
3, if P >= 63,
4, if P >= 50,
5, otherwise.

Presence is mandatory for the first lecture. Otherwise, it is not a requirement, but strongly recommended.
If you fail to show up for an exam, you will receive 0 points for this exam.

Homework sheets must be submitted before the deadline to be eligible for presentation in class. You can indicate for each problem on a homework sheet whether you would be willing to present it. The presenter for each problem is chosen by the instructors among all those that are willing to present, with ties broken randomly. There will be enough problems so that each student can present twice if everyone is willing to present all problems. If you fail to submit a homework sheet or are not chosen for presentation because you were unwilling to present many of the subproblems or are chosen to present but don't show up, you will receive 0 points.

Prüfungsstoff

- all material presented in class
- contents and discussion of all exercise sheets
- reading material as provided on Moodle

Literatur

Literature will be announced in class and (as far as possible) made available on Moodle.

Zuordnung im Vorlesungsverzeichnis

Module: AAL

Letzte Änderung: Mo 03.10.2022 12:48