1. Язык Си как исполнители алгоритмов.
2. Сложность по времени и по памяти. Верхние и нижние оценки.
3. O, Ω, Θ обозначения — формальные определения.
4. Задача о рюкзаке.
5. Коротко о P и NP, почему безнадёжно искать точное решение некоторых задач.
6. Индуктивные функции.

Переход от алгоритмов, заданных рекурсивно, к алгоритмам, заданным итеративно, с использованием стека на примере алгоритма Евклида.
1. Расширенный алгоритм Евклида.
2. Алгоритм быстрого возведения в степень.
3. Числа Фибоначчи. Вычисление через:
– рекурсию
– рекурсию с запоминанием
– итерацию
– возведение матрицы в степень
4. Доказательство нижних оценок на время работы алгоритма Евклида через числа Фибоначчи.
5. Переход от рекурсии к итерации с помощью стека.

Деревья рекурсии. Доказательство Θ-оценок для алгоритмов:
1. Алгоритм Карацубы.
2. Сортировка слиянием.
3. Поиск k-ой порядковой статистики (детерминированный алгоритм).
4. Алгоритм деления целых чисел.
Анализ рекуррентных соотношений. Доказательство основной теоремы о рекурсии.
* Теорема Akra-Bazzi об анализе рекуррентных соотношений для алгоритмов «разделяй и властвуй».

1. Детерминированный алгоритм поиска k-ой порядковой статистики.
2. Быстрая сортировка (вероятностный алгоритм). Оценка среднего времени работы.
3. Быстрая сортировка (детерминированный алгоритм).
4. Сортировка за линейное время:
– Сортировка подсчётами (Counting sort)
– Поразрядная сортировка (Radix sort)

Сортировки сравнениями. Модель разрешающих деревьев, доказательство нижних оценок.
1. Доказательство оценки Ω (nlogn) для сортировок сравнениями.
2. Бинарный поиск. Нижняя оценка на поиск элемента в отсортированном массиве.
3. Задача поиска F−1(x) для монотонной функции.
4. Потенциальные функции. Нижняя оценка на поиск второго максимума в массиве.
5. Оценки сложности различных алгоритмов сортировки:
– сортировка пузырьком
– сортировка вставками

1. Стеки и очереди.
2. Односвязные и двусвязные списки.
3. Heap (пираммда/куча):
– Heap sort
– Очередь с приоритетами на основе
4. Хэш-функции и хэш-таблицы.

1. Двоичные деревья поиска.
2. Определение красно-чёрных деревьев.
3. Балансировка красно-чёрных деревьев при добавлении и удалении вершины.
* Декартовы деревья.

Поиск в глубину. Связь времени открытия и времени закрытия вершин с правильными скобочными последовательностями. Переход от рекурсивного варианта алгоритма к итеративному с помощью стека.
Алгоритмы на основе поиска в глубину:
1. Топологическая сортировка.
2. Сильно-связные компоненты.
3. Поиск Эйлерова цикла.
4. Проверка на двудольность.
5. Поиск мостов.

1. Поиск в ширину.
2. Алгоритм Беллмана-Форда.
3. Алгоритм Дейкcтры.

1. Структура данных Union-Find.
2. Алгоритм Крускала.
3. Алгоритм Прима.
4. 2-приближённое решение задачи о Комивояжёре.
5. Вероятностный алгоритм поиска минимального разреза.

1. Сюжет с матрицами:
– возведения матрицы в степень — связь с количеством путей в графе
– смена кольца на (∨,∧) — проверка на связность и транзитивное замыкание
– смена кольца на (min,+) — поиск кратчайших путей
2. Алгоритм Флойда-Уоршелла.
3. Линейный алгоритм поиска кратчайших расстояний в топологически сортированном графе.
4. Задача о наибольшей возрастающей подпоследовательности.
5. Задача о расстоянии редактирования (Edit distance).

1. Динамическое программирование сверху и снизу: рекурсия и индукция.
2. Поиск выигрышных стратегий в конечной игре.
3. Алгоритм для дискретной задачи о Рюкзаке.
4. ε-приближённый алгоритм для дискретной задачи о Рюкзаке.