Design and Analysis of Algorithms (DAA)
"The most valuable acquisitions in a scientific or technical education are the general-purpose mental tools which remain serviceable for a life-time." —George Forsythe
The main objective of this course is to acquaint students with algorithmic thinking and reasoning. At the end of this course, students are expected to be able to:
- Analyze the asymptotic running times of algorithms.
- Explain the major design techniques for algorithms.
- Write accurate proofs for the correctness of algorithms.
- Synthesize efficient algorithms in related engineering problems.
NB! 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.
Syllabus
- Orders and Growth
- Greedy Methods
- Divide and Conquer
- Network Flow
- Linear Programming
- Randomized Algorithms
- Approximation Algorithms
Literature
- T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, MIT Press, Boston 2009.
- 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.
Lecture
- Wednesday 12:15 - 14:00, Delta — room 1037 (Mozhgan Pourmorad Nasseri)
Due to COVID-19 restrictions, the lectures will be live-streamed.
Practice sessions (select one of the three)
- group 1. Monday 16:15 - 18:00, Delta — 1022 (Galina Pass)
- group 2. Tuesday 16:15 - 18:00, Delta — 2047 (Zahra Alijani)
- group 3. Thursday 14:15 - 16:00, Online (Eldho Thomas)
If you are not able to attend the on-site practice sessions, you can choose the online group.
Grading policy
Final grade = Homework (30%) + Midterm (30%) + Final exam (40%).
Contacts
- Lecturer:
- Mozhgan Pourmorad Nasseri, room 3041 — mozhgan@ut.ee
- Teaching assistants:
- Galina Pass — avital.pass@gmail.com
- Zahra Alijani — zahra.alijani@ut.ee
- Eldho Thomas — eldho.thomas@ut.ee
- Communication: Moodle