## Design and Analysis of Algorithms

Instructor: Vitaly Skachek

Teaching assistants: Behzad Abdolmaleki, Mozhgan Pourmoradnasseri

Lecture: Mon. 14.15 - 16.00, J. Liivi 2 - 122

Practice: Mon. 16.15 - 18.00, Paabel 219, or Tue. 16.15 - 18.00, Paabel 218, or Thur. 14.15 - 16.00, Paabel 220

Office hours: to be announced

Language: English

Contact: Vitaly Skachek

### Literature

- S. Dasgupta, C. Papadimitriou and U. Vazirani,
, McGraw Hill, New York 2008.*Algorithms* - V.V. Vazirani,
, Springer-Verlag, Berlin 2003.*Approximation Algorithms* - S. Even,
, 2nd edition, Cambridge University Press, New York 2012.*Graph Algorithms* - T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein,
, MIT Press, Boston 2009.*Introduction to Algorithms*

### Course description

This course focuses on design and analysis of advanced algorithms in computer science. It is advised to take **Algorithms and Data Structures** (MTAT.03.133) and **Advanced Algorithmics** (MTAT.03.238) before you take this course or in parallel. In comparison to "Advanced Algorithmics", this course will emphasize the analysis of the algorithms (proof of correctness, complexity analysis), and will **not** focus on implementations and programming.

### Grading policy

There will be six homeworks, the midterm and final exam. The final grade will be based on the grade of homeworks (30%), of the midterm (30%), and of the final exam (40%). The homeworks will mainly contain questions of design and of analysis of algorithms, and typically will **not** contain programming tasks.

### Exam dates

- Midterm: November 11 at 14:15-16:00 (during the lecture time).
- Final exam: December 16 at 14:15-16:15 or January 13 at 14:15-16:15.

### Syllabus

The following is a preliminary list of topics (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.
- Knapsack problem.
- Linear programming in approximation algorithms.
- Linear programming approach to set cover problem.
- Primal-dual approach.