I. Асимптотика
1. Определение O, Ω, ϴ, o, ω и базовые свойства
2. Переопределение o через lim
3. Утв: f ± o(f) = ϴ(f)
4. Утв: для полинома f, f = ϴ(n^{deg f})
5. Алгоритм merge sort. Анализ
6. Мастер теорема

II. Структуры данных
1. Структура данных массив
2. Структура данных связный список
3. Стэк, Очередь, Дэк и их реализации
4. Структура данных вектор (push_back за O(1) в среднем).
5. Бинарный поиск на инвариантах.
6. Бинарный поиск по ответу (пример задачи про стикеры)
7. Бинарная куча, операции min(), extMin(), add()

III. Сортировки
1. Построение кучи за O(n log n) и за O(n)
2. Heap sort
3. Квадратичные сортировки: Selection Sort
4. Квадратичные сортировки: Insertion sort
5. QuickSort (и оценка через матожидания числа сравнений).
6. Рандомизированный алгоритм поиска порядковой статистики (оценка T <= 9n)

IV. Сортировки
1. Алгоритм Median of Medians.
2. Нижняя оценка на число сравнение в (детермин.) сортировке сравнениями
3. CountSort
4. DigitSort
5. Концепция стабильности сортировки
6. Жадные задачи: выполнить всё до дедлайна
7. Min на очереди (два способа)

V. Динамическое программирование
1. Задача про полоску
2. Основные понятия: состояния, переходы, высиелние вперёд, назад, лениво.
3. Задача про путь вниз и вправо по матрице
4. Восстановление ответа в задачах на Дп
5. Задача о Рюкзаке (Subset sum)
6. Оптимизация памяти до линейной в рюкзаке (и восст. ответа).
7. Стоимостной рюкзак
8. Задача LCS

VI. Динамическое программирование
1. Задача про НВП за O(n^2), O(n log n)
2. Динамика по подотрезкам. Задача про наибольший подпалиндром
3. Динамика по подмножествам. Задача про Комивояжёра
4. Динамика по подмножествам. Гамильтонов путь. O(2^n n^2), O(2^n n)
5. Динамика по подмножествам. Гамильтонов цикл.

VII. Графы, dfs
1. Концепция графа.
2. Хранение графа (матрица смежности, список смежности, список рёбер).
3. (*) Хранение графа, мультисписок смежности.
4. Поиск в глубину.
5. Применения: разбиение на комп. связности; двудольность; существование пути
6. Поиск цикла в неор. графе.
7. Классификация рёбер в dfs (4 типа)
8. Классификация рёбер вслучае неор графа (2 типа и их обратные копии)
9. Поиск цикла в ор. графе
10. Топологическая сортировка (через сортировку tout)

VIII. Графы, dfs, bfs
1. Поиск мостов.
2. Поиск компонент сильной связности
3. Задача 2-SAT
4. Поиск Эйлерова пути (и цикла).
5. Bfs (самая простая версия)

XIX. Кратчайшие пути
1. Bfs c очередью
2. Bfs 1-k и 0-k. Восстановление пути.
3. Алгоритм Дейкстры. Общий алгоритм и доказательство.
4. Реализация алгоритма Дейкстры наивно и с кучей

XX. Кратчайшие пути 2
1. Алгоритм Bellman-Ford (O(VE) времени, O(V) памяти).
2. Утв: если нет отр цикла алгоритм не делает релаксации при d >= n
3. Восстановление ответа в случае если в графе нет отр циклов (и корректность)
4. Утв: если сущ отр цикл достижимый из s, то будет релаксация на шаге n
5. Floyd-Warshall. (O(V^3) времени, O(V^2) памяти)
6. Критерий проверки наличия отр. цикла.

XXI.
1. Лемма о разрезе
2. Алгоритм Прима. Доказательство и способы реализации
3. Алгоритм Краскала. Доказательство
4. DSU. Реализация small-to-large
5. DSU. Древесная реализация.
6. DSU. Ранговая эвристика. Оценка на log(n)
7. DSU. Эвристика сжатия путей. Оценка на log(n)

XXII. Строки.
1. Z-функция.
2. Применение Z-функции к поиску строки в строке
3. Pi-функция
4. Применение Pi-функции к поиску строки в строке
5. Бор. операции add, remove, find
6. Задача про lowerBound в боре
7. Поиск строки s в строке t только за O(s) памяти.

XXIII. Строки
1. Ахо-Корасик. Суфсылки и вычисление суфссылок.
2. Ахо-Корасик. Общий алгоритм. Понятие длинной суфсылки
3. (*) Ахо-Корасик. Замыкание до автомата
4. Хеш-Таблица с открытой адресацией
5. Хеш-таблица с закрытой адресацией
6. Полиномиальный хеш