Список заданий по АиСД-year2015-сем1

<wikitex>

Алгоритмы и структуры данных, 1 семестр

1. Можно ли построить структуру данных, с двумя видами операций, одна из которых работает за истинное $O(2^n)$, а вторая за истинное $O(\log{n})$, и при этом амортизированное время работы обеих операций $O(1)$. Почему?
2. Можно ли построить структуру данных, с двумя видами операций, одна из которых работает за истинное $O(\sqrt{n})$, а вторая за истинное $\Theta(\log{n})$, и при этом амортизированное время работы обеих операций $O(1)$. Почему?
3. Пусть структура данных выполняет два типа запросов. Первый тип запроса выполняется за $O(f(s) k \log{k})$, а второй — за $O(\frac{g(s)}{k \sqrt{k}})$, причем значение $k$ можно выбрать любым натуральным числом, а $f(s)$ и $g(s)$ известны и зависят от размера структуры данных. Вам стало известно, что к структуре данных сделают $n$ запросов первого типа, и $m$ запросов второго типа. Какое $k$ нужно выбрать, чтобы среднее время работы запросов было минимальным.
4. Проанализировать саморасширяющийся массив, если расширение происходит в $A$ раз ($1 < A$)
5. Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в 2 раза, а при заполнении менее чем на 1/4 - сужение в 2 раза с помощью метода потеницалов. Потенциал должен зависеть только от текущего состояния стека (размера выделенного массива и числа заполненных элементов) и не должен зависеть от истории операций.
6. Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в A раз, а при заполнении менее чем на B - сужение в C раз
7. Разработать вектор с добавлением/удалением с истинной стоимостью всех операций $O(\log n)$.
8. Разработать вектор с добавлением/удалением с истинной стоимостью всех операций $O(1)$.
9. В массиве есть элемент, который встречается хотя бы $n/2$ раз. Требуется найти его за $O(n)$ с $O(1)$ дополнительной памяти
10. Использования памяти без инициализации. Задан массив $a[1..n]$. Требуется поддержать две операции: $set(i, x)$ и $get(i)$. Операция $set$ должна присваивать $i$-му элементу массива значение $x$. Операция $get$ должна возвращать последнее присвоенное $i$-му элементу значение, либо 0, если присвоения не было. При этом исходно массив заполнен произвольными данными. Разрешается завести $O(1)$ дополнительных массивов (также заполненных произвольным мусором) и реализовать все операции за истинное $O(1)$.
11. Счетчик Кнута. Рассмотрим массив $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)$ дополнительной памяти.
12. Реализуйте менеджер памяти, позволяющий выделять и возвращать блоки одинакового размера за $O(1)$ времени и $O(1)$ дополнительной памяти
13. Предложите реализацию стека, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в стеке"
14. Стек с множественным извлечением. Добавим в стек операцию multipop(k), которая снимает вершины стека k элементов. Докажите, что амортизированная стоимость операции multipop равна $O(1)$. Сформулируйте окончательное доказательство с использованием метода потенциалов.
15. Продемонстрируйте, как просимулировать очередь на двух стеках. Амортизированная стоимость операций push и pop должна быть $O(1)$.
16. Предложите реализацию очереди, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в очереди". Амортизированная стоимость всех операций должна быть $O(1)$.
17. Можно ли реализовать два стека на очереди (ограничений на время выполнения операций нет)?
18. Задан односвязный список, каждый элемент знает следующий после себя. При этом возможно, что на самом деле список зацикливается (один из элементов ссылается как на следующий на элемент, который уже встречался в списке перед ним). Требуется проверить, зацикливается ли заданный односвязный список за $O(n)$ с $O(1)$ дополнительной памяти

</wikitex>