Изменения
Нет описания правки
# Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в 2 раза, а при заполнении менее чем на 1/4 - сужение в 2 раза с помощью метода потеницалов. Потенциал должен зависеть только от текущего состояния стека (размера выделенного массива и числа заполненных элементов) и не должен зависеть от истории операций.
# Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в A раз, а при заполнении менее чем на B - сужение в C раза
# Разработать вектор с добавлением/удалением с истинной стоимостью всех операций $O(\log n)$.
# Задан односвязный список, каждый элемент знает следующий после себя. При этом возможно, что на самом деле список зацикливается (один из элементов ссылается как на следующий на элемент, который уже встречался в списке перед ним). Требуется проверить, зацикливается ли заданный односвязный список за $O(n)$ с $O(1)$ дополнительной памяти
# В массиве есть элемент, который встречается хотя бы $n/2$ раз. Требуется найти его за $O(n)$ с $O(1) $ дополнительной памяти
# Использования памяти без инициализации. Задан массив $a[1..n]$. Требуется поддержать две операции: $set(i, x)$ и $get(i)$. Операция $set$ должна присваивать $i$-му элементу массива значение $x$. Операция $get$ должна возвращать последнее присвоенное $i$-му элементу значение, либо 0, если присвоения не было. При этом исходно массив заполнен произвольными данными. Разрешается завести $O(1)$ дополнительных массивов (также заполненных произвольным мусором) и реализовать все операции за истинное $O(1)$.
# Можно ли просимулировать два стека на одной очереди?
# Счетчик Кнута. Рассмотрим массив $a[0..n-1]$. Будем считать, что в каждом элементе может быть число 0, 1 или 2 и массив представляет собой число $a[0]+a[1]\cdot 2+a[2]\cdot 4 + \ldots + a[n-1]\cdot2^{n-1}$. Требуется реализовать операцию добавления $2^k$ к числу, представленному в массиве за истинное $O(1)$ и $O(n)$ дополнительной памяти.
# Реализуйте менеджер памяти, позволяющий выделять и возвращать блоки одинакого размера за $O(1)$ времени и $O(1)$ дополнительной памяти
# В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Какое оптимальное асимптотически $d$ следует выбрать?
# В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Время выполнения decreaseKey - $C_1 \log n$, а extractMin - $C_2 d \log n$. Какое $d$ следует выбрать?
# Как найти $s$-й по величине элемент в куче при малых $s$?
# Приведите алгоритм построения кучи из $n$ заданных элементов за $O(n)$
# На базе кучи разработайте алгоритм сортировки за $O(n \log n)$ c $O(1)$ дополнительной памяти
# Левосторонние кучи. Будем называть двоичное дерево левосторонней кучей, если в нем выполнены следующие условия. 1) На элементах выполнен порядок кучи. 2) Будем называть отсутствующего ребенка "свободной позицией". Обозначим как $d(u)$ минимальное расстояние от вершины $u$ до свободной позиции в ее поддереве. У любой вершины $u$ с левым ребенком $L(u)$ и правым ребенком $R(u)$ должно быть выполнено $d(R(u)) \le d(L(u))$. Докажите, что для любой вершины $d(u) \le \log_2 n$. Как найти свободную позицию в левосторонней куче за $O(\log n)$?
# Предложите реализацию операции merge для левосторонних куч.
# Предложите реализацию операций insert, extractMin для левостронних куч.
# Предложите реализацию операций decreaseKey для левостронних куч.
# Как построить левостороннюю кучу из $n$ элементов за $O(n)$?
# Пусть подряд выполняется $n$ операций insert в пустую биномиальную кучу. Какое среднее время операции?
# Как можно модифицировать биномиальную кучу, чтобы insert выполнялось за истиное $O(1)$, а амортизированная стоимость остальных операций не поменялась?
# Тонкие кучи. Будем называть дерево "тонким", если оно может быть получено из биномиального удалением у некоторых вершин ребенка максимального ранга. Тонкой кучей называется коллекция тонких деревьев. Операции insert, extractMin и merge выполняются в тонкой куче также, как в куче Фибоначчи. Разработайте операцию decreaseKey для тонкой кучи. Докажите, что амортизированное время выполнения есть $O(1)$ (используйте потенциал $2M + T$, где $M$ - число вершин, у которых удалили ребенка)
# Тонкие кучи. Докажите, что операция decreaseKey в тонкой куче из предыдущего задания выполняется за истиные $O(\log n)$
# Ускорение extractMin. Докажите, что в фибоначчиевой или тонкой куче можно добиться истинного $O(\log n)$ на extractMin, если обрабатывать корневой список, сливая деревья разных рангов, как при extractMin каждый раз, когда в корневом списке становится хотя бы $2\log n$ элементов.
</wikitex>
