Algoritmy a datové strukury I (NTIN060)

Konzultace po dohodě emailem (nejlépe ve středu nebo pátek na MS, 2. patro). Do subjektu emailů pište "ADS2026".

Odpřednesená látka

17. února: Co to je algoritmus. Definice výpočetního modelu RAM. Časová a prostorová složitost. O notace. Video
24. února: Prohledávání grafů do hloubky a klasifikace hran. Aplikace pro hledání mostů Video
3. března: Aplikace DFS, topologické třídění, topologická indukce, silně souvislé komponenty Video
10. března: Dokončení silně souvislých komponent. Nejkratší cesty: Disktrův algoritmus Video z technických důvodů bohužel chybí. Video Martina Mareše z loňka (na konci jsou KSS) Video Martina Mareše z loňka (na konci jsou KSS)
17. března: Nekratší cesty II: Důkaz správnosti a časová složitost Dijsktrova algoritmu. Bellmanův-Fordův algoritmus. Floydův-Warshallův algoritmus. Video z technických důvodů bohužel chybí. Video Martina Mareše z loňka
24. března: Minimální kostry Video
31. března: Úvod do datových struktur pro množiny a uspořádané množiny. Binární vyhledávací stromy Video Martina Mareše z loňka
7. dubna: Insert a delete v AVL stromu
14. dubna: (a,b)-stromy (insert, delete), RB stromy (jen převod z (2,4)-stromu), krátký úvod do Hašován (separované řetezce a otevřená adresace). Pokračování bue po třídicích algoritmech
21. dubna: Rozděl a panuj (merge sort, Karatsuba, kuchařková věta)