Список заданий по АиСД-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| + |b|) ^ {2 - \epsilon})$, для некоторого $\epsilon > 0$.
18. Задача о рюкзаке. Заданы $n$ предметов, для каждого известен вес $w_i$ и цены $p_i$. Вам нужно выбрать подмножество предметов суммарным весом не более $W$ с максимальной суммарной ценой. Найдите это подмножество за время $O(W \cdot n)$ и память $O(W)$.
19. Подпалиндромом последовательности будем называть подпоследовательность $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$, в которой для любого $j$ выполняется $a_{i_j} = a_{i_{k-j+1}}$. Докажите, что длина максимального подпалиндрома последовательности $a$ равна длине наибольшей общей подпоследовательности $a$ и $a^r$, где $a^r$ — это развернутая последовательность $a$ ($a^r_i = a_{|a| - i + 1}$).
20. Покажите, что если решить задачу о максимальном подпалиндроме, использовав алгоритм поиска наибольшей общей подпоследовательности, как в предыдущем задании, то алгоритм может выдать подпоследовательность, которая не является палиндромом. Предложите алгоритм, который находит максимальный подпалиндром последовательности $a$ за время и память $O(|a|^2)$.
21. $a$ — последовательность длины $n$ из различных чисел от 1 до $n$. Докажите, что произведение длин наибольшей возрастающей и наибольшей убывающей подпоследовательностей в $a$ не меньше $n$.
22. Заданы две последовательности $a$ и $b$. Числа в последовательности $a$ различны. Найдите наибольшую общую подпоследовательность $a$ и $b$ за время и память $O((|a| + |b|) \log{(|a| + |b|)})$.
23. Заданы $n$ предметов, каждый весом $w_i$. Известно, что за один раз вы можете унести предметы, суммарным весом не более $S$. Какое минимальное число подходов вам нужно сделать, чтобы унести все предметы? Решать за $O(3^n)$.
24. Заданы $n$ различных натуральных чисел. Посчитать число перестановок этих чисел, что НОД любых двух соседних не меньше $d$ за $O(n^2 2^n)$.
25. Заданы $n$ предметов, каждый весом $w_i$. Известно, что за один раз вы можете унести предметы, суммарным весом не более $S$. Какое минимальное число подходов вам нужно сделать, чтобы унести все предметы? Решать за $O(2^n \cdot n)$.

</wikitex>