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

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

• Топологическая сортировка
• Выделение компонент сильной связности
• 2-SAT, решение
• 1.5-приближение задачи коммивояжера
• Сеть, остаточная сеть, поток, разрез
• Теорема Форда-Фалкерсона: Связь максимального потока, минимального разреза и отсутствия дополняющего пути.
• Алгоритм Форда-Фалкерсона
• Масштабирование
• Алгоритм Эдмондса-Карпа

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

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

5. ДП по профилю и подмножествам

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

6. Геометрия за log

• Выпуклая оболочка за O(n log n)
• Проверка принадлежности точки выпуклому многоугольнику за O(log n)
• Поиск касательных к выпуклому многоугольнику, параллельных данной прямой
• Поиск точек пересечения прямой и выпуклого многоугольника
• Поиск касательных к выпуклому многоугольнику из точки
• Две наиболее удалённые точки
• Сумма минковского и ее применения

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

• Основные принципы. Сортировка слиянием
• Детерминированный алгоритм поиска медианы
• Две ближайшие точки
• Маскимальный тандемный повтор
• Dynamic connectivity offline
• Алгоритм Карацубы
• Мастер-теорема с доказательством

8. ScanLine

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

9. Корневая оптимизация

• SQRT-декомпозиция массива с операциями:

1. insert(i, x), erase(i)
2. sum(l, r), min(l, r)
3. add(l, r, x), reverse(l, r)
4. elements_less_than_x(l, r, x)
5. kth_statistics(l, r, k) split/merge split/rebuild

• SQRT-декомпозиция запросов
• Маленькие и большие объекты. Задача про треугольники в графе
• Если сумма объектов n, то различных <= sqrt(n)
• Алгоритм Мо
• Алгоритм Мо на дереве

10. Алгоритмы на строках

• Префикс функция
• Бор
• Автомат Ахо-Корасик
• строка не содержащая набор строк
• Суффиксный массив: определение, построение за O(n^{2logn) и O(nlog}2n)
• Алгоритм вычисления LCP: Касаи-Ли-Аримуры-Арикавы-Парка
• Поиск строки в тексте за O(S + log T)

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

• Построение за O(n*logn)
• Максимальная общая подстрока двух строк
• Количество различных подстрок

12. Теория сложности

• Языки и да/нет-задачи
• Существование неразрешимых задач из теоретикомножественных соображений
• Машина Тьюринга и недетерминированная МТ
• Классы P, NP, co-NP, соотношение, примеры
• Теорема Кука: NP-полнота задачи CNF-SAT, a также 3-SAT
• NP-полнота 3-COL
• NP-полнота HAM и UHAM
• NP-полнота SUBSET SUM и KNAPSACK
• NP-полнота IS (а также VERTEX COVER и CLIQUE)