Zkuska 6.2

Tak stastne hlasim ze to mam za sebou :). Ocividne mal p. koubek aj mna rad a dal mi Quicksort, som mu tam popisal tri strany, po 20 minutach som mu ich ukazal, na vsetko prikyvoval ze dobre dobre, a potom sa ma spytal ci by som nejak vedel este doplnit preco je slozitost v priemernom pripade nlogn, ja som nejak vahal, a povedal ze inac mi to da za 3, ked som pocul tuto moznost uz som nevahal a zobral som si trojku :D. Uff esteze to mam za sebou.

Ostatny mali:
Hasovania vselijakych druhov(dvojite,..)
A-sort
WordSort
Hladanie v usporiadanom poli

Nutno podotknut este jeden fakt, ze p. Koubek to vymysla fakt za behu a prave na zaciatku ho vacsinou vzdy napadnu hashovania a ku konci ho uz napadaju vseliajke zvrhlosti, alebo lahke veci, napriklad, ja som bol skoro posledny, a uz nemal z coho lovit ale kedze predomnou typek mal wordsort tak mi dal quicksort ;).

Moje zkušenost je téměř na chlup stejná. Sice jsem popsal jen dvě A4 a měl jsem dvojité hashování, ale výsledek byl stejný. Odevzdával jsem jako druhý asi po 40 minutách. Složitost jsem tam měl a když chtěl důkaz, tak sem mu řek, že asi ne. Tak říkal, že bez důkazu za tři ... bych se akorát trápil a nic nevyplodil, tak jsem radši bral :D
Doplním otázky co jsem zaslechl:
RB stromy
AVL stromy
univerzalni hash
konstrukce perf. hash

Snažil jsem se, ale víc jsem neslyšel (a nebo si nevzpomínám). Řekl bych že se snažil každýmu dát něco jinýho.
Jeden to vzdal a o ostatních nevím...

Tak už to mám taky za sebou. Byl jsem první a dostal jsem hašování se separovanými řetězci. Popis, algoritmy, důkaz časové složitosti v úspěšném a neúspěšném případě. 8)

O 4 a půl A-čtyřky a necelé dvě hodinky později jsem měl hotovo, a kdybych se nezamotal ve výpočtech, tak to mohlo být dřív. Musím ocenit, že dr. Koubek dává dost času a je hodnej. Jenom by mohl mluvit trošku hlasitěji :-)

Docela jsem se divil, když to někteří odevzdávali už po pár desítkách minut. Mě nenapadlo, že jste zvolili tak pragmatický přístup. :wink:

Jinak kolega vedle (v pořadí druhý) měl myslím perfektní hašování - dolní odhad velikosti a existenci.

Já jsem dostal (a,b)-stromy, za dvě a půl hoďky jsem vyprodukoval 6 A4, kde jsem celkem podrobně popsal (slovy, nikoli kódem) snad všechny operace na těchto stromech + nějaké povídání prosáklé z OZD I. Měl jsem jinak štěpení/slévání než bylo na přednášce, což ovšem nebylo hodnoceno negativně, jen jsem na to byl upozorněn.

Dr. Koubek to vše prošel a následně pokládal dotazy směřující k nejednoznačně/nepřesně popsanému chování. Ptal se buď jak něco bude fungovat na určitém vstupu, z čehož se dalo vcelku svižně odvodit, kde je třeba ještě něco ošetřit, ale také pokládal dotazy "Bude to takto fungovat vždy ?", to jsem pak obhajoval dobré chování na všech vstupech, dokud jsem sám nenašel chybu, nebo jsem nebyl zastaven dotazem "Opravdu ?".

Nakonec jsem neobhájil, že se SPLIT vejde do O(log |S|) a dostal jsem za 2 se slovy "ale to jsme si ukazovali na přednášce" :wink: .

Poznatek: Je dost času rozmyslet si každý položený dotaz a je lépe hodnoceno, když je odpověď jednoznačná a přesná, než když se hraje slovní ping-pong.