Краткое содержание лекций

1. Алгоритмы на графах

• Дфс, времена входа и выхода, функция up
• Отсутствие перекрестных рёбер
• Мосты
• Точки сочленения
• Компоненты реберной двусвязности
• Компоненты вершинной двусвязности
• СНМ
• Лемма о безопасном ребре
• Краскал

2. Паросочетание и Эйлеров цикл

• Двудольные графы, проверка на двудольность
• Паросочетание, теорема о дополняющей цепи
• Алгоритм Куна
• Вершинное покрытие и независимое множество в двудольных графах
• Эйлеров цикл

3. Задачи о рюкзаке

• Постановка задачи
• Задача о рюкзаке с предметами
• Решение с линейной памятью без восст. ответа
• Случай без стоимостей. Битовое сжатие
• Случай без стоимостей. Восстановление ответа с линейной памятью
• Задача о рюкзаке с типами
• Большое C
• Случай без стоимостей. Поиск кратчайшего пути в графе остатков
• Решение с помощью Meet-in-the-middle
• Генерация в подмножеств с ценой в отсотрированном порядке за O(2^n)
• Рюкзак в задачах на дереве

4. ДП со сложным состоянием

• Состояние - подмножество
• Пример - гамильтонов путь, комивояжер
• Перебор всех подмножеств за O(3^n)
• Состояние - профиль
• Изломанный профиль
• Пример - симпатичные узоры, замощения
• Возведение матрицы в степень
• Профиль - скобочная последовательность
• Профиль - компонента связности

5. log(n) в геометрии

• Выпуклая оболочка. Грэхем
• Точка внутри выпуклого многоугольника.
• Двоичный поиск на циклических последовательностях
• Касательная к многоугольнику. Пересечения прямой и вып. многоульника
• Калиперы. Минимальный и максимальный объемляющий прямоугольник.
• Две наиболее удалённые точки

6. Разделяй и властвуй

• Общий принцип разделяй и властвуй, примеры
• Две самые ближние точки
• Максимальный тандемный повтор
• Dynamic connectivity offline
• (*) Алгоритм Карацубы

7. ScanLine

• Краткое напоминание про ДО, групповые операции
• Сканирующая прямая
• Число точек в прямоугольнике
• Точка, накрытая макс. числом прямоугольников
• Число самопересечений ломаной
• Площадь объединения
• Какая-нибудь точка пересечения отрезков (smoking)
• Напоминание о декартовом дереве

8. Корневая эвристика

• Разбить элементы на кусочки по sqrt(n)
• Разбить запросы на кусочки по sqrt(n)
• Перестраивать через sqrt(n) запросов
• Если сумма объектов n, то различных <= sqrt(n)
• Алгоритм Мо
• Дискретный логарифм (Baby step Giant step)

9. Хеши, бор

• Хеши подстрок
• Сравнение строк, Суффиксный массив за O(n log^2 n)
• Антихеш тест
• Парадокc дней рождения
• Выбор числа модулей, умножение чисел по модулю порядка sqrt(2) * 2^61
• Хеши для множеств
• Бор, хранение, применение
• Цифровой бор

10. Ахо-Корасик

• Префикс-функция
• Автомат КМП
• Постановка задачи
• Суффиксные ссылки
• Дополнение до автомата
• Супер-суффиксные ссылки
• Использование

11. Суффиксный массив

• Определение
• Построение за nlogn
• Алгоритм Аримуры-Арикавы-Касаи-Ли-Парка
• Применения

12. LCA

• Постановка задачи
• Двоичные подъёмы
• Эйлеровы обходы деревьев
• Сведение к RMQ
• Sparse table
• Level ancestor problem
• Longest path decomposition (ladder)
• LA O(nlogn), O(1) combo: ladder + jump-pointers
• Алгоритм Тарьяна