Design and Analysis of Algorithms 2023/24 fall

Design and Analysis of Algorithms

Instructor: Vitaly Skachek, office hours Wed 14:00-15:00, or by appointment
Teaching assistants: Sander Mikelsaar, Kristo Valjako, Daniel Würsch
Lecture: Wednesday 10:15 - 11:45, Delta 1019
Practice :
Friday 10:15 - 11:45, Delta 2010 -- Daniel
Monday 12:15 - 13:45, Delta 2010 -- Kristo
Monday 14:15 - 15:45, Delta 1022 -- Sander
Language of instruction: English
Main mode of communications: Moodle

Announcements

• The second final exam in MTAT.03.286 Design and Analysis of Algorithms will take place on Wednesday, January 17th, between 10:15-11:55 (during the lecture time). The total duration of the exam is 1 hour and 40 minutes. The exam will take place in room 1019 in Delta (the regular lecture room).
• The second retake of the midterm exam will take place on Wednesday between 12:15-13:55. The retake of the midterm will take place in room 2045 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.)

Old announcements

• The midterm exam in MTAT.03.286 Design and Analysis of Algorithms will take place on Wednesday, November 8th, between 10:15-11: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-1019 in Delta (the 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.) The topics for the exam - everything from the first lecture and up to probabilistic algorithms (including).
• There will be no classes on Monday, September 4th. The first lecture takes place on Wednesday, September 6th.
• Some examples of previous year exams are available from the "courses" webpage under the link https://courses.cs.ut.ee/2023/designalg/fall/Main/Homeworks .

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.

Important dates

Midterm exam: November 8th, 10:15-11:55
Final exam 1: December 20th, 10:15-11:55
Retake 1 of the midterm: December 20th, 12:15-13:55
Final exam 2: January 17th, 10:15-11:55
Retake 2 of the midterm: January 17th, 12:15-13:55
Retake of the final exam: January 24th, 10:15-11:55

Syllabus

The following is a preliminary list of topics (some deviations from this list are possible):

Part 1: Deterministic algorithms

• Algorithms for finding a minimum spanning tree in a graph.
• Flow networks. Efficient algorithm for finding a maximum flow in a network.
• Randomized algorithms.
• Fast Fourier transform. Algorithm for fast multiplication of polynomials.
• 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.