Otázky u Feldmanna

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Otázky u Feldmanna

Otázky u Feldmanna

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 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

Nahoru