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

Амортизационный анализ

• Амортизационный анализ
• Динамический массив
• Hashed Array Tree[math]^\star[/math]
• Список
• Стек
• Очередь
• Дек
• Мажорирующий элемент
• Счетчик Кнута
• Мастер-теорема[math]^\star[/math]
• List order maintenance[math]^\star[/math]

Персистентные структуры данных

• Персистентные структуры данных
• Персистентный стек
• Персистентная очередь
• Персистентный дек
• Персистентная приоритетная очередь

Приоритетные очереди

• Двоичная куча
• Биномиальная куча
• Фибоначчиева куча
• Левосторонняя куча
• Тонкая куча
• Толстая куча на избыточном счетчике
• Куча Бродала-Окасаки[math]^\star[/math]

Система непересекающихся множеств

• Наивные реализации
• Списки с весовой эвристикой
• Реализация с помощью леса корневых деревьев
• СНМ с операцией удаления за О(1)[math]^\star[/math]

Поисковые структуры данных

• Упорядоченное множество
• Дерево поиска, наивная реализация
• АВЛ-дерево
• 2-3 дерево
• B-дерево
• B+-дерево
• Красно-черное дерево
• Декартово дерево
• Декартово дерево по неявному ключу
• Splay-дерево
• Взвешенное дерево
• Tango-дерево[math]^\star[/math]
• Рандомизированное бинарное дерево поиска
• Дерево ван Эмде Боаса
• Список с пропусками
• Fusion tree[math]^\star[/math]
• Сверхбыстрый цифровой бор
• Rope[math]^\star[/math]
• AA-дерево[math]^\star[/math]
• Техника частичного каскадирования [math]^\star[/math]
• Centroid decomposition [math]^\star[/math]

Запросы на отрезках

Корневая эвристика

• Статистики на отрезках. Корневая эвристика
• Корневая декомпозиция с операциями: get, insert, erase
• Алгоритм Мо

Дерево отрезков

• Дерево отрезков. Построение
• Реализация запроса в дереве отрезков сверху
• Реализация запроса в дереве отрезков снизу
• Несогласованные поддеревья. Реализация массового обновления
• Многомерное дерево отрезков
• Сжатое многомерное дерево отрезков

Дерево Фенвика

• Дерево Фенвика
• Встречное дерево Фенвика
• Дерево Фенвика для некоммутативных операций
• Многомерное дерево Фенвика

Задача о наименьшем общем предке

• Сведение задачи LCA к задаче RMQ
• Сведение задачи RMQ к задаче LCA
• Метод двоичного подъема
• Решение RMQ с помощью разреженной таблицы
• Двумерная разреженная таблица
• Алгоритм Фарака-Колтона и Бендера (решение +/-1 RMQ с помощью метода четырех русских)
• Алгоритм Хьюи
• Heavy-light декомпозиция
• Алгоритм Шибера-Вишкина[math]^\star[/math]
• Алгоритм Тарьяна поиска LCA за O(1) в оффлайн[math]^\star[/math]
• Link-Cut Tree[math]^\star[/math]
• Rake-Compress деревья[math]^\star[/math]

Хеширование

• Хеш-таблица
• Разрешение коллизий
• Хеширование кукушки
• Идеальное хеширование
• Перехеширование
• Фильтр Блума
• Quotient filter[math]^\star[/math]
• Универсальное семейство хеш-функций
• Расширяемое хеширование[math]^\star[/math]

Сортировки

Квадратичные сортировки

• Сортировка выбором
• Сортировка пузырьком
• Сортировка вставками

Сортировки на сравнениях

• Сортировка Шелла[math]^\star[/math]
• Сортировка кучей
• Быстрая сортировка
• Сортировка слиянием
• Cортировка слиянием с использованием O(1) дополнительной памяти
• Терпеливая сортировка[math]^\star[/math]
• Timsort[math]^\star[/math]
• Smoothsort[math]^\star[/math]
• Теорема о нижней оценке для сортировки сравнениями

Многопоточные сортировки

• Многопоточная сортировка слиянием[math]^\star[/math]
• PSRS-сортировка[math]^\star[/math]

Другие сортировки

• Поиск k-ой порядковой статистики
• Поиск k-ой порядковой статистики за линейное время
• Поиск k-ой порядковой статистики в двух массивах[math]^\star[/math]
• Сортировка подсчетом
• Цифровая сортировка
• Карманная сортировка
• Сортировка Хана[math]^\star[/math]
• Задача флага Нидерландов[math]^\star[/math]
• Блинная сортировка[math]^\star[/math]

Сортирующие сети

• Сортирующие сети
• Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
• Сортирующие сети для квадратичных сортировок
• Сортировочные сети с особыми свойствами[math]^\star[/math]
• Сеть Бетчера

Алгоритмы поиска

• Целочисленный двоичный поиск
• Поиск в матрице[math]^\star[/math]
• Вещественный двоичный поиск
• Троичный поиск
• Поиск с помощью золотого сечения
• Интерполяционный поиск
• Метод Фибоначчи[math]^\star[/math]

Динамическое программирование

Классические задачи динамического программирования

• Кратчайший путь в ациклическом графе
• Задача о числе путей в ациклическом графе
• Задача о расстановке знаков в выражении
• Задача о порядке перемножения матриц
• Задача о наибольшей общей подпоследовательности
• Задача о наибольшей возрастающей подпоследовательности
• Быстрый поиск наибольшей возрастающей подпоследовательности*
• Задача коммивояжера, ДП по подмножествам
• Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
• Задача о рюкзаке

Способы оптимизации методов динамического программирования

• Метод четырех русских для умножения матриц
• Применение метода четырех русских в задачах ДП на примере задачи о НОП[math]^\star[/math]
• Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
• Meet-in-the-middle[math]^\star[/math]
• Convex hull trick

Другие задачи

• Задача о расстоянии Дамерау-Левенштейна[math]^\star[/math]
• Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
• Задача о наибольшей подпоследовательности-палиндроме
• Задача о наибольшей общей возрастающей последовательности[math]^\star[/math]
• Задача о наибольшей общей палиндромной подпоследовательности[math]^\star[/math]
• Динамическое программирование по профилю[math]^\star[/math]
• Динамика по поддеревьям

Связь между структурами данных

• Связь между структурами данных