Design and Analysis of Algorithms
Instructor: Vitaly Skachek, Wed 10.30-11.30, or by appointment
Teaching assistants: Sander Mikelsaar, Karan Khathuria, Javier Gil Vidal
Lecture (Delta bld. room 1021): Wednesday 12.15 - 13.45 (both in-person and online)
Practice :
Monday 12.15 - 13.45 (both in-person and online): Delta room 2048
Thursday 14.15 - 15.45 (in-person): Delta room 2010
Friday 12.15 - 13.45 (in-person): Delta room 2010
Language of instruction: English
Main mode of communications: Moodle
Announcements
- The retake of the final exam in MTAT.03.286 Design and Analysis of Algorithms will take place on Wednesday, January 25th, between 12:15-13:55. The total duration of the exam is 1 hour and 40 minutes. The exam will take place in room 1022 in Delta.
Any written and printed materials are allowed in both exams (for example, books, lecture notes, your hand-written notes, etc.). No electronic devices are allowed (no phones, computers, tablets, smart watches, etc.) Please register for the exam in ÕIS or in ÕIS2. If you cannot register -- please email Vitaly.
Old announcements
- The second final exam in MTAT.03.286 Design and Analysis of Algorithms will take place on Wednesday, January 18th, between 12:15-13:55. The total duration of the exam is 1 hour and 40 minutes. The exam will take place in room 1019 in Delta.
The retake of the midterm exam will take place on January 18th between 14:15-15:55. The retake of the midterm will take place in room 1022 in Delta.
Any written and printed materials are allowed in both exams (for example, books, lecture notes, your hand-written notes, etc.). No electronic devices are allowed (no phones, computers, tablets, smart watches, etc.)
The final exam will focus mainly on the topics of the last five weeks - linear programming and approximation algorithms. However, it can also touch some of the previously studied topics. The format will be similar to the first final exam.
Some examples of previous year midterm exams are available from the "courses" webpage under the link https://courses.cs.ut.ee/2022/designalg/fall/Main/Homeworks . - The final exam will take place on December 14th, between 12:15-13:55 (during the lecture time). The total duration of the exam is 1 hour and 40 minutes. The exam will take place in room 18-1018 in Delta -- please note that it is a room different from the regular lecture room!
The retake of the midterm exam will take place on December 14th between 14:15-15:55. The retake of the midterm will take place in room 18-1022 in Delta -- it is a small room in the very beginning of the corridor.
Any written and printed materials are allowed in both exams (for example, books, lecture notes, your hand-written notes, etc.). No electronic devices are allowed (no phones, computers, tablets, smart watches, etc.) - The practice session on Thursday, December 1st, will take place as usual between 14:15-15:45, in room 2010.
- The midterm exam will take place on Wednesday, November 9th, between 12:15-13:55 (during the lecture time). The total duration of the exam is 1 hour and 40 minutes. The exam will take place in room 18-1021 in Delta (lecture room).
Any written and printed material is allowed in the exam (for example, books, lecture notes, your hand-written notes, etc.). No electronic devices are allowed (no phones, computers, tablets, smart watches, etc.) - There will be no class on Monday, August 29th. The first class will be on Wednesday, August 31st.
Literature
- 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.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, MIT Press, Boston 2009.
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) (or equivalent courses) 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 homework assignments, the midterm and final exam. The final grade will be based on the grade of homework assignments (30%), of the midterm (30%), and of the final exam (40%). The homework assignments will mainly contain questions of design and of analysis of algorithms, and typically will not contain programming tasks.
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.