Algoritmy a dátové štruktúry

Oznam

Prednášajúci:Milan Vojvoda
Cvičiaci:Milan Vojvoda
Tomáš Fabšič
Martin Nehéz
Linky:IS Sylabus
Vyučovanie
Kategória predmetu:,

Upozornenie

—

Organizácia
Podmienky
Oznamy
Viac

Organizácia predmetu

Link na vyučovanie: Vyučovanie

Predmet je členený do nasledujúcich aktivít:

  • Prednášky: 2 hodiny týždenne podľa rozvrhu
  • Cvičenie: 2 hodiny týždenne podľa rozvrhu
  • Samostatné domáce štúdium
Konzultácie:

Konzultačné hodiny po dohode mailom

Plán semestra

  1. Greedy algoritmy.
  2. Dynamické programovanie I. (Rod cutting)
  3. Dynamické programovanie II. (Matrix chain multiplication, Optimal binary search tree)
  4. Dynamické programovanie III. (Knapsack, TSP)
  5. Dynamické programovanie IV. (Longest common substring, subsequence, edit distance)
  6. Kompresné algoritmy (Huffman, RLE, LZW)
  7. Amortizačná analýza
  8. SAT, 2-SAT, 3-SAT, k-clauses 2-SAT
  9. AVL-stromy
  10. Aproximačné algoritmy I.
  11. Aproximačné algoritmy II.

Podmienky absolvovania

Počas semestra budú 3 zadania, každé za 15 bodov. Študenti musia odovzdané zadania odprezentovať v termíne po dohode s cvičiacimi, musia byť schopní zodpovedať otázky ohľadom odovzdaného riešenia a svoje riešenie obhájiť.

Na každom cvičení bude úloha za 3 body. (Na cvičeniach sa teda dokopy bude dať získať 12*3=36 bodov.)

Na získanie zápočtu je potrebné získať zo zadaní a z cvičení dokopy aspoň 30 bodov.

Záverečná skúška bude za 30 bodov. (Dokopy sa na predmete bude teda dať získať až 111 bodov.)

Záverečné hodnotenie bude podľa platnej klasifikačnej stupnice FEI STU.

Literatúra
  • Cormen, T.H., Leiserson, C.E., Rivest, R.R., Stein, C.: Introduction to Algorithms. 2nd edition, MIT Press, 2003.
  • Sedgewick, R., Wayne, K.: Algorithms. 4th edition. Addison-Wesley, 2011.