Universität Wien
Warning! The directory is not yet complete and will be amended until the beginning of the term.

052120 VU Advanced Topics in Algorithms (2019W)

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

  • Tuesday 01.10. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 07.10. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 08.10. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 14.10. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 15.10. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 21.10. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 22.10. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 28.10. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 29.10. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 04.11. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 05.11. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 11.11. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 12.11. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 18.11. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 19.11. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 25.11. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 26.11. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 02.12. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 03.12. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 09.12. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 10.12. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 16.12. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 17.12. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Tuesday 07.01. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 13.01. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 14.01. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 20.01. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 21.01. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 27.01. 09:45 - 11:15 Seminarraum 3, Währinger Straße 29 1.UG
  • Tuesday 28.01. 08:00 - 09:30 Seminarraum 7, Währinger Straße 29 1.OG

Information

Aims, contents and method of the course

In this lecture, the students obtain a systematic understanding of algorithmic questions and solution approaches in the area of algorithm engineering. The students will be able to transfer the learned techniques onto similar problems and be able to interpret and understand current research topic in the area of algorithm engineering.

Content:
What is algorithm engineering?
Realistic machine models and applications
Algorithm design
Implementation techniques
Experimental methodology
Interpretation of measurements

The listed abilities will be learned by concrete examples. As example we will use topics from the following areas:
FPT/Kernelization in Practice
- Independent set / vertex cover
- Minimum cuts (NOI algorithm, ...)
- Clique cover
- Node ordering
- Exact branch-and-reduce
- ...
Graph partitioning / graph clustering
- NP-completeness
- Modularity clustering (internal, external memory)
- Dynamic clustering
- Multi-level approaches for partitioning
- Spectral techniques
- Exact approaches
- Hypergraph partitioning
- ...
Routen planning
- State-of-the-Art in route planning
- Energy-efficient routing
Graphen drawing
Parallel processing
- Parallel sampling
- Communication-free graph generation
- Process mapping
- ...

In particular, we will almost always cover the best practical and theoretical methods. This methods often deviate a lot by the algorithms learned in the basic courses. We will probably have a small coding competition in which the students develop an algorithm and can compete with each other about the fastest or best solution.

Assessment and permitted materials

There will be one oral examination and, depending on the choice of the student, either participation in a lecture internal programming competition (TBA) or a seminar talk about a recent research result in algorithm engineering. The oral exam yields 80 points and the other task yields 20 points.

Minimum requirements and assessment criteria

Grading scale: 100% = 100 points
89% <= P <= 100% Sehr Gut (1)
76% <= P < 89% Gut (2)
63% <= P < 76% Befriedigend (3)
50% <= P < 63% Genügend (4)
0% <= P < 50% Nicht Genügend (5)

Examination topics

The exams cover all the material presented in class, in the seminar talks, and in the reading material.

Reading list

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

Association in the course directory

Module: AT-AL

Last modified: Mo 07.09.2020 15:20