Skúška Mareš
Napsal: 6. 10. 2020 21:51
1. linear probing - očakávaná dĺžka runu je ohraničené konštantou nezávislou na n,m a h.
Pýtal sa, kde je potrebný predpoklad úplne náhodnej hashovacej funkcie - na použitie Černovovej nerovnosti. V skutočnosti by to šlo zoslabiť, ale museli by sme použiť inú vetu a rátať momenty.
2. Ukažte, jak provádět 1-rozměrné intervalové dotazy na binárním vyhledávacím stromu.
Pýtal sa, kde je potrebný predpoklad úplne náhodnej hashovacej funkcie - na použitie Černovovej nerovnosti. V skutočnosti by to šlo zoslabiť, ale museli by sme použiť inú vetu a rátať momenty.
2. Ukažte, jak provádět 1-rozměrné intervalové dotazy na binárním vyhledávacím stromu.