Design and Analysis of Algorithms
Instructor: Vitaly Skachek, office hours: Paabel 224, Monday 10:15 - 12:15, or by appointment
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
Language of instruction: English
Final exam and retake of the midterm
- Final exam
Final exam 13 January 2020, Solutions (updated)
The final exam in Design and Analysis of Algorithms will take place on January 13, 2020. It will start at 14:15, and its duration is 1 hour 40 minutes. It will take place in room J.Liivi 2 - 405.
Any printed and hand-written materials can be used in the final exam (as well as in the midterm retake). No electronic devices are allowed (i.e. no phones, no laptops, no smart watches).
- Midterm retake
The retake of the midterm exam will also take place on January 13, 2020. We will have a ~20 minute break after the main exam, and then we will start the retake. Please be there by 16:20 the latest. The duration is 1 hour and 40 minutes. The retake will take place in room J.Liivi 2 - 405.
A student who is not happy with his midterm exam grade, can retake the midterm. In that case, the latest grade will be used.
- Final exam -- old information
Final exam 16 December 2019, Solutions
There are two dates for the final exam: December 16, 2019, and January 13, 2020. Both exams start at 14:15, and their duration is 1 hour 40 minutes. You can choose any out of these two dates. Please register for the selected date in ÕIS.
The exam on December 16th will take place in rooms J.Liivi 2-122 and -202 (room 611 will not be used). The exam on January 13 will take place in room J.Liivi 2-405.
Any printed and hand-written materials can be used in the final exam (as well as in the midterm retake). No electronic devices are allowed (i.e. no phones, no laptops, no smart watches).
- Midterm retake - old information
The retake of the midterm will be on the same dates as the final exam (December 16, 2019, and January 13, 2020). We will have a 15-20 minute break after the main exam, and then we will start the retake. Please be there by 16:20. The duration is 1 hour and 40 minutes.
On December 16, the retake will take place in room J.Liivi 2-202. On January 13, the retake will take place in room J.Liivi 2-405.
Any student who is not happy with his/her midterm grade, can retake the midterm exam. In that case, the latest grade will be used.
Midterm exam
Midterm exam 13 January 2020
Midterm exam 16 December 2019
Midterm exam 11 November 2019, Solutions
A midterm exam will take place on Monday, November 11th, between 14:15-15:55 (during the lecture time). The total duration of the exam is 1 hour and 40 minutes. The exam will take place in rooms J. Liivi 2-122, -224, and -512.
Any written and printed material is allowed in the exam. No electronic devices are allowed (no phones, computers, tablets, calculators, etc.)
Due to room constraints, please register to one of the exam rooms (122, 224 or 512) as soon as possible. If you cannot register for some reason -- please notify Vitaly without delay.
Announcements
Old announcements:
- Change of room due to the Institute Day on Thursday, October 3rd: the practice session will take place in J. Liivi 2, room 207.
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) 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.