Изменения
Нет описания правки
# Рассмотрим последовательность отрезков с целыми концами: $[l_1, r_2]$, $[l_2, r_2]$, $\ldots$, $[l_m, r_m]$ ($1 \le l_i \le r_i \le n$). Вам задан $x$ ($1 \le x \le n$), найдите число различных последовательностей отрезков, что никакой не вкладывается в другой и существует $i$, что $l_i=x$, за время $O((nm)^\frac{3}{2})$.
# Задано дерево из $n$ вершин. На каждом ребре записан один бит. Нам известно про каждое ребро, нужно ли оставить тот же бит или изменить на противоположный. На каждом шаге разрешается выбирать путь в дереве и изменять все биты на этом пути на противоположные. Какое минимальное число путей нужно выбрать, чтобы получить из начальной конфигурации битов конечную за $O(n^2)$.
# Докажите парадокс дней рождений: было выбрано $n$ случайных целых чисел от 1 до $m$, для того, чтобы вероятность, что хотя бы два из $n$ чисел совпадут, была больше $\frac{1}{2}$, требуется $n > C \sqrt{m}$, для некоторого $C$.
# Предложите алгоритм удаления элемента из хеш-таблицы с открытой адресацией, все операции все еще должны работать за $O(1)$.
# Предложите алгоритм удаления элемента из хеш-таблицы с открытой адресацией такой, что число занятых ячеек всегда равно числу элементов в хеш-таблице, все операции все еще должны работать за $O(1)$.
# Пусть при хешировании используется разрешение конфликтов с открытой адресацией линейным проходом, размер хеш-пространства равен $cn$, где $n$ {{---}} число элементов. Оцените среднюю длину кластера (участка из подряд идущих занятых ячеек)
# Докажите, что конструкция семейства $H = \{ (ax + b) \bmod p \bmod m \}$, где случайно выбираются $a$ и $b$, $0 \le a, b < p$, является универсальным семейством хеш-функций.
# Универсальное семейство $H$ хеш функций обладает свойством попарной независимости, если для любых двух злементов $x$ и $y$ и любых двух хеш-значений $a$ и $b$ вероятность того, что $h(x) = a$ и $h(x) = b$ есть $1/m^2 + o(1 / m^2)$ (вероятность берется по случайному выбору хеш-функции из множества $H$). Докажите, что семейство из предыдущего задания обладает этим свойством.
</wikitex>
