Design and Analysis of Algorithms
Instructor: Kristo Väljako
Teaching assistants: Juhan Oskar Hennoste, Aleksei Ganyukov, Andres Alumets
Lecture: Tuesday 10:15 - 11:45, Delta 1021
Practice :
Friday 10:15 - 11:45, Delta 2010 -- Andres
Monday 12:15 - 13:45, Delta 2048 -- Juhan Oskar
Monday 14:15 - 15:45, Delta 1019 -- Aleksei
Language of instruction: English
Main mode of communications: Moodle
Announcements
- There will be no tutorial on Friday, September 5th. Students of group 3 may go to other groups' tutorials, which will be held on Monday, September 8th. Also, the material of the first tutorial will be covered in the lecture on Tuesday, September 2nd.
- There will be no classes on Monday, September 1st. The first lecture takes place on Tuesday, September 2nd.
- 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.)
- Some examples of previous year exams are available from the "courses" webpage under the link https://courses.cs.ut.ee/2024/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 4th, 10:15 - 11:55, Delta 1021
Final exam 1: December 16th, 10:15 - 11:55, Delta 1021
Retake 1 of the midterm: December 16th, 12:15 - 13:55, Delta ?
Final exam 2: ?
Retake 2 of the midterm: ?
Retake of the final exam: ?
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.