052100 VU Algorithms and Data Structures 2 (2022S)

Please always address me by my first name "Sagar" in all communications.

Please read very, very carefully this important warning before you register. Due to two crucial reasons that this course
1) having just 3 ECTS, so too little time, and
2) being a SECOND course on algorithms at University of Vienna,
it would be unacceptable if you do not have the mathematical maturity and the prerequisites that will be described in detail soon. We (I in class and also you outside class) will not be able to afford spending much time on the prerequisites. Just knowing the concepts or that these names exist is not enough. You must have solved plenty of problems on your own (reading the solutions does not count) and must have done several mathematical proofs already. IF you are not comfortable with the following topics, PLEASE DO NOT TAKE THIS COURSE. Remember: this is a mathematical course full of mathematical proofs. There will be a compulsory prerequisites exam in the second lecture, i.e., on 14 March 2022. IF YOU GET LESS THAN 50% IN THE PREREQUISITES EXAM, YOU WILL GET A FAIL GRADE IN THE COURSE.

Here are the detailed prerequisites so that you can start brushing up on the topics.

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 including several mathematical proofs. 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.

Don't worry, the prerequisites exam will not be very hard, and if you do indeed possess the prerequisites, you would not need to even study for it. Here is a link to the last year's prerequisites exam: https://ucloud.univie.ac.at/index.php/s/5evOVm9MiRAH2jw

This year, the format and length of the prerequisites exam may be different.

Resources for prerequisites:
You can consult your old notes, or I recommend the following.
1. Mathematics for Computer Science by Lehman, Leighton, and Meyer: https://courses.csail.mit.edu/6.042/spring18/mcs.pdf and/or course based on this book on MIT Open Courseware (OCW) Instructors: Prof. Albert R. Meyer and Prof. Adam Chlipala
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/
2. For basic algorithms analysis and discrete structures, study appropriate chapters in the following classic book:
Introduction to Algorithms By Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest
https://mitpress.mit.edu/books/introduction-algorithms-third-edition

The main aim of this course 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:
--Algorithmic strategies:
----Dynamic Programming, and
----Greedy Algorithms
--Advanced Data Structures and Algorithms:
----Network Flows
----Hashing