# Otázky u Feldmanna

<{ForumPost(poster="kačus", timestamp=2017-02-16 14:54:18)}>
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
<{/ForumPost}>