Если использовать универсальное семейство хэш-функций для хранения n ключей, то при размере хэш-таблицы M = n², какова будет вероятность получить хотя бы одну коллизию?

Правильный ответ:

• # У структуры данных дерево отрезков рассмотрим произвольную вершину v и относящийся к ней отрезок [l, r]. Если l ≠ r, каких сыновей имеет эта вершина?
• # Что такое канонический отрезок в дереве отрезков?
• # Как эффективно реализовать стэк с поддержкой минимума?
• # Как можно добиться, чтобы логарифмическая оценка для алгоритма быстрой сортировки была справедлива не в среднем, а в худшем случае?
• # За какое время в среднем выполняется поиск ключа в структуре данных дуча (treap)?