1. Скидки и обозначения
    1. Нужно сдать 19 задач. Это обязательно. Это ДОПУСК.
    2. В некоторых билетах есть пометка "bonus:". Все, что следует после нее, НЕ нужно рассказывать тем, кто сдал >= 25 задач.
    3. Запись [O(n), O(logn)] означает, что время, требуемое на предподсчет, = O(n), после предподсчета на 1 запрос мы умеем отвечать за O(logn).
  2. Графы - база
    1. dfs (время работы, реализация, док-во корректности)
    2. bfs (время работы, реализация, док-во корректности)
    3. ford-bellman, реализация тремя циклами, реализация с break-ом, реализация с очередью (время работы, реализация, bonus: док-во корректности последней реализации)
    4. floyd (время работы, реализация, bonus: док-во корректности)
    5. поиск отрицательного цикла (любой из двух вариантов - или через Флойда, или через Форда-Беллмана, bonus: док-во корректности)
    6. MST (Прим, Краскал) (время работы, bonus: док-во корректности)
  3. Игры
    1. Игры на ацикличных графах = динамическое программирование. O(E). LOSE/WIN, максимизировать/минимизировать число ходов.
    2. Ретроанализ, игры на графах с циклами. O(E). LOSE/WIN/DRAW, максимизировать/минимизировать число ходов.
    3. Функция Гранди. Способ подсчета за O(E). Применение. Доказательство LOSE/WIN. bonus: Доказательство XOR-а.
    4. Функция Смита. Способ подсчета за O(EsqrtE). Доказательство LOSE/WIN/DRAW. bonus: Доказательство XOR-а.
  4. Перебор
    1. Метод ветвей и границ. Отсечение по ответу. Меморизация состояний.
    2. Меморизация: проблемы в случае решения задачи "поиск кратчайшего по весу пути". Решение проблемы.
    3. Связь перебора и жадности. Что лушче? Сортировка ребер в переборе. Выбор первых K ребер. Вещественное K. Зачем это нужно (идея с первыми K ребрами)?
    4. Iterative Deepening. Связь dfs-а и bfs-а. Почему dfs + Iterative Deepening работает не дольше bfs-а?
    5. Автоматический подбор параметров. Iterative Increasing K в билете выше "Выбор первых K ребер".
  5. Приближенные методы
    1. Локальные оптимизации. Оптимизация произвольной функции f : AnySpace → R. Оптимизация для задачи коммивояжера.
    2. Отжиг. Сам процесс. Отличие от локальных оптимизаций. На примере f : R → R. bonus: На примере задачи "ограничить на плоскости max число точек веревкой длины L".
    3. bonus: Генетический алгоритм (мутации, скрещивание, отличие от Отжига и Локальных оптимизаций)
  6. Вероятностыне алгоритмы
    1. Las-Vegas (про самое часто встречающееся число, про подобные прямоугольники, про арифметическую прогрессию + bonus: во всех трех задач оценка и док-во времени работы)
    2. Monte-Karlo (собственно метод, bonus: оценка относительной и абсолютной погрешности)
    3. Каргер-Штейн (собственно метод, оценка времени работы O(N4*log), улучшение, bonus: оценка времени работы O(N2*log2))
  7. Коммивояжер
    1. Док-во невозможности r-приближения задачи коммивояжера в графе, в котором не выполняется неравенство треугольника при P != NP (сведение к задаче про гамильтонов цикл)
    2. MST x 2, объянение, почему на практике погрешность меньше теор. оценок, bonus: MST x 3/2 (алгоритм Кристофилдса)
    3. Nearest (просто описание аллгоритма). bonus: док-во того, что Nearest не хуже построения MST Примом.
    4. Локальные оптимизации для Коммивояжера (собственно хотя бы 2 локальных оптимизации, док-во конечности процесса, поиск очередной оптимизации за O(N))
  8. Двудольные графы
    1. Паросочетание, контролирующее множество, независимое множество (определения, как соотносятся их размеры)
    2. Лемма о дополняющем пути (и алгоритм поиска паросочетания за O(VE), который из нее следует).
    3. Лемма Холла (лемма о девушках). Формулировка. bonus: Док-во.
    4. Алгоритм Куна (отличие от базого алгоритма, bonus: док-во).
    5. Алгоритм Хопкрофта-Карпа за O(EsqrtV), bonus: док-во времени работы
    6. Раскраска ребер двудольного графа в max Degee цветов.
    7. Покрытие ацикличного графа min числом цепей (сведение к паросочетанию в двудольном графе).
    8. Теорема Дилворта. Формулировка. bonus: Док-во неравенств в обе стороны.
  9. Раскраски
    1. Теорема Брукса (про вершины, формулировка, док-во)
    2. Теорема Визинга (про ребра, только формулировка)
    3. Алгоритм раскраски вершин планарного графа в 6 цветов.
  10. Потоки
    1. Поток, разрез (определение,)
    2. Теорема Форда-Фалкерсона (max F = min C)
    3. Алгоритм Эдмондса (поиск в ширину, bonus: док-во времени работы O(VE2))
    4. Алгоритм Масштабирования потока (bonus: док-во времени работы O(E2log))
    5. Алгоритм Диница (bonus: док-во времени работы O(VE2))
    6. Вершинные поток и разрез. Поток и разрез (реберные и вершинные) в неорграфе.
    7. MinCost поток. Отсутствие отрицательных циклов.
    8. Лемма о дополняющем пути для MinCost потока.
    9. Дейкстра с потенциалами.
    10. Задача о назначениях, транспортная задача (формулировки задач, сведение их к mincost потоку)
    11. [L,R] потоки (решение mincost потоком, решение обычным потоком)
    12. Алгоритм Штор-Вагнера (собственно алгоритм, док-во времени работы O(V3), BigBonus: док-во корректности)
  11. Декартовы деревья
    1. Дерево по явному ключу. Операции Split и Merge.
    2. Операции с деревом по явному ключу: Insert, Delete, K-th, Add(L, R), GetSum(L, R) (1) Выразить эти операции через Split и Merge (2) реализовать их независимо.
    3. Дерево по неявному ключу. Add(L, R), GetSum(L, R), Reverse(L, R), Insert(i), Delete(i) (что из этого умеет дерево отрезков, что нет?)
    4. Построение за O(N) дерева по неявному ключу
  12. RSQ, RMQ, Деревья отрезков
    1. RSQ: Неменяющийся массив [O(n), O(1)]
    2. RMQ: Неменяющийся массив [O(n), O(logn)], Sparse table [O(nlogn), O(1)]
    3. RSQ: Меняющийся массив, дерево Фенвика [O(n), O(logn)], собственно дерево, преимущество над деревом отрезков, bonus: док-во корректности
    4. RSQ, RMQ: Меняющийся массив, дерево отрезков [O(n), O(logn)], преимущество над деревом Фенвика.
    5. Прибавление и присваивание на отрезке (в дереве отрезков, время на 1 операцию = O(logn)).
    6. RSQ и RMQ на неменяющейся матрице [O(n2), O(1)] для RSQ и [O(n2log2n), O(1)] для RMQ.
    7. RSQ и RMQ на меняющейся матрице, 2D деревья отрезков и Фенвика [O(n2), O(log2n)].
    8. Квадродерево на матрице [O(n2), O(n)]. Преимущество над 2D деревом отрезков, bonus: док-во времени работы.
  13. 2D-запросы и деревья
    1. 2D дерево отрезков (дерево строится на N точках, [O(NlogN), O(log2N)]. Использует O(NlogN) памяти
    2. КД-дерево [O(NlogN), O(sqrtN)], использует O(N) памяти. Преимущество над 2D деревом отрезков (не память). bonus: Док-во времени работы.
    3. Дерево отрезков декартовых деревьев (на примере задачи "сколько чисел на отрезке [i,j] имеют величину от L до R").
  14. LCA, Функции на путях дерева
    1. Разбиение путия дерева через LCA на 2 вертикальных, Offline и Online задачи.
    2. Offline поиск LCA (алгоритм Тарьяна, O(n*), собственно алгоритм, рассказ про СНМ, bonus: док-во корректности работы)
    3. 2 метода Online поиска LCA (двоичный подъем [O(nlogn), O(logn)] и Эйлеров обход дерева [O(n), O(logn)] а также [O(nlogn), O(1)] с помощью SparseTable)
    4. Веса ребер дерева не меняются, RSQ и RMQ (RSQ = [O(n), O(1)] + LCA, RMQ = [O(n), O(logn)] + LCA).
    5. Веса ребер дерева меняется, RSQ за [O(n), O(logn)] (Эйлеров обход + фишечка)
    6. Покрытие дерева путями, сведение запроса на пути к 2D запросу. Решение задач RMQ и RSQ за [O(n), O(log2n)]
  15. Численные методы
    1. Бинарный поиск (поиск корней функции, поиск числа в массиве)
    2. Троичный поиск (связь с двоичным поиском и производной)
    3. Градиентный спуск, случайный поиск, метод Ньютона (в R, в Rn). Выбор направления, выбор расстояния.
    4. Усовершенствованные поиски для f : R → R (2 варианта, основная мысль = разделить отрезок на ~100 частей )
    5. Поиск вещественных корней многочлена. Время работы = O(N2log)
  16. Теория чисел
    1. Решето Эратосфена = O(NloglogN), описание алгоритма. bonus: док-во времени работы.
    2. Тест Ферма, тест Миллера-Рабина. O(logN). Док-во корректности отсечений.
    3. Эвристика Полларда. O(N1/4). bonus: Док-во времени работы.
  17. Cтроки
    1. Полиномиальный хэш от строки. А также подсчет хэша от подстроки, как суммы на отрезке.
    2. Хэштаблицы со списками и с открытой адресацией. Добавление. Удаление. Поиск.
    3. bonus: Коллизии у полиномиальных хэшей и хэш-таблицы. Оценка вероятности коллизий сверху.
    4. Задачи: Поиск слов в тексте, наибольшая общая подстрока, наибольший подпалиндром (все они решаются хэшами за O(NlogN)).
    5. Суффиксный массив хэшами за O(Nlog2N), сравнение хэшами строк на больше меньше. LCP за O(NlogN).
    6. Суффиксный массив цифровой сортировкой за O(N2)
    7. LCP для суффиксного массива за O(N). Алгоритм Касаи для суффиксов. bonus: Случай циклических сдвигов.
    8. Бор. Суф.дерево. Способы хранения бора (массив, список, дерево поиска, хэш-таблица, общая хэш-таблица для всех вершин).
    9. Сжатый бор, сжатое суффиксное дерево, получение из суф.массива с LCP за O(N)
    10. Алгоритм Укконена за O(N). Сам алгоритм. bonus: док-во времени работы.
    11. Алгоритм Ахо-Корасика. Сам алгоритм. (1) построение полного автомата next[vertex, char] (2) версия с линейной памятью, bonus: док-во времени работы в (2).
  18. Паросочетания в произвольном графе
    1. Лемма Татта-Берджа. Формулировка. bonus:. Док-во.
    2. Теорема о дополняющем чередующемся пути. bonus:. Док-во.
    3. Алгоритм Эдмондса (сжатие соцветий). Реализация за O(V4). bonus: док-во корректности работы.
    4. Рандомизированный алгоритм (на основе алгоритма построения паросочетания в двудольном графе)
  19. Матроиды
    1. Определение. Алгоритм Радо-Эдмондса. bonus: Док-во.
    2. Графовый матроид (определение, док-во того, что это матроид, алгоритм, который из этого следует)
    3. Трансверсальный матроид (паросочетания) (определение, док-во того, что это матроид, алгоритм, который из этого следует)
    4. Векторный матроид (определение, док-во того, что это матроид, алгоритм, который из этого следует)
  20. Планарные графы
    1. Теорема Эйлера
    2. Укладка в R3, на сфере
    3. Док-во того, что K3,3 и K5 не планарны. Теорема Куратовского (только формулировка)
    4. Алгоритм Демукрона. Собственно алгоритм, bonus: разбор всех крайних случаев и док-во времени работы O(N2).
    5. Алгоритм разбиение графа на грани за O(E). Выделение внешних граней (смотрим на знак площади грани).
  21. 2-SAT
    1. Формулировка задач 2-SAT, 3-SAT.
    2. Жадное решение за O(VE), bonus: док-во.
    3. Решение за O(E). Док-во времени работы.
  22. Нейрон
    1. Задача классификации. Что такое нейрон. Разделение "хорошего" и "плохого" на >= 1 и <= t.
    2. Обучение Нейрона с помощью Л.П (если все неравенства разрешими, если не все разрешимы - 2 метода = наращивать, или удалять лишние)
    3. Обучение Нейрона с помощью Градиентного спуска.
    4. Решение задачи "Кто автор этого стиха? Пушкин или Лермонтов?" (изменяем пространство объектов)
    5. Simplex метод. bonus: Реализация Simplex метода.