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.