Otázky u Feldmanna
Napsal: 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:
 = \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
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
----
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