Algorithmics

elective courses

Algorithms and Data Structures 1000-213aASD

The course is a continuation of the course "Algorithms and data structures". The aim is to make students acquainted with the methods of constructions of efficient algorithms for various combinatorial problems.

Prerequisities: Algorithms and data structures

1. Path problems in graphs

- Bellman-Ford algorithm

- applications of matrix multiplication in path problems

- Floyd-Warshall algorithm

- Johson's algorithm

2. Network flows

- min-cut max-flow theorem,

- algorithms of Ford-Fulkerson, Edmonds-Karp, Dinic, three Indians

- min cost flow, cycle cancelling algorithm, successive shortest paths algorithm

- reductions to flow problems

3. Complexity classes: P and NP, proving NP-hardness

4. Linear Programming

- the geometry of linear programs,

- simplex algorithm

5. Approximation algorithms

- 2-approximation for vertex cover

- nonapproximability of general Travelling Salesman Problem

- Christofides algorithm for metric Travelling Salesman Problem

- applications of linear programming in approximation

6. Parameterized algorithms

- FPT and XP classes

- branching algorithms

- kernelization: linear kernel for vertex cover

- treewidth and pathwidth

- dynamic programming on tree decpompositions

7. Randomized algorithms

- Monte Carlo and Las Vegas algorithms

- Monte-Carlo algorithm for the maximum matching problem

- sublinear algorithms

1. Introduction to Algorithms, T. H. Cormen, C. E. Leiserson, C. Stein, MIT, 2001.

2. Approximation Algorithms, V. V. Vazirani, Springer 2003.

3. Probability and Computing, M. Mitzenmacher, E. Upfal, Cambridge University Press 2006.

4. The Design and Analysis of Algorithms, D. C. Kozen, Springer 1991.

5. Parameterized Algorithms, Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh, Springer 2015

knowledge

1. Knows the most important combinatorial optimization problems

2. Knows the concepts of complexity classes P and NP, the concept of NP-hard problems

3. Knows the most efficient algorithms for combinatorial optimization problems within the class P (path and flow problems, linear programming)

4. Knows the most important NP-hard problems.

5. Is familiar with the concept of approximation algorithm and knows examples of such algorithms, both using combinatorial approach and based on the linear programming theory

6. Is familiar with the concept of parameterized algorithm and examples of various parameterizations. Knows the notion of kernalization.

7. Knows the notion of treewidth and applies the technique of dynamic programming over tree decomposition

8. Knows examples of randomized Monte-Carlo and Las-Vegas algorithms

Skills:

1. reduces new problems to the well-known flow and path problems, or to linear programming

2. proves NP-hardness

3. is able to design approximation algorithms and analyze the quality of approximation

4. is able to identify natural parametrizations of problems and applies techniques like branching, kernelization and dynamic programming over tree decomposition

5. applies the basic techniques of randomization (randomized rounding, Zippel-Schwartz lemma, color coding) and derandomizes algorithms with the method conditional expected value

After each lecture, there will be a short quiz available in Moodle. 75% of quiz points is required to get a passing grade in the first exam session.

Moreover, during the semester there will be 3-4 homeworks, each consisting of 1-2 problems. The exam will be a 90-minutes test, checking knowledge and its creative use. The final grade depends on the scores from homeworks and the exam.

In the case of completing the course by a doctoral student, the student will read a selected recent research article and a chat with a lecturer about the article will be a part of the exam.

To be admitted to the early exam ("zerówka"), one needs more than 90% of points from quizzes and more than 90% of points from homeworks.