Алгоритмы и структуры данных, 2022-2024

Первый семестр

Время работы алгоритма. O-нотация. Квадратичные сортировки. Сортировка слиянием. Два указателя. Двоичная куча. Сортировка кучей. Бинарный и тернарный поиск. Стек. Очередь. Амортизационный анализ. Связные списки. Pointer Machine. Система непересекающихся множеств. Быстрая сортировка. K-я порядковая статистика. Динамическое программирование. Задача о рюкзаке. Наибольшая возрастающая/убывающая подпоследовательность.

Второй семестр

Дерево отрезков. Дерево Фенвика. Sparse Table. Многомерные структуры данных. Хеш-таблицы. Двоичное дерево поиска. AVL-дерево. Декартово дерево. Splay дерево. LCA. HLD. Центроидная декомпозиция.

Третий семестр

Обход в глубину. Компоненты сильной связности. Конденсация графа. 2-SAT. Мосты и точки сочленения. Двусвязность. Эйлеровость. Обход в ширину. Алгоритмы Дейкстры и Форда-Беллмана. Алгоритм Флойда. Минимальное остовное дерево. Строки. Префикс-функция и Z-функция. Бор. Ахо-Корасик. Цифровой бор. Суффиксный массив. Корневые оптимизации.

Четвёртый семестр

Паросочетания в двудольных графах. Паросочетания в произвольных графах. Потоки. Задача о назначениях. Линейное программирование. Вычислительная геометрия. Теория чисел. Быстрое преобразование Фурье.