1. (1) Префикс-функция. Линейный алгоритм подсчета. Алгоритм Кнута-Морриса-Прата.
2. (1) Z-функция. Линейный алгоритм подсчета. Алгоритм Кнута-Морриса-Прата.
3. (1) Полиномиальное хеширование. Алгоритм Рабина-Карпа.
4. (1) Бор. Сравнительный анализ времени работы в зависимости от выбора контейнера для хра-
нения дочерних вершин.
5. (3) Суффиксный массив. Построение за O(|S| log |S|).
6. (3) Понятие LCP. Массив lcp. Алгоритм Касаи-Аримуры-Арикавы-Ли-Пака построения lcp
(корректность б/д). Поиск LCP с использованием массива lcp и решения задачи RMQ.
7. (2) Суффиксные ссылки в боре. Функция перехода. Алгоритм Ахо-Корасик построения суф-
фиксных ссылок.
8. (2) Сжатые суффиксные ссылки. Автомат Ахо-Корасик. Поиск множества паттернов в тексте.
9. (1) Понятие правого контекста. Классы эквивалентности по равенству правых контекстов. Тео-
рема Майхилла-Нероуда (б/д). Определение суффиксного автомата.
10. (1) Атрибуты состояний. Устройство класса эквивалентности.
11. Понятие longest. Критерий longest. Устройство ребер в суффиксном автомате.
12. (2) Новые состояния в суффиксном автомате при дописывании символа. Алгоритм построения
суффиксного автомата: случаи 1 (новая буква) и 2 (без порождения clone).
13. (3) Алгоритм построения суффиксного автомата: все случаи.
14. (2) Время построения суффиксного автомата.
15. (1) Задача интерполяции. Матричная постановка, существование и единственность решения.
Комплексные корни из единицы. Обратная к матрице Вандермонда на комплексных корнях из
единицы.
16. (2) Дискретное преобразование Фурье. Быстрое преобразование Фурье. Преобразование бабоч-
ки.
17. (2) Обратное преобразование Фурье. Перемножение многочленов.
18. (3) Свертка последовательностей. Расстояние Хэмминга. Алгоритм поиска вхождений паттерна
в текст с не более k расхождениями.
19. (1) Персистентные структуры данных. Частичная и полная персистентность. Персистентный
стек
20. (2) Персистентные структуры данных. Частичная и полная персистентность. Персистентный
массив
21. (2) Процедура Merge. Оптимальное время работы: оценка.
22. (2) Процедура Merge. Оптимальное время работы: оценка б/д, алгоритм.
23. (2) Inplace Merge Sort.
24. (1) Алгоритм Introsort.
25. (1) Биномиальные деревья. Свойства: число вершин на уровне. Процедуры SiftDown, SiftUp и
DecreaseKey в биномиальном дереве.
26. (2) Биномиальная куча. Время работы слияния куч. Выполнение основных операций кучи.
27. (2) Фибоначчиева куча. Топология узла. Структура кучи. Операции Insert, Merge, GetMin.
28. (2) Фибоначчиева куча. Структура кучи. Операции Consolidate, ExtractMin. Оценка на D(n).
29. (3) Фибоначчиева куча. Структура кучи. Операции Consolidate, DecreaseKey. Оценка на D(n).
30. (1) Алгоритмы во внешней памяти. Устройство памяти и понятие I/O-операции. Понятия latency,
throughput. Модель оценивания времени на основе I/O-операций. Модельная задача: сумма по-
следовательности во внешней памяти.
31. (2) Алгоритмы во внешней памяти. Модель оценивания времени на основе I/O-операций. Сор-
тировка во внешней памяти.
32. (3) Алгоритмы во внешней памяти. Модель оценивания времени на основе I/O-операций. (a, b)-
дерево. Основные операции с (a, b)-деревом.
33. (3) Алгоритмы во внешней памяти. Модель оценивания времени на основе I/O-операций. BufferTree
как (a, b)-дерево. Разбиение буффера на две части: основную и накопительную с родителей.
34. (1) Задание полуплоскости. Пересечение полуплоскостей за O(N 2 ).
35. (2) Пересечение полуплоскостей за O(N log N ) через построение огибающих.
36. (2) Пересечение полуплоскостей за O(N log N ) без построения огибающих.
37. (1) Диаграмма Вороного за O(N 3) или за O(N 2 log N ).
38. (2) Диаграмма Вороного. Линейность числа ребер и граней.
39. (2) Диаграмма Вороного. Критерии того, что точка является вершиной или лежит на ребре в
диаграмме Вороного.
40. (3) Диаграмма Вороного. Алгоритм Форчуна.
41. (2) Граф Делоне. Линейность числа ребер и граней в графе Делоне. Критерии того, что вер-
шина/ребро будут в графе Делоне.