Zkouška 29.1.2014

Klasická sada otázek, žádné pekla z Dodatků jsem neslyšel.

Já měl univerzální hasovani.

Napsal jsem definici, alt. definici s pravdepodobnosti s minidukazem. Dolni odhad c bez dukazu. Existenci c - univ. systemu s dukazem. Ocekavanou slozitost (µ = Σ δ) coz vede na 1 + c α s dukazem (to prohozeni sum) a markovovu nerovnost bez dukazu.

Cetl, cetl, kyval souhlasne hlavou. Nakonec se me zeptal na to jak volit i pro h_i. Ja, ze generatorem pseudonahodnych cisel. On proc chceme cmalé? Já, že pseudonahodne generatory jsou zavisle na drive vygenerovanych hodnotach. Oceneno bez dalsiho komentare zapisem do indexu za jedna.

Já bych jen dodal, že skutečně dodatek zkouší, kolega vedle mě dostal kukaččí hašování a myslím, že to hned vzdal, protože to nevěděl (asi na dodatek vůbec nekoukal). Přitom si myslím, že když si to člověk jednou přečte, tak to není těžké a zbytečně takto můžete přijít o jeden pokus.

Jinak já jsem měl červeno-černé stromy a celkem jsem se u toho zapotil. Popsal jsem asi 6x A4, všechny operace a rotace a vyvažování až na jednu u DELETE jsem měl dobře, měl jsem tam důkaz, že výška stromu je O(log|S|), definice 2-parc, 3-parc atd. a stejně mě tam pan Koubek hodně trápil. Hlavní je dát si pozor na definici bin. vyhledávacích stromů, kterou jsem samozřejmě zkazil. :-) Není to jen levý(v) < v < pravý(v) pro všechna v, ale (všechny levý(v)) < v < (všechny pravý(v)) pro všechna v. Tímto jsem ho myslím docela dost naštval (ještě mi vyčítal, jak několikrát zdůrazňoval na přednášce, že na tohle si máme dát pozor a stejně mu to tam všichni píšeme špatně :-)) a i když jsem měl pak všechno dobře (až na to jedno vyvažování), tak mi řekl, že se mu to nelíbí, ale že mi dá za 3. Byl jsem nakonec rád, že mám datovky za sebou...

Dnešní termín (30.1.):

Huffmanův kód (napsal jsem prakticky všechno, co bylo ve skriptech, ale něco jsem pokazil v závěru toho důkazu, takže za 2)

Co jsem tak zaslechl okolo: Červeno-černé stromy, binomiální haldy, Fibonacciho haldy, ale taky třeba souvislost Quicksortu s operacemi na obecném BVS...

Tip 1: Nepodceňte látku z Dodatku, zkouší se a celkem houfně (a rozhodně to není peklo, dá se naučit zhruba za den).

Tip 2: Pokud chcete ČČ-stromy, sedněte si do první řady úplně vpravo (založeno na dvou pozorováních) :D

Jo, 30. byl slyšet z druhé strany místnosti zase normální (A-sort, dvojité hashování, leftist haldy...) a relaxované stromy dostal nějaký chudák.
Přišlo mi, že možná není zas tak složité dostat tu trojku, jen se asi člověk fakt zapotí, když chce cokoliv lepšího...