Algoritmy a dátové štruktúry

Oznam

Prednášajúci:Milan Vojvoda
Cvičiaci:Milan Vojvoda
Kategória predmetu:,

Upozornenie

Organizácia
Podmienky
Oznamy
Viac

Organizácia predmetu

Link na vyučovanie: bude doplnený

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.

 

„Ostré“ testovacie vstupy pre Veľké zadanie 1

Podmienky absolvovania (2024/2025)

Bodovanie.

  • Dve veľké zadania počas semestra, každé za 14 bodov (spolu 28 bodov).
  • Malé zadania na 8 cvičeniach, max. po 4 body (1 za účasť + 3 za správne riešenie) na každom takomto cvičení (spolu 8*[1+3] = 32 bodov)
  • Záverečná skúška bude za 40 bodov.

(2+2=4 týždne sú rezervované na preberanie 2 veľkých zadaní)

Pri ospravedlnenej neúčasti je možné odovzdať zadanie neskôr.

Študenti musia odovzdané zadania odprezentovať v termíne po dohode s cvičiacimi a musia byť schopní zodpovedať otázky ohľadom odovzdaného riešenia a svoje riešenie obhájiť.

Podmienka účasti na skúške:

  • počas semestra je potrebné získať aspoň 30 bodov.

Záverečné hodnotenie bude v súlade s platnou klasifikačnou stupnicou 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.