Algoritmy a dátové štruktúry

Oznam

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

3 zadania po 25 bodov v priebehu semestra, riešené doma, pričom š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ť.

Úlohy na cvičeniach v priebehu semestra v súčte za 25 bodov.

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