Design and Analysis of Algorithms
Instructor: Vitaly Skachek, office hours: Wednesday 15:00-16:30, or by appointment
Teaching assistants: Thamara Luup Carvalho, Karan Khathuria, Tejas Anil Shah
Lecture (Delta bld. room 1019): Wednesday 12.15 - 13.45 (both in-person and online)
Practice (Delta bld. room 2047): Monday 16.15 - 17.45 (both in-person and online)
Consultation: Thursday 14.15 - 15.15 (online via Moodle)
Language of instruction: English
Main mode of communications: Moodle
Announcements
- The first final exam will take place on Wednesday, December 15th, at 12:15-13:55. The exam will take place in Moodle. The access is via the course environment in Moodle.
- The retake of the midterm exam will take place on Wednesday, December 15th, at 14:15-15:55. The exam will take place in Moodle. The access is via the course environment in Moodle.
Old Announcements
- Due to very low attendance of the practice sessions in the course, we reorganize them as following, starting from this week.
- The practice sessions on Thursday 14:15-15:45 and Friday 12:15-13:45 will be discontinued.
- The practice session on Monday 16:15-17:45, which has the biggest audience so far, will continue as before. It will also be streamed live via the Moodle (instead of the practice session on Thursday), and it will also be video-recorded. The video recordings will be available in Moodle, as before.
- During the practice session time slot on Thursday, specifically between 14:15-15:15, we will have an online consultation. You can access the consultation session via a dedicated link in Moodle, and to ask questions about the study materials and homework exercises.
- The lectures will continue as before, Wednesday 12:15-13:45, both in-class and online.
- The first lecture will take place on Wednesday, September 1st. There is no class on Monday, August 30th.
- Due to COVID-19 situation, the course follows the corresponding university guidelines. The classes will be held in the hybrid mode. As of now, there will be face-to-face meetings for both lectures and practice classes. The lectures and practice classes on Thursday will also be streamed online.
Final exam and retake of the midterm
There are two dates for the final exam: December 15th and January 19th, both at 12:15-13:55. You can choose any out of these two dates. Please register for the selected date in ÕIS.
Midterm exam
The midterm exam will take place on November 10th at 12:15-13:55.
The exam will be held online using Moodle.
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.