Программа курса
1. Матрица смежности. Обход в глубину. Топологическая сортировка. Обход в ширину, очередь. Списки смежности, структура данных «вектор». Поиск эйлерова цикла в графе.
2. Арифметика: проверка на простоту, решето Эратосфена, разложение на множители, алгоритм Евклида. Расширенный алгоритм Евклида.
3. Куча. Быстрая сортировка. Нижняя оценка на количество действии в сортировке. Цифровая сортировка.
4. Бинарный поиск: по вещественным числам, ближайшего числа, по ответу.
5. Комбинаторика: понятие о перестановках, размещениях, сочетаниях. Генерация комбинаторных объектов. Схемы перебора. Генерация объекта по номеру, номера по объекту. Правильные скобочные последовательности.
6. Математическая прокачка: принцип Дирихле, индукция, инварианты и полуинварианты, теория чисел, графы, комбинаторные подсчёты, игры.
7. Основы языка C++. Основные операторы и типы данных. «С-способы» и «С++-способы». Польза от стандартной библиотеки: вектор, быстрая сортировка. Приоритеты операций. «Звёздочки, стрелочки и амперсанды.» Основы архитектуры компьютеров: память, регистры, стек, механизм вызова функций. Понятие о парадигмах программирования: процедурное программирование, объектно-ориентированное программирование, обобщённое программирование. Перегрузка операторов.
8. Вычислительная геометрия на плоскости: прямые и векторы, многоугольники и выпуклые оболочки, окружности.
9. Динамическое программирование: одномерная динамика, динамика на таблицах, рюкзак, динамика на подотрезках и подстроках, динамика по профилю.
10. Структуры данных: RMQ и RSQ, операция изменения на отрезке, хэш-таблицы, деревья поиска, контейнеры set и map. Декартово дерево: операции split и merge, реализация групповых операций, неявный ключ.
11. Поиск кратчайших расстояний: Дейкстра, Флойд, Форд—Беллман. Минимальное остовное дерево: алгоритм Прима, алгоритм Краскала, система непересекающихся множеств.
12. Тернарный поиск. Метод отжига.
13. Поиск подстроки в строке.
14. Квадродерево.
15. Поиск максимального потока: теорема Форда—Фалкерсона, алгоритм Эдмондса—Карпа. Поиск максимального паросочетания.
16. Игра «ним». Функция Шпрага—Гранди. «Кусторезка» на деревья и на произвольных графах.
17. Задача LCA: наивный алгоритм, двоичные подъёмы, алгоритм Тарьяна LCA-offline, сведение LCA к RMQ.
18. Быстрое преобразование Фурье. Применение: умножение длинных чисел, поиск подстрок по шаблону с вопросиками.