Zk 21. 1. 2014

Dostal jsem fibonaciho haldy. Slovne jsem presne popsal jak probihaji operace (insert, min atd). Napsal slozitosti a rekl, jaky jsou amortizovany slozitosti. Nemel jsem to uplne tip top jako v knizce, ale vse hned proslo. Pak jsem se snazil dokazat amortizovanou slozitost (dukaz pres fibonaciho cisla). Tam jsem se trochu zasekl, tak pak jsem jen dopsal myslenku. Tzn i-ty strom ma alespon F_i+2 vrcholu a fib cisla rostou exponencialne, tzn staci log stromu (zkracene receno). Vse stacilo na 1.

Takze je dulezite znat princip a vysvetlit ho, netreba to uplne exaktne spocitat.
Na 3 by urcite v pohode stacilo jen popsani operaci.

Já jsem dostal A-sort, tak jsem se pozvolna rozpomenul na fungování ab-stromů a ve výsledku snad popsal algoritmus tak, jako byl na přednášce. Včetně složitosti, tu jsem si z části pamatoval a odvodit se dá docela snadno. Koubek se zeptal na pár podrobností, protože jsem řešení psal hodně random-access, a dal mi jedničku.

Teď mi dochází, že vlastně ani nemám ponětí, proč algoritmus čte posloupnost odzadu: popředu by podle mě fungoval taky.

Úspěšnost asi hodně záleží na otázce. Spolužák, co dneska přišel pozdě a neomluvil se, dostal perfektní hashování a radši šel rovnou zas domů.