od kačus » 16. 2. 2017 14:54
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
. 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:
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
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 [latex]m=\Theta(n^3)[/latex]. 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:
[latex]h(x) = \sum_{i=0}^{d-1} T_i(x_i) \mod m[/latex]
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