Arvutiteaduse instituut
  1. Kursused
  2. 2020/21 sügis
  3. Algoritmide kavandamine ja analüüs (MTAT.03.286)
EN
Logi sisse

Algoritmide kavandamine ja analüüs 2020/21 sügis

  • Home
  • Lectures
  • Homework
  • Exam
  • Links

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:

  1. Analyze the asymptotic running times of algorithms.
  2. Explain the major design techniques for algorithms.
  3. Write accurate proofs for the correctness of algorithms.
  4. 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 PourmoradNasseri)

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 PourmoradNasseri, 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
  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Courses’i keskkonna kasutustingimused