Otázky u Feldmanna

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.
kačus
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 11. 2. 2016 13:38
Typ studia: Informatika Bc.

Otázky u Feldmanna

Příspěvek od kačus »

Otázky, které jsem potkala, slyšela:

1) Fibonacci heaps
2) Definition of c-universal system, perfect hashing and "with high probability" + S is set of elements, |S| = n, size of hash table m=\Theta(n^3). Proof that hash function from c-universal system is perfect for S with high probability.

----

1) (a,b)-trees + red-black trees
2) You have a tabulation hashing with a small change: instead of XOR there is + and mod m:
h(x) = \sum_{i=0}^{d-1} T_i(x_i) \mod m
Proof it is 2-independent, but not 4-independent. (Well, the proof is practiclly the same as for normal tabulation hashing.)

----
1) Range trees
2) Interval trees
3) Some proof about Dijkstra
Odpovědět

Zpět na „TIN066 Datové struktury I“