1a. Popište rozhodovací strom u třídích algoritmů a dokažte že složitost třídicích algoritmů založených na porovnávání prvků je THETA(Nlog N)
1b. Přihrádkové třídění + jeho složitost
2a. Popiště Floyd-Warshallův algoritmus včetně rekonstrukce cesty
2b. Vyslovte invariant FW algoritmu a na pomocí něj zdůvodněte správnost
3a. Dokažte nebo vyvraťte (už nevím přesně, f je elementem něčeho & g je elementem něčeho => ...)
3b. Dokažte substituční metodou že T(n)=2T(n/3)+2T(n/6)+bn je T(n) = THETA(Nlog N)
Na ústní jsem dostala očekávaná doba vyhledávání pro hešování se zřetězením při úspěchu a neúspěchu, pak se mě ještě ptal na dvojité hešování. Další otázky byly na topologické uspořádání, Primův algoritmus, randomizovaný quicksort.