Основные ресурсы: память и время. О-символика. Примеры моделей вычисления: машина Тьюринга, RAM-машина. Сложность в среднем и худшем случаях.

Анализ учетных стоимостей операций. Банковский метод. Метод потенциалов: функция потенциала, истинные и учетные стоимости. Задача о двоичном счетчике.

Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ мультипликативной схемы для массива переменного размера с помощью банковского метода.

Стеки и очереди. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков.

Изменяемые (mutable) и неизменяемые (immutable) структуры данных. Структуры данных с хранением истории (persistent). Immutable-стек и immutable-очередь. Проблема множественного будущего при анализе учетных cтоимоcтей в persistent-структурах.

Задача сортировки. Разрешающие деревья. Нижняя оценка сложности в модели разрешающих деревьев. Сортировка сравнениями. Понятия устойчивости и in-place. Понятие о методе «разделяй и властвуй»: quicksort и mergesort. Алгоритм Quick-Sort. Процедура Partition, два варианта её in-place реализации. Примеры неудачного выбора опорных элементов. Рандомизированный выбор опорного элемента. Сложность Quick-Sort в худшем и среднем случаях. Глубина рекурсии в худшем и среднем случаях. Подробности реализации (кратко): сортировка вставками для малых подмассивов, удаление хвостовой рекурсии, медиана трёх, переход к другому виду сортировки. Алгоритм Merge-Sort. Слияние двух упорядоченных списков. Оценка сложности. Нерекурсивная реализация. Сортировка слиянием без использования дополнительной памяти: swap вместо присваивания, использование части массива в качестве буфера, слияние с перекрыванием входа и выхода. Сортировка подсчётом. Поразрядная сортировка.

Понятие очереди с приоритетом. Деревья со свойствами кучи. Почти полные бинарные деревья: нумерация вершин, навигация. Двоичная куча. Операция просеивания вниз и вверх. Реализация операций вставки, удаления и поиска минимума. Сложность операций. Поддержание указателей на элементы кучи. Преобразование произвольного массива ключей в кучу (операция Make-Heap), линейность времени работы. k-ичные кучи, зависимость сложности операций от выбора k.

Биномиальные (binomial), левацкие (leftlist) и косые (skew) кучи.

Слияние двух упорядоченных последовательностей различной длины. Теоретико-информационная нижняя оценка. Бинарный поиск от края (galloping). Нахождение порядковых статистик с помощью рандомизированной модификации алгоритма Quick-Sort. Линейность матожидания времени работы. Приближенные медианы. Выбор k-й порядковой статистики за линейное в худшем случае.

Хеш-функции. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей. Совершенные хеш-функции. Построение совершенной хеш-функции с помощью универсального семейства (размер m = O(n^2)). Двухуровневая хеш-таблица (размер m = O(n)).

Определение дерева поиска. Вставка и удаление элементов. Inorder-обход дерева. Красно-черные деревья: определение и основные свойства. Реализация операций вставки для красно-черного дерева. Splay-деревья. Операция splay: zig, zig-zig и zig-zag шаги. Реализация операций вставки, удаления, слияния и разделения для splay-деревьев.

Декартовы деревья (дучи). Единственность декартова дерева для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания высоты дучи. Операции слияния и разделения для дуч. Операции вставки и удаления элементов для дуч. Построение декартового дерева за линейное время при условии предварительной сортировки ключей. B+ деревья: определения и основные свойства. Операции поиска, вставки и удаления для B+ деревьев.

Статические задачи RMQ/RSQ (range minimum/sum query) и LCA (least common ancestor). Оптимальное решение задачи RSQ. Решение задачи LCA методом бинарного подъёма (O(NlogN) памяти, запрос за O(logN) времени). Сведение от задачи RMQ к задаче LCA: декартово дерево. Сведение задачи LCA к задаче ±1-RMQ: Эйлеров обход дерева. Простейшие алгоритмы для решения задачи RMQ: полная и разреженная таблицы ответов. Алгоритм Фарах-Колтона-Бендера для задачи ±1-RMQ: деление массива на блоки, предподсчёт для префиксов и суффиксов блоков, предподсчёт всех нормализованных блоков. Алгоритм Тарьяна для поиска LCA в режиме offline.

Системы непересекающихся множеств. Реализация с использованием леса. Ранги вершин, эвристика ранга. Логарифмическая оценка ранга через количество элементов. Рандомизированная ранговая эвристика. Эвристика сжатия путей. Оценка учетной стоимости операций (без доказательства).

Location problem, stabbing problem. Деревья интервалов. Сведение системы интервалов к двумерной задаче. Задача поиска точек в коридоре. Priority search tree. Задача поиска точек в прямоугольнике. Дерево отрезков по координате X, упорядоченные по Y списки точек в каждой вершине. Сложность O(n log n) для построения и O(log^2 n) для запроса. Уменьшение времени поиска до O(log n). Задача одновременного поиска в наборе упорядоченных списков. Fractional cascading.

Задача о динамической связности: вставки и удаления ребер, запросы о связности. Частный случай задачи для случая лесов. Деревья эйлеровых обходов: слияние и разделение.