Teoretické otázky:
- Statické slovníky - ukázat FKS a HMP, přičemž stačilo popsat kvadratické univerzum á la trie a jak funguje redukce do lineárního s randomizovanou konstrukci (důkaz lemma nemusel být vůbec podrobný, stačilo bez derandomizace).
- Dynamizace - nadefinovat rozložitelný problém a obecnou dynamizaci.
- Reprezentace řetězců nad obecnou abecedou s redundancí O(log n) - mixérové lemma + stromovitá struktura mixérů.
- Dynamizovat intervalové stromy - buď použít BB-alpha stromy a ukázat, že amortizovaně vyjdou o log n hůř nebo (to jsem dělal) šlo použít konstrukci řadou exponenciálně rostoucích statických struktur se sléváním (pozor, není třeba třídit) a škrtat mazané prvky. Na jedničku stačilo ukázat jak se řeší fractional cascading (verze pro 2D), a že to funguje i pro vylepšené intervalové stromy s efektivní 3D konstrukcí - protože se buňková reprezentace na dně nedá snadno upravovat, find může vycházet špatně v závislosti na počtu vyškrtaných prvků, ale průměrně vyjde dobře, protože se řada průběžně přebudovává když se prvků vyškrtá hodně.
- Datová struktura pro udržování inkrementální kostry - udržuje kostru a přidává hrany (pomocí Link-Cut stromů).
- Pro X podmnožinu U odpovídat na rank(x) a unrank(i) (i-tý prvek X) v o(log n) - stačilo staticky přes van Emde Boasovi stromy nebo Fusion Trees.