Алгоритмы и структуры данных.

Первый семестр.

• Задачи на динамику.
• Жадные алгоритмы.
• Хэш функции и хеш таблица.

Второй семестр.

Алгоритмы на графах.

1. Обход графов.
   • ДФС,
   • БФС,
   • Топологическая сортировка,
   • Алгоритмы нахождения компонент сильной связности.
2. Поиск путей в графе.
   • Обходы графа для нахождения путей согласно поставленной задаче,
   • Построение транзитивного замыкания,
   • Алгоритм Форда-Беллмана.
3. Работа с двудольными графами.
   • Алгоритм Куна,
   • Построение Минимального остовного дерева с помощью Алгоритма Прима,
   • Нахождение минимального разреза.
4. Структуры данных для быстрых ответов на большое количество запросов.
   • Sparse table (разреженная таблица),
   • Дерево отрезков,
   • Метод двоичного подъема,
   • Декартово дерево по неявному ключу.
5. Элементы ООП.
   • Класс BigInteger (алгоритм Карацубы для произведения),
   • Геометрия (тренировка наследования).

Третий семестр

1. Алгоритмы для обработки строк.
   • Префикс-функция,
   • Алгоритм Манакера,
   • Алгоритм Ахо-Корасика.
2. Алгоритмы для обработки строк.
   • Суффиксный массив,
   • Алгоритм Касаи,
   • Алгоритм Укконена.
3. Геометрия.
   • Нахождение расстояния между отрезками в пространстве,
   • Построение выпуклой оболочки на плоскости (Алгоритм Эндрю),
   • Построение выпуклой оболочки в пространстве (Алгоритм Чана),
   • Сумма Минковского для проверки пересечения фигур на плоскости,
   • Сканирующая прямая для нахождения хотя бы одного пересечения в наборе отрезков,
   • Диаграмма Вороного (получение перпендикулярами к триангуляции Делоне, которую строим как проекции ребер выпуклой оболочки на парабаллоиде).
4. FFT и теория игр.
   • Проверка сжатия с помощью ФФТ,
   • Ответ на игру Терминатор с помощью ретроспективного анализа,
   • Ответ на игру с помощью теориему Шпрага-Гранди.