Список заданий по АиСД-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)$.

</wikitex>