Zkouška 14. 1. 2025 10:00 Martin Mareš

Každému zadal vlastní téma, jinak průběh zkoušky jako vždy.

  1. Fredman-Tarjan: chtěl napsat algoritmus (zkratkovitě jsem napsal i Jarníkův) a dokázat časovou složitost (včetně lemmatu o jedné fázi v O(m)\mathcal O(m))

  2. LCA: chtěl vědět co to je; lemma o převodu na RMQ + důkaz; co je RMQ; co je RMQ±1

(Padla dnes ještě otázka na multiple přihrádky.)