# 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 $\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**.)*