Tak na tomto terminu jsme byli 4.
Zadani:
a)definice B-stromu
b) INSERT v cerveno-cernem strome (dobre, ze jsem si vzal cervenou tuzku :wink: )a) Substitucni metodou dokazat: T(n) = 2T(n/4)+T(n/2)+5n splnuje fce O( n * log(n) )
b) algoritmus rychleho nasobeni velkych cisel, tj. aby byl z o(n<sup>2</sup>) - to je ten s O(n^log<sub>2</sub>3) (tzv. Karacubuv); a proc je rychlejsi (asi stacilo napsat rovnici a pouzit Master theorem)a) Dijkstra - popis + kde se uplatnuje interface datovych struktur
b) dukaz Dijkstry
casu bylo 75min;
Hric byl velmi prijemny (jak pri zkouseni, tak pri bodovani);
vsem good luck
P.S.: na ustni padaly otazky: quicksort (proc a jak se randomizuje - ocekavana slozitost random.), hashovani, Floyd-Warshall; plus se ptal na to, co clovek mel v pisemne casti spatne