Hubička 31. 5.

Ahoj,zkouška probíhala ve velmi klidné a příjemné atmosféře.

1. Popiště hešování, kolize, metodu find a insert. Uveďte časovou složitost (10b)

2. Popište merge sort. Odvoďte časovou složitost (5b)

3. Směnárna obchoduje s n měnami (měna číslo 1 je koruna) a vyhlašuje matici kurzů K. Kurz Kij říká, kolik za jednu jednotku i-té měny dostaneme jednotek j-té měny. Vymyslete algoritmus, který zjistí, zda existuje posloupnost směn, která začne s jednou korunou a skončí s více korunami.

4. Souvislý neorientovaný graf, v jakém pořadí musí být odebírány vrcholy, abychom je odebrali všechny a graf zůstal až do konce souvislý (5b)

5 bonusová úloha) Zadání si nepamatuji přesně, prosím kdyžtak někoho o doplnění. V zásadě byla nějak definovaná soustava pro hezká Fibonacciho čísla a měla se provést efektivní implementace jejich sečtení.