# Hric 13.6.2019

<{ForumPost(poster="Elen Eresiel", timestamp=2019-06-14 12:58:23)}>
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ů.
<{/ForumPost}>