• Задачи на поддеревьях
  • Дерево. Поддеревья, листья, отношение предок-потомок, корень
  • Эйлеров обход дерева. Время входа и выхода
  • Двоичные подъемы
  • Задачи LCA и LA
• Задача RMQ
  • Формулировка, варианты решения. Разреженные таблицы
• Алгоритм Фарах-Колтона и Бендера
  • Сведение LCA к RMQ+-1
  • Решения RMQ+-1 за O(1) с предпосчетом за O(N)
• Сведение RMQ к LCA

• Двоичные подъемы: O(log n) на запрос + O(N log N) предпосчет
• Лесенки: O(log n) на запрос + O(N) предпосчет
• Двоичные подъемы + Лесенки: O(1) на запрос + O(N log N) предпосчет
• Идея уменьшить число прыжковых вершин до O(N / log N)
• Микро-макро эвристика

http://courses.csail.mit.edu/6.851/spring14/scribe/lec15.pdf

• Поиск минимума на пути в дереве
• Статическая задача: двоичные подъемы
• Тяжелые и легкие ребра
• Разбиение на тяжелые пути
• Оценка \(log(n)\) на число легких ребер
• Финальная оценка \(log^2(n)\)
• Off-topic: амортизационный анализ
  • амортизационное время. определение
  • метод потенциалов
  • метод предоплаты

• Строки. Основные определения.
• Хеширование строк с помощью полиномиальных хешей
• Алгоритм Рабина--Карпа
• Префикс-функция и КМП
• Алгоритм Бойера--Мура
• Z-функция

• Бор. Использование для хранения множества строк
• Суффиксные ссылки.
• Поиск множества строк с помощью бора и суффиксных ссылок
• Алгоритм Ахо-Корасик, связь с КМП

• Суффиксное дерево. Определение. Примеры использования.
• Суффиксный массив. Построение с помощью сортировки.
• Ускорение сортировки с помощью хешей.
• Алгоритм построения за O(N log N)
• Алгоритм Касаи
• Примеры использования.
  • нахождение подстроки
  • нахождение наибольшего общего префикса
  • подсчет числа различных подстрок
  • нахождение наибольшей общей подстроки

• Суффиксное дерево. Основные свойства
• Итеративный алгоритм построения за \(O(N^2)\) дополнением символов в конец строки
• Оптимизация размера дерева с помощью сжатия путей
• Переход по суффиксной ссылке в сжатом дереве
• Автоматическое продление листов
• Итоговая линейная оценка

• Паросочетание. Определение
• Паросочетание в двудольном графе
• Теорема о дополняющем пути
• Поиск дополняющего пути
• Алгоритм Куна
• Нахождение минимального вершинного покрытия
• Нахождение минимального реберного покрытия

• Поток
• Разрез, лемма о потоке через разрез
• Дополняющая сеть, дополняющий путь
• Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
• Алоритм Эдмондса-Карпа

• Стоимость потока
• Теорема о дополняющем пути минимального веса
• Построение потока с помощью Форда-Беллмана
• Потенциалы Джонсона

Дополнительно: * Алгоритм Диница

• Игры на графах. Выигрышные, проигрышные, ничейные позиции
• Ациклические графы
• Графы с циклами. Ретроспективный анализ
• Сумма игр
• Функция Гранди