Algorithmics 1000-2N00ALG
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
Type of course
Prerequisites
Course coordinators
Term 2023L: | Term 2024L: |
Learning outcomes
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
Assessment criteria
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.
Bibliography
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
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: