Oznamy

• Pripomíname, že na skúšku treba vedieť aj učivo, ktoré neprednášal prof. Ďuriš
• Najbližšie cvičenia sú 9.5. (pondelok) a 11.5. (streda).
• Najbližšie cvičenia sú 25.4. (pondelok) a 27.4. (streda).
• V DÚ4 sa vyskytla drobná chyba, väčšina riešiteľov a tiež my, sme zle riešili vstupy, kde n bolo medzi p a q. Vaše riešenia boli pretestované. Stiahnite si prosím nové zadanie, kde sú pridané dva ukážkové vstupy a skontrolujte si, či na ne váš program odpovedá správne. Ospravedlňujeme sa za prípadné nepríjemnosti.
• V DÚ3 to možno nie je na prvý pohľad zjavné, ale medzi dvoma križovatkami môže viesť aj viac ciest (násobné hrany) a tiež môže viesť cesta z jednej križovatky do tej istej križovatky (slučka). Ak máte pocit, že by toto mohlo robiť vášmu algoritmu problém, skúste ho opraviť.
• 11.4. a 13.4. budú tiež cvičenia.
• Cvičenie cez Veľkonočný pondelok sa posúva o týždeň neskôr. Inak povedané, pondelková skupina bude mať najbližšie cvičenie 4. apríla a stredňajšia skupina 30. marca.
• Prvý týždeň (od 15.2.) nebudú cvičenia, pretože jeden cvičiaci je vo Švajčiarsku a druhý je chorý. Stretneme sa na druhej prednáške (22.2.)

Organizácia predmetu

Prednáška: pondelok 10:40 - 12:55, miestnosť F1

Cvičenia 1: pondelok 14:00 - 15:30, učebňa M-XII
Cvičenia sa konajú raz za dva týždne.
Michal Anderle (zaba zavináč ksp bodka sk) miestnosť T2

Cvičenia 2: streda 16:30 - 18:00, učebňa F1-108
Cvičenia sa konajú raz za dva týždne.
Ján Hozza (janoh zavináč ksp bodka sk) miestnosť T2

Bližšie informácie, prehľad prebraného učiva, domáce úlohy a ďalšie informácie budú postupne pribúdať.

Domáce úlohy

Pre úspešné absolvovanie predmetu je potrebné spraviť aspoň 5 zo 7 domácich úloh, každú do stanoveného termínu. Posledná domáca úloha sa bude dať odovzdávať aj na začiatku skúškového obdobia. Na skúšku však môžete ísť až po vyriešení aspoň piatich domácich úloh. Domáce úlohy sa odovzdávajú na stránke foja.dcs.fmph.uniba.sk/eval/

Domáca úloha 1: (PDF) (Odovzdajte do 18.3.2016)
Riešenie domácej úlohy 1: (PDF)
Domáca úloha 2: (PDF) (Odovzdajte do 1.4.2016)
Riešenie domácej úlohy 2: (PDF)
Domáca úloha 3: (PDF) (Odovzdajte do 15.4.2016)
Riešenie domácej úlohy 3: (PDF)
Domáca úloha 4: (PDF) (Odovzdajte do 22.4.2016)
Riešenie domácej úlohy 4: (PDF)
Domáca úloha 5: (PDF) (Odovzdajte do 6.5.2016)
Riešenie domácej úlohy 5: (PDF)
Domáca úloha 6: (PDF) (Odovzdajte do pondelka 23.5.2016)
Riešenie domácej úlohy 6: (PDF)
Domáca úloha 7: (PDF) (Odovzdajte do 27.5.2016)
Riešenie domácej úlohy 7: (PDF)
Bonusová domáca úloha: (PDF) (Odovzdajte do 27.5.2016)

Poznámky k cvičeniam

Cvičenie 1: (PDF)
Cvičenie 2: (PDF)
Cvičenie 3: (PDF)
Cvičenie 4: (PDF)
Cvičenie 5: (PDF)
Cvičenie 6: (PDF)

Materiály k prednáškam

Hlavné skriptá z predmetu (k tomu, čo prednášal prof. Ďuriš) (PDF).
Invervalové stromy - odporúčam si prečítať tento článok. Je tam pomerne pekne popisané to čo som robil na prednáške. Časom bude tento odkaz nahradený mojím spísaným materiálom. Na skúške by ste mali vedieť ako funguje dátová štruktúra intervalový strom (segment tree), akú časovú zložitosť majú jej operácie a ako sa robí update intervalu pomocou lazy propagácie.
Pokročilé využitie DFS (PDF)
Modulárna matematika (PDF)
Geometria, obahy, konvexný obal (PDF)

Preberané učivo

(Sivou sú predbežné plány.)

• 15. február: Úvodná prednáška, Median of five (prof. Ďuriš)
• 22. február: Triedenie, počet porovnaní (prof. Ďuriš)
• 29. február: Intervalové stromy (Mišo)
• 7. marec: 2-3 stromy, Union-find set (prof. Ďuriš)
• 14. marec: Dijkstrov algoritmus (najkratšia cesta), Kruskalov algoritmus (najlacnejšia kostra) (prof. Ďuriš)
• 21. marec: Floyd-Warshalov algoritmus, Pokročlé využitie DFS (Mišo)
• 4. apríl: Modulárna matematika (Mišo)
• 11. apríl: Rozdeľuj a panuj (prof. Ďuriš)
• 18. apríl: Dynamické programovanie (prof. Ďuriš)
• 25. apríl: Geometria (ako k nej pristupovať, užitočné triky), konvexný obal (Jano)
• 2. máj: Triedy P a NP -- úvod (prof. Ďuriš)
• 9. máj: Aproximačné algoritmy -- úvod (prof. Ďuriš)
• 16. máj: prednáška nebude