1. Понятие алгоритм, примеры.
Временная сложность алгоритма.
Значение тета-, омега-, о- нотаций (большие и малые).
Свойства тета-, омега-, о- нотаций.
Пример с сортировками.
Основные функции и соотношение их между собой.
2. Структура данных куча.
Основные операции с кучей.
Очереди с приоритетами.
HeapSort.
Задачи на кучу: k-минимальных элементов.
Задача, сводимая к сортировке: найти i, j, что a[i]+a[j]=C для отсортированного массива a и заданного значения C.
3. Задача о сортировке.
Виды сортировок.
Теорема о нижней оценке числа сравнений для сортировок.
Сортировка слиянием.
Вывод оценки времени работы сортировки слиянием.
Приложения сортировок: (ломанная без пересечений, задача о сумме произведений).
Сравнительный анализ heapsort, mergesort и quicksort.
4. Быстрая сортировка.
Общий вид быстрой сортировки.
Варианты выбора опорного элемента.
Операция partition.
Анализ времени работы и используемой памяти.
Сравнение с HeapSort.
Алгоритм нахождения k-ой порядковой статистики.
5. Линейные сортировки.
CountSort, ее устойчивые модификации. RadixSort.
Примеры работы алгоритмов.
Оценки времени работы.
Приложения сортировок: задачи на сортировки (уникальные элементы, точка наибольшего наслоения отрезков).
Задача, сводимая к сортировке: объединение отрезков на прямой.
6. Хэш-функции.
Виды хэш-функций (по области применения).
Особенности каждого из видов.
Хэш-таблицы.
Основные операции с хэш-таблицами.
Время работы хэш-таблиц.
Методы разрешения коллизий (подробно).
Способы построения хэш-функций.
Пример: алгоритм Рабина-Карпа. Фильтр Блума.
7. Бинарный поиск.
Назначения и идея алгоритма.
Оценка количества действий.
Функции стандартной библиотеки C++, основанные на бинарном поиске.
Модификации: реализация first_index_of, last_index_of на основе стандартной библиотеки C++.
Задача об i-том числе для заданных отрезков.
Задача о катушках с нитками.
7. Реализации функций binary_search, index_first_of, index_last_of без использования
функций стандартной библиотеки C++, основанных на бинарном поиске.
Оптимизация бинпоиска для лучшего использования кэша процессора.
Вещественнозначный бинарный поиск.
Задача о деревнях и вышках сотовой связи.
Задача о сине-красных точках.
8. Троичный (тернарный) поиск.
Назначение и применимость.
Реализация.
Время работы.
Приложения и примеры: задача о поиске точке, минимизирующей взвешенную сумму растояний,
вероятностный поиск минимума/максимума на гладкой функции.
Задача о нахождении всех вещественных корней полинома.
9. Бинарные деревья поиска.
Наивная реализация вставки и поиска.
Оценка кол-ва действий в наивной реализации.
Примеры эффективных BST.
Рандомизированное бинарное дерево поиска.
Идея и его реализация (все базовые операции, включая delete).
10. Реализации операций lower_bound, upper_bound, kth_element, element_index для рандомизированного BST.
11. Динамические таблицы.
Примеры в современных языках.
Реализация основных операций.
Оценка времени работы.