# Hubička 30. 6.

Hubička je neocenitelný. Během zkoušky byl velmi příjemný, byla to spíše písemná zkouška, člověk dostal zadání, řešil je a následně zavolal pana docenta na zkontrolování.

1. Popište hešování, , vysvětlete, jak se řeší kolize, zanalyzujte složitost `FIND` a `INSERT` v průměrném čase
2. Popište mergesort a analyzujte jeho složitost.
3. (Přibližné znění) Směnárna obchoduje s valutami a drží si kurz -- v matici $K$, kde v $(K)_{ij}$ je hodnota měny $j$, kterou dostaneme za jednotku měny $i$. Dá se na směňování vydělat, tj. existuje způsob, jak po nějakém nakupování valut skončit s vyšším obnosem peněz, než s kolika jsme začali (skončíme a začneme ve stejné měně)?
4. Mějme souvislý neorientovaný graf. Vymyslete algoritmus, který nám dá pořadí, v němž se dají odstraňovat vrcholy takovým způsobem, že souvislost nebude porušena
5. Bonus: příklad na sčítání Fibonacciho čísel (Zeckendorfova věta), vizte předchozí termíny.