Zkouška 16.6.2008(Hric)

[marxin]

Písemná část zkoušky:
1a:Delete na AVL stromech
1b:Dokázat, že výška RB-stromu je O(logN)
2a:Dokažte, že pro neorientovaný graf je množina všech lehkých hran pro všechny řezy minimální kostra
2b:Ukažte jakou má časovou složitost Jarníkův algoritmus v závislosti na volbě datové struktury
3a:Definujte topologické uspořádání
3b:Dokažte správnost algoritmu pro nalezení nejkratší cesty v acyklickém grafu (orientovaném)

Ústní část:
Důkaz Master-Theoremu

Hric se choval docela příjemně, dostal jsem na ústní čas na přípravu, žádné záludné otázky nepokládal.

[Him]

Moje ustní: silne souvisle komponenty - je dobre rict obe lemmata k tomu + definici transponovaneho grafu + definici silne souvislych komponent.. znamka je podle pisemky a ustniho - pokud je pisemka slabsi, tj. mene nez 11 bodu z 15, tak mate zarucenou dvojku.. me ji kvuli tomu jednomu bodu dal

[vidlak]

Já vás asi naštvu, ale měl sem z písemky 9 bodů, všechny důkazy byly vlastní bez použití jedinýho lemma (důkaz ČČ stromů sem měl na tři řádky, prošel za plný počet). U ústní sem písemku dostal k opravě (všechno sem opravil na ok). K ústní mi nejdřív dal hledání nejkratší cesty pomocí speciálního násobení matic. To sem se přiznal rovnou že nevím, tak sem dostal Master Theorem. Ke konci se mne ještě zeptal na lineární třídící algoritmy (radix sort) a dostal sem za 1 !!! Odcházel sem jako poslední v 17:45 štastnej jako blecha

P.S.: 2b bylo: Navrhněte datovou strukturu pro Primův (Jarníkův) algoritmus a ukažte jeho složitost. Tedy stačilo jen napsat, že se používá halda, jsou v ní vrcholy ohodnocené podle nejmenší hrany která do něj vede z již zpracované kostry, v každém kroku se odebere min a zavolá decrease_key na vrcholy do kterých vede hrana ze zpracovávaného vrcholu. Složitost tak log n za každý vrchol a hranu -> (n+m)*log n