# Zkouška 30.5.2022 09:30 Jan Hric

<{ForumPost(poster="Xerneis", timestamp=2022-05-30 16:04:32)}>
1.  
a) Formulujte Master Theorem.  
b) Pomocí Master Theoremu odhadněte složitost v závislosti na parametru a:  
T(n) = aT(n/3) + O(n^2)  
  
2.  
a) Definujte univerzální množinu hashovacích funkcí.  
b) Popište konstrukci univerzální množiny hashovacích funkcí.  
  
3.  
Máte algoritmus na hledání minimální kostry grafu:  
-> Vstup: souvislý G s ohodnocenými hranami  
  
-> Dokud jsou v G cykly:  
-> Z nějakého cyklu smažete jeho nejdražší hranu  
  
-> Výstup: zbývající hrany  
a) Dokažte, že výstupem je minimální kostra.  
b) Navrhněte implementaci algoritmu a odvoďte časovou složitost.
<{/ForumPost}>