Achtung! Das Lehrangebot ist noch nicht vollständig und wird bis Semesterbeginn laufend ergänzt.

# 052100 VU Algorithms and Data Structures 2 (2021S)

Prüfungsimmanente Lehrveranstaltung
VOR-ORT

## An/Abmeldung

Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").
• Anmeldung von Mo 15.02.2021 09:00 bis Mo 22.02.2021 09:00
• Abmeldung bis So 14.03.2021 23:59

## Details

max. 25 Teilnehmer*innen
Sprache: Englisch

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

IMPORTANT: This is a second course on algorithms at University of Vienna, and hence has the following prerequisites.
1) Discrete mathematics: a one semester course, equivalent to 051110 VO Mathematical Foundations of Computer Science 1 at University of Vienna covering the following topics. Set theory, functions and relations, combinatorics (counting), applications of pigeonhole principle, etc., several proofs using the principle of mathematical induction, graph theory, probability theory, and linear algebra

2) Basic algorithms analysis and discrete structures: a one semester course, equivalent to 051024 VU Algorithms and Data Structures 1 at University of Vienna covering the following topics. Big-O notation and asymptotic analysis; lists, stacks, and queues and their applications; trees and binary trees: tree traversals (inorder, preorder, postorder); graphs: adjacency list and adjacency matrix representations, depth-first search, breadth first-search, minimum spanning tree algorithms, etc.; searching and sorting algorithms; divide and conquer algorithms

We need to start with a common minimum knowledge and be familiar with the mathematical/algorithmic language and notation. We will have a quiz at the end of the first lecture that will give you an idea of how much comfortable you are with these prerequisites. This quiz is COMPULSORY.

Note the following:
This is a mathematical course, and we will be focusing on mathematical proofs. Appropriate level of mathematical background is assumed. The main aim is to develop mathematical intuition with respect to algorithm analysis by doing several mathematical proofs. At the end of the course, you should be able to not only recognize correct mathematical proofs but also be able to come up with your own mathematical proofs of correctness of an algorithm and its running time.

Montag 01.03. 09:45 - 11:15 Digital
Montag 08.03. 09:45 - 11:15 Digital
Montag 15.03. 09:45 - 11:15 Digital
Montag 22.03. 09:45 - 11:15 Digital
Montag 12.04. 09:45 - 11:15 Digital
Montag 19.04. 09:45 - 11:15 Digital
Montag 26.04. 09:45 - 11:15 Digital
Montag 03.05. 09:45 - 11:15 Digital
Montag 10.05. 09:45 - 11:15 Digital
Montag 17.05. 09:45 - 11:15 Digital
Montag 31.05. 09:45 - 11:15 Digital
Montag 07.06. 09:45 - 11:15 Digital
Montag 14.06. 09:45 - 11:15 Digital
Montag 21.06. 09:45 - 11:15 Digital
Montag 28.06. 09:45 - 11:15 Hörsaal 14 Oskar-Morgenstern-Platz 1 2.Stock
Hörsaal 2, Währinger Straße 29 2.OG
Hörsaal 3, Währinger Straße 29 3.OG
Seminarraum 10, Währinger Straße 29 2.OG

## Information

### Ziele, Inhalte und Methode der Lehrveranstaltung

IMPORTANT: This is a second course on algorithms at University of Vienna, and hence has the following prerequisites.
1) Discrete mathematics: a one semester course, equivalent to 051110 VO Mathematical Foundations of Computer Science 1 at University of Vienna covering the following topics. Set theory, functions and relations, combinatorics (counting), applications of pigeonhole principle, etc., several proofs using the principle of mathematical induction, graph theory, probability theory, and linear algebra

2) Basic algorithms analysis and discrete structures: a one semester course, equivalent to 051024 VU Algorithms and Data Structures 1 at University of Vienna covering the following topics. Big-O notation and asymptotic analysis; lists, stacks, and queues and their applications; trees and binary trees: tree traversals (inorder, preorder, postorder); graphs: adjacency list and adjacency matrix representations, depth-first search, breadth first-search, minimum spanning tree algorithms, etc.; searching and sorting algorithms; divide and conquer algorithms

We need to start with a common minimum knowledge and be familiar with the mathematical/algorithmic language and notation. We will have a quiz at the end of the first lecture that will give you an idea of how much comfortable you are with these prerequisites.

This is a mathematical course, and we will be focusing on mathematical proofs. Appropriate level of mathematical background is assumed. The main aim is to develop mathematical intuition with respect to algorithm analysis by doing several mathematical proofs. At the end of the course, you should be able to not only recognize correct mathematical proofs but also be able to come up with your own mathematical proofs of correctness of an algorithm and its running time.
We will not do any programming.

Contents:
How to do rigorous proofs: mathematical logic and induction.
Algorithmic strategies: recursion (backtracking, branch and bound, heuristics, reduction transform and conquer), dynamic programming, and greedy algorithms (focus on dynamic programming and greedy algorithms)
Hashing; pattern matching and string algorithms
Advanced data structures and algorithms: network flows and geometric algorithms

### Art der Leistungskontrolle und erlaubte Hilfsmittel

Two quizzes, each worth 10 points
Two homeworks, each worth 5 points
Either a final exam or a project depending on the pandemic situation, worth 30 points.
Bonus points: Compulsory prerequisites quiz, 2 points and class participation, 8 points.

Exams/quizzes will be closed book, closed notes, and no resources/help from the Internet allowed.

Further details will be added soon.

### Mindestanforderungen und Beurteilungsmaßstab

percentage of points grade
>= 89% 1
>= 76% 2
>= 63% 3
>= 50% 4
< 50% 5

### Prüfungsstoff

Everything covered in the lectures, the homework problems, the slides, and the reading material

### Literatur

Will be provided on Moodle.

## Zuordnung im Vorlesungsverzeichnis

Module: CNA

Letzte Änderung: Mo 14.06.2021 11:08