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

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

• Персистентные структуры данных
• Ортогональные запросы в 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 пар.