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

Algoritmide kavandamine ja analüüs 2018/19 sügis

  • Home
  • Lectures
  • Homeworks
  • Links

Design and Analysis of Algorithms

Instructor: Vitaly Skachek
Teaching assistants: Oliver-Matis Lill, Eldho K. Thomas, Behzad Abdolmaleki
Lecture: Wed. 12.15 - 14.00, J. Liivi 2 - 404
Practice: Mon. 16.15 - 18.00, Paabel 220 or Tue. 16.15 - 18.00, Paabel 219 or Wed. 10.15 - 12.00, Paabel 220
There will be no practice classes during the week September 3-9. The lecture on September 5 takes place as scheduled.
Office hours: to be announced
Language: English
Contact: Vitaly Skachek

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 and the final exam. The final grade will be based on the grade of homeworks (60%) 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.

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.
  • 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