Advanced Methods in Algorithms
Instructor: Vitaly Skachek
Lecture: Tue. 14:15 - 16:00, J. Liivi 2-611
Practice: Thu. 10:15-12:00, J. Liivi 2-512
Office hours: Tue. 10:00-12:00, J. Liivi 2-216 (or by appointment)
Contact: Vitaly Skachek
- Thursday, January 16th, 11:15-13:15, room J. Liivi 2-405.
- Printed and hand-written materials are allowed. No electronic tools are allowed (no laptop computers, ipads, mobile phones, calculators).
- Final exam
There will be no lecture on Tuesday, November 12th!
- T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, MIT Press, Boston 2009.
- S. Dasgupta, C. Papadimitriou and U. Vazirani, Algorithms, McGraw Hill, New York 2008.
- V.V. Vazirani, Approximation Algorithms, Springer-Verlag, Berlin 2003.
- S. Even, Graph Algorithms, 2nd edition, Cambridge University Press, New York 2012.
This course focuses on design and analysis of advanced algorithms in computer science. It is strongly advised to take Algorithms and Data Structures (MTAT.03.133) and Advanced Algorithmics (MTAT.03.238) before you take this course. In comparison to "Advanced Algorithmics", this course will emphasize more the analysis of the algorithms (proof of correctness, complexity analysis), and will not focus on implementations and programming.
There will be about five-six homeworks and the final exam. The final grade will be based on the grade of homeworks (50%) and of the final exam (50%). The homeworks will mainly contain questions of design and of analysis of algorithms, and typically will not contain programming tasks.
The following is a preliminary list of topics (since the course is taught for the first time, some deviations from this list are possible):
Part 1: Deterministic algorithms
- Fast Fourier transform. Algorithm for fast multiplication of polynomials.
- Algorithms for finding a minimum spanning tree in a graph.
- Flow networks. Efficient algorithm for finding a maximum flow in a network.
- Finding maximum flow in 0-1 network.
- Finding a minimum cost flow. Finding a minimum cost matching in a bipartite graph.
- Linear programming. Feasible solution. Primal and dual problem.
Part 2: Approximation algorithms
- Approximation algorithm for set cover problem.
- Travelling salesman problem.
- Minimum feedback set problem.
- Knapsack problem.
- Linear programming in approximation algorithms.
- Linear programming approach to set cover problem.
- Primal-dual approach.