Z minula

DFS

• DFS ve stromech
• DFS v obecných grafech
• DFS na počítání hloubky

Úlohy z minula

• Dostanete strom, najděte v něm nejdelší cestu. Pozor, cesty ve stromech mohou vést jak "svisle" (mezi předkem a potomkem) nebo „napříč“ (mezi dvěma různými větvemi).
• Zjistěte, zda zadaný neorientovaný graf je acyklický. Jak je to pro orientované grafy?

Pro dnešek

Rozděl a panuj

• MergeSort
• QuickSort

• QuickSelect

• Kolik inverzí je v zadané posloupnosti? Prvky x_i a x_j jsou v inverzi, pokud i < j a současně x_i > x_j. Nápověda: Upravte Mergesort.

• Napište funkci, která dostane seznam čísel a najde nejmenší přirozené číslo, které v něm chybí.
  1. Naivní přístup bez jakéhokoli omezení
  2. Pokud smíte pole upravovat v O(N) s O(1) paměti navíc.
  3. (BONUS) Seznam nesmíte nijak upravovat a kromě něj smíte použít pouze konstantní množství paměti.