# Zkouska - Hric 16.6. 2009

<{ForumPost(poster="Gorak", timestamp=2009-06-16 12:46:14)}>
Tak na tomto terminu jsme byli 4.  
Zadani:  
1) a)definice B-stromu  
    b) INSERT v cerveno-cernem strome (dobre, ze jsem si vzal cervenou tuzku  :wink: )  
2) a) Substitucni metodou dokazat: T(n) = 2*T(n/4)+T(n/2)+5*n 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)  
3) 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
<{/ForumPost}>

<{ForumPost(poster="ra", timestamp=2009-06-16 20:58:33)}>
Jen pro pořádek - myslim že to nebyl DELETE, ale INSERT na červeno-černých stromech - ne že by to nějak zásadně měnilo obtížnost...
<{/ForumPost}>

<{ForumPost(poster="Gorak", timestamp=2009-06-17 20:27:50)}>
Jasne, omlouvam se za mystifikaci, 1b) byl insert (IMHO je jeste jednodussi nez Delete). Uz jsem to opravil.  
 :oops:
<{/ForumPost}>