Материал, мимо которого мы прошли

29.07.12 День 1. Персистентные и сливаемые структуры данных.

Понятие персистентности.
Персистентное дерево отрезков.
Персистентное дерево поиска.
Персистентный стек.
Персистентная очередь.
Персистентный дек.
Выражение операций Build, Add, Merge друг через друга.
Добавление операции слияния к структурам данных с операцией add.
Добавление операции слияния к структурам данных с операцией build и без разделения.

30.07.12 День 2. Теория чисел.

Операции по модулю.
Китайская теорема об остатках..
ρ-метод Полларда.
Первообразные корни.
Дискретное логарифмирование.
Извлечение квадратного корня по модулю.
Комплексные числа.
Интерполяция: существование и единственность.

31.07.12 День 3. Теория чисел (продолжение).

FFT.
Тест Миллера-Рабина.
Двоичный, троичный, k-ичный поиск.
Градиентный спуск.
Метод отжига.

01.08.12 День 4. Задачи на путях и поддеревьях.

Splay Tree (cтатья [PDF]).

Euler Tour Tree.

Heavy-Light Decomposition.

Linking-Cutting Trees.

02.08.12 День 5. Задачи на путях и поддеревьях — продолжение.

Dinamic Connectivity Offline (sqrt N, log²N).
Dinamic 2-Connectivity Offline (sqrt N, log N).
Dinamic Connectivity Online.

03.08.12 День 6. Потоки.

Алгоритм Ефима Абрамовича Диница: базовый алгоритм, масштабирование, LCT.
Global Min-cut: Алгоритм Штор-Вагнера.
Preflow Push: базовая схема.
Preflow Push: очередь.
Preflow Push: Max-Height-Discharge.
Preflow Push: Global relabeling, Gap.

05.08.12 День 7. Линейная алгебра.

Аксиомы векторного пространства, примеры.
Системы линейных уравнений, пространство решений.
Метод Гаусса, обращение матрицы.
Edge-space, cycle-space, cut-space. Основные операции.
Проверка, является ли множество разрезом, оценка вероятности (без доказательства леммы)

06.08.12 День 8. Линейная алгебра — продолжение.

Евклидовы пространства. Скалярное произведение, метрика.
Проекция вектора на вектор. Ортогонализация Грама-Шмидта.
Задача линейного программирования. Приведение к стандартному виду.
Выпуклость множества. Свойства линейных функций на выпуклых множествах.
Каноническая форма. Симплекс-алгоритм.
Поиск начального допустимого решения.

07.08.12 День 9. Дополнительный материал.

Два вещественных преобразования Фурье.
Определитель, различные определения, основные свойства.
Матрица Татта: проверка наличия совершенного паросочетания.
Двойственность задач линейного программирования.

08.08.12 День 10. Геометрия number one!

Пересечение отрезков за N log N
Поворот на рандомный угол: ближайшие точки для всех точек за N sqrt N
Пара ближайших точек за N log N
Пересечение полуплоскостей за N³
Пересечение полуплоскостей за N²
Пересечение полуплоскостей за N log N
Пересечение полуплоскостей за N

11.08.12 День 11. Геометрия again and again and again...

Диаграмма Вороного за N^2

Точка внутри невыпуклого многоугольника: построение за N log² N, запрос за log² N
Точка внутри невыпуклого многоугольника: построение за N log N, запрос за log² N
Объединение кругов за N³
Пересечение невыпуклых многоугольников
3D геометрия: основы
3D геометрия: пересечение полупространств
3D геометрия: выпуклая оболочка за NH
3D геометрия: выпуклая оболочка за N²

12.08.12 День 12. Геометрия? Noooooooo...

Поток в планарном графе за N log N
Диаграмма Вороного за N log N