Cvičenie z Algoritmov a dátových štruktúr 1 (NTIN060), LS 2025/26

Pondelok 12:20 ‒ 13:50, N4 (Impakt, Troja)

Poštovní sova ‒ odovzdávanie domácich úloh, prehľad získaných bodov.

Informácie

• Informácie o predmete, cvičení a pravidlách získania zápočtu sú v sove, pridajte sa do kurzu. Link aj enrollment token sú boli v PDF z prvého cvičenia. Token už je správny.
• PDF jednotlivých cvičení nájdete kliknutím na odkazy tu na stránke.
• Dobrý zdroj informácií (a tiež cvičených úloh) je Průvodce labyrintem algoritmů od Martina Mareše.

Obsah cvičení

Sem budem postupne pridávať zhrnutia a materiály z cvičení. Pred každým cvičením tu nájdete úlohy, ktoré budeme preberať.

• 16. 2. ‒ Úvodné cvičenie

  Vysvetlil som, ako bude predmet fungovať a kde nájdete podrobné informácie. Riešili sme motivačné úlohy 🥔🥕.
  Zadal som prvú domácu úlohu.
  Nápovedy k úlohám z cvičenia pošlem do sovy.

• 23. 2. ‒ Zložitosť

  Definície zložitosti, zoraďovanie funkcií podľa zložitosti.
  Tu je riešenie so správnym zoradením (niektoré dvojice sú len iné vyjadrenia tej istej funkcie, logaritmy s rozdielnymi základmi majú asymptoticky rovnakú zložitosť ‒ konštantný podiel).

• 2. 3. ‒ RAM

  Pokračovali sme úlohami v RAM modeli, dokončili sme papier z predošlého cvičenia.

• 9. 3. ‒ BFS, DFS

  Písali sme krátky test z vecí, ktoré sme doteraz preberali. Testy a staršie úlohy opravím v priebehu budúceho týždňa.
  Pokračovali sme riešením prvej polovice úloh na BFS a DFS.

• 16. 3. ‒ Mosty, artikulácie

  Dokončili sme úlohy na BFS a DFS z predošlého papiera, pokračovali sme mostami a artikuláciami.
  Vysvetlil som algoritmus na hľadanie mostov z prednášky, veľmi podobný koncept pre artikulácie som nestihol, nájdete ho v Průvodci.
  

• 23. 3. ‒ Najkratšie cesty

  Dokončili sme predošlý papier, pokračovali sme úlohami o najkratších cestách a Dijkstrovom algoritme.
  Druhý test nebude 13.4., keďže v tom čase budem preč zahlasujte prosím za termín náhradného cvičenia, detaily nájdete v sove.

• 30. 3. ‒ Minimálne kostry

• 8. 4. ‒ Binárne vyhľadávacie stromy (a AVL stromy)

  Náhradná hodina za 13.4., kedy cvičenie odpadá. 12:20 v N5.

• 20. 4. ‒ (a,b)-stromy a červeno-čierne stromy

  Budeme písať druhý test z tém od BFS po minimálne kostry.
  Na pochopenie fungovania stromových dátových štruktúr odporúčam pozrieť si vizualizácie na stránke Algovize.

• 27. 4. ‒ Trie, hešovanie, Bloomov filter

• 4. 5. ‒ Rozdeľ a panuj, master theorem

• 11. 5. ‒ Pravdepodobnostné algoritmy, dynamické programovanie

• 11. 5. ‒ Posledné cvičenie

  Budeme písať poslednú písomku a náhradné písomky za prvú a druhú. Chýbajúce body sa budú dať neskôr doplniť domácimi úlohami nad rámec limitu potrebného na zápočet.
  S ľudmi, ktorí nepotrebujú písať náhradné písomky, sa budeme venovať úlohám, ktoré sme na predošlých cvičeniach nestihli.

Off-topic

• Mnemotechnická pomôcka o spätných hranách a mostoch (presný zdroj bohužiaľ nepoznám, takže predpokladám, že je public domain).
• Tričká slovenského KSP majú v dizajne schované rôzne termíny z algoritmov a dátových štruktúr, ideálna zábavka v rámci prokrastinácie.

Kontakt

Ahojte, ja som Janči. Tykajte mi.

Ak odo mňa čokoľvek potrebujete alebo máte otázku, neváhajte sa ozvať mailom userovi janci v doméne kam.mff.cuni.cz, alebo cez mail, ktorý nájdete v SISe.

Pozor, píšem dlhé maily 😅

Back to homepage