Zkouska - Hric 16.6. 2009

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Gorak
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 16. 1. 2007 13:08

Zkouska - Hric 16.6. 2009

Příspěvek od Gorak »

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(n2) - to je ten s O(n^log23) (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
Naposledy upravil(a) Gorak dne 17. 6. 2009 20:25, celkem upraveno 1 x.
ra

Re: Zkouska - Hric 16.6. 2009

Příspěvek od ra »

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...
Gorak
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 16. 1. 2007 13:08

Re: Zkouska - Hric 16.6. 2009

Příspěvek od Gorak »

Jasne, omlouvam se za mystifikaci, 1b) byl insert (IMHO je jeste jednodussi nez Delete). Uz jsem to opravil.
:oops:
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“