Hric 13.6.2019

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Elen Eresiel
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 25. 1. 2019 18:20
Typ studia: Informatika Bc.

Hric 13.6.2019

Příspěvek od Elen Eresiel »

1. Dokažte substituční metodou že složitost F(n) je O(n^2)
F(n) = 4T(n/2) + 2T(n/2) + 5n

2. Popište Floyd-Warshallův algoritmus ( včetně invariantu ) a odůvodněte jeho korektnost

3. Popište červeno-černé stromy a oduvodněte proč mají logaritmickou hloubku

4. 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ů.
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“