Universität Wien

052100 VU Algorithms and Data Structures 2 (2023W)

3.00 ECTS (2.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. 50 participants
Language: English

Lecturers

Classes (iCal) - next class is marked with N

NOTE:
The first class (kickoff class) will be in HS C1, UniCampus Hof 2, and not in HS 3, Währinger Straße.

Please also observe that attendance is mandatory for the first class by study law. This also applies if you are currently on the waiting list, i.e., please come to the first class if you are interested in taking this course.

  • Monday 02.10. 09:45 - 11:15 Hörsaal 3, Währinger Straße 29 3.OG
    Hörsaal C1 UniCampus Hof 2 2G-O1-03
  • Monday 09.10. 09:45 - 11:15 Hörsaal C1 UniCampus Hof 2 2G-O1-03
  • Monday 16.10. 09:45 - 11:15 Hörsaal C1 UniCampus Hof 2 2G-O1-03
  • Monday 23.10. 09:45 - 11:15 Hörsaal C1 UniCampus Hof 2 2G-O1-03
  • Monday 30.10. 09:45 - 11:15 Hörsaal C1 UniCampus Hof 2 2G-O1-03
  • Monday 06.11. 09:45 - 11:15 Hörsaal C1 UniCampus Hof 2 2G-O1-03
  • Monday 13.11. 09:45 - 11:15 Hörsaal C1 UniCampus Hof 2 2G-O1-03
  • Monday 13.11. 15:00 - 16:30 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 20.11. 09:45 - 11:15 Hörsaal C1 UniCampus Hof 2 2G-O1-03
  • Monday 27.11. 09:45 - 11:15 Hörsaal C1 UniCampus Hof 2 2G-O1-03
  • Monday 04.12. 09:45 - 11:15 Seminarraum 5, Kolingasse 14-16, EG00
  • Monday 11.12. 09:45 - 11:15 Hörsaal C1 UniCampus Hof 2 2G-O1-03
  • Monday 08.01. 09:45 - 11:15 Digital
  • Monday 15.01. 09:45 - 11:15 Hörsaal C1 UniCampus Hof 2 2G-O1-03
  • Monday 15.01. 16:45 - 18:15 Seminarraum 7, Währinger Straße 29 1.OG
  • Monday 22.01. 09:45 - 11:15 Hörsaal C1 UniCampus Hof 2 2G-O1-03
  • Monday 29.01. 09:45 - 11:15 Hörsaal 3, Währinger Straße 29 3.OG
    Seminarraum 5, Währinger Straße 29 1.UG
    Seminarraum 8, Währinger Straße 29 1.OG

Information

Aims, contents and method of the course

The main objective of this course is to learn some of the key techniques for designing and analyzing algorithms. We will study algorithmic paradigms and show concrete examples on how to use these paradigms to solve different optimization problems. This is a theoretical course, and we’ll largely be focusing on using mathematical tools to prove the correctness and the running time complexity of the algorithms.

At the end of the course, you should be able to recognize which paradigm you would need to use for solving new problems, as well as study the correctness and the time complexity of your suggested solutions.

Prerequisites:
- Discrete Mathematics – equivalent to 051110 VO Mathematical Foundations of Computer Science 1
- Introduction to Algorithms and Data Structures – equivalent to 051024 VU Algorithms and Data Structures 1

Topics:

* Proof Techniques

* Algorithmic Strategies:
- Dynamic Programming
- Greedy Algorithms

* Data Structures and Algorithms
- Maximum Flow
- Shortest Paths
- Hashing

Assessment and permitted materials

Students can collect up to 100 regular points as follows:
- 2 online multiple choice quizzes (up to 10 points each)
- 2 homework sheets (up to 15 points each)
- scribing a lecture (up to 10 points)
- written exam (up to 40 points)

In addition, up to 20 bonus points can be collected as follows:
- attending >= 12 classes (up to 5 points)
- answer the question of the day (up to 13 x 1 points)
- intro quiz (up to 2 points)

Exams/quizzes are closed-book, no resources/help from the Internet are allowed.

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.
There are no minimum required number of points per exam/homework sheet/quiz.

Examination topics

Everything covered in the lecture, the reading material, the homework problems, and the quizzes.

Reading list

- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms. MIT Press, 2009/2022 (3rd & 4th edition).
- Kleinberg, Jon; Tardos, Éva. Algorithm Design. Pearson, 2006.
- Erickson, Jeff. Algorithms. Online resource: http://algorithms.wtf/

Further literature will be provided via Moodle.

Association in the course directory

Last modified: Fr 05.01.2024 11:05