Universität Wien

052111 VU Advanced Algorithms (2022W)

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

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. 25 participants
Language: English

Lecturers

Classes (iCal) - next class is marked with N

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

Information

Aims, contents and method of the course

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.

Assessment and permitted materials

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

Minimum requirements and assessment criteria

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.

Examination topics

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

Reading list

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

Association in the course directory

Module: AAL

Last modified: Mo 03.10.2022 12:48