Otázky u Feldmanna

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