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

<wikitex>

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

1. Покажите, что если в сплей дереве при операции splay делать только операцию zig на всем пути до корня, то амортизированное время работы не $O(\log n)$.
2. Петя предлагает сделать гибрид декартового дерева и сплей-дерева: при доступе к ключу в декартовом дереве удалять его и добавлять заново с приоритетом меньше текущего минимального. Что у него получилось?
3. Докажите, что если сделать splay ко всем элементам в порядке возрастания ключа, то суммарное время работы будет $O(n)$.
4. Постройте дерево из хотя бы 7 вершин, которое после операции splay к одному из самых глубоких листьев становится бамбуком.
5. В пустое сплей-дерево были добавлены элементы в таком порядке: 30, 40, 60, 50, 80, 70. Какой элемент нужно добавить, чтобы дерево имело минимальную глубину? А какой, чтобы максимальную?
6. Пусть мы хотим хранить информацию только в листьях дерева, как нам использовать сплей-дерево для этого?
7. Предложите реализацию операции splay(v), если у вас нет ссылки на саму вершину $v$ и ссылок на родителя во всех вершинах, а известен только ее ключ, с $O(1)$ дополнительной памяти.
8. Задана строка длины $n$ из латинских букв и знаков вопроса. Посчитать число слов длины $n$ из букв латинского алфавита, в которых после согласной всегда идет гласная буква, которые можно получить заменой знаков вопроса во входной строке на буквы, за время $O(n)$.
9. Задано дерево, у каждой вершины есть вес. Нужно выбрать $k$ вершин суммарно максимального веса, чтобы никакие две соединенные ребром вершины не были выбраны.
10. Задана скобочная последовательность из нескольких видов скобок. Посчитайте минимальное число скобок, которое нужно вставить в эту последовательность, чтобы она стала правильной.
11. Задана последовательность чисел длины $n$, каждое число не больше $n$. Посчитайте число различных непустых подпоследовательностей последовательности за $O(n)$. Например, последовательность (1, 1, 2) содержит 5 подпоследовательностей: (1), (2), (1, 2), (1, 1), (1, 1, 2).
12. Посчитайте число различных двоичных деревьев из $n$ вершин.
13. Посчитайте число различных двоичных деревьев из $n$ вершин без порядка на детях.
14. Посчитайте число различных красно-черных деревьев из $n$ вершин.
15. Предложите алгоритм восстановления наибольшей возрастающей подпоследовательности по функции ДП, вычисление которой была предложено на лекции за $O(n \log{n})$ с $O(n)$ дополнительной памяти.
16. Задана последовательность. Про каждое $i$ определите одно из трех: элемент $a_i$ не может входить ни в одну НВП, элемент $a_i$ входит хотя бы в одну НВП, элемент $a_i$ входит во все НВП за $O(n \log{n})$.
17. Заданы две последовательности $a$ и $b$. Подпоследовательность $c$ называется общей для $a$ и $b$, если $c$ является подпоследовательностью $a$ и подпоследовательностью $b$. Найдите наибольшую общую подпоследовательность $a$ и $b$ за время $O(|a| \cdot |b|)$ и памятью $o(|a| \cdot |b|)$.
18. Задача о рюкзаке. Заданы $n$ предметов, для каждого известен вес $w_i$ и цены $p_i$. Вам нужно выбрать подмножество предметов суммарным весом не более $W$ с максимальной суммарной ценой. Найдите это подмножество за время $O(W \cdot n)$ и память $O(W)$.

</wikitex>