Dokažte substituční metodou že složitost F(n) je O(n^2)
F(n) = 4T(n/2) + 2T(n/2) + 5nPopište Floyd-Warshallův algoritmus ( včetně invariantu ) a odůvodněte jeho korektnost
Popište červeno-černé stromy a oduvodněte proč mají logaritmickou hloubku
Vymyslete algoritmus který dostane 2 sestříděné posloupnosti délky n a v o(n) ( malé o ) najde jejich společný medián
( myšleno median posloupnosti délky 2n která by vznikla ze zadaných posloupností ). Posloupnosti mate uložené v poli a prvek na indexu získáte v konstantním čase.
každý úkol za 5 bodů
Na ústní mi dal Hashování a chtěl odhad neúspěšného vyhledávání při hashování s řetězením.
Při odevzdávání testu vám určí čas kdy máte přijít na ústní a až tam se dozvíte, jestli jste vůbec splnili dolní hranici 13/20 bodů.