В рамках курса будут рассмотрены продвинутые алгоритмы и структуры данных, как правило, не покрываемые курсом базовых алгоритмов. Отчетность: задача по программированию, теоропрос в конце курса. Правила получения зачёта.

Список планируемых тем, порядок может поменяться:

• Персистентные структуры данных
• Ортогональные запросы в K-мерных пространствах (дерево отрезков, fractional cascading)
• MST и запросы на пути дерева (min, sum на пути дерева за $ O(1) $, рандомизированный алгоритм для поиска MST за $ O(E) $)
• Алгоритмы без использования дополнительной памяти (rotate, $ d $-куча, minmax-куча, merge, стабильная сортировка BlockSort)

• Кучи (куча Фибоначчи, Leftist, Skew, Pairing, Weak, Radix, алгоритм Дейкстры за $ O(m + n\sqrt{\log C}) $)

• Поиск на плоскости (локализация точки в планарном графе в offline и online)

• Неортогональные запросы на плоскости (число точек в полуплоскости, в треугольнике в online за $ O(n^{0.44}) $, где n − число исходных точек)

• Вычисления и структуры данных во внешней памяти, cache-oblivious вычисления

• LCA, RMQ, LA

• Euler-Tour trees, Heavy-Light декомпозиция, Link-Cut trees, Динамическая связность графов в online

• Динамическая связность и 2-связность в offline; задача о поиске MST: $ \max w - \min w = \min $

• Потоки и разрезы (глобальный разрез за $ O(V^3) $ и $ O(V^2\log V) $, preflow push & global relabeling, поток за $ O(VE + V^2\log U) $)

• Графы (stable marriage problem, поток минимальной стоимости за полином, цикл минимального среднего веса, кратчайший путь за $ E\sqrt V $)

• Метод четырех русских (число единичных бит, умножение булевых матриц за $ O(n^3/log^2n) $, НОП за $ O(n^2/log^2n) $, построение схемы по булевой функции)

Последние три темы (потоки, графы, метод четырех русских) мы скорее всего не успеем рассмотреть за 12 пар.