Cvičenia: 11. týždeň

Ciele cvičení:

• poznať a vedieť implementovať algoritmy na nájdenie najlacnejšej kostry
• vedieť, čo sú to greedy algoritmy
• vedieť argumentovať, že greedy algoritmus vypočíta korektné riešenie

Najlacnejšia kostra

Implementujte Primov (a/alebo) Kruskalov algoritmus

• nemusí ísť o tak efektívnu implementáciu, ako bola prezentovaná na prednáške (t.j. s prioritnou frontou a Union/Find údajovou štruktúrou)

Algoritmy si môžete precvičiť pri riešení úlohy z ŠVK 2012:

• http://palma.strom.sk/SVK2012/C/

Rozdiskutujte formálny dôkaz korektnosti Primovho (a/alebo) Kruskalovho algoritmu.

Greedy algoritmy

• Festivalové leto I aplikovaním greedy stratégie podľa návodu na riešenie 7. sady zadaní
  • Formálne dokážte, že použitá greedy stratégia vedie ku optimálnemu riešeniu (nápoveda: http://en.wikipedia.org/wiki/Activity_selection_problem)
• Vyriešte úlohy 1-3 z cvičení (Exercises): http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/04-greedy.pdf
  • Ak sa rozhodnete pre greedy stratégiu, nezabudnite dokázať, že je korektná.
  • Pokúste sa vyriešiť aspoň jednu z úloh 1 a 2.