Дополнительные главы алгоритмов, часть 1

Санкт-Петербург, осень 2019

Описание

Это курс по алгоритмам для тех, кто уже что-то знает про алгоритмы. Мы постараемся поглубже разобраться как работают основные алгоритмы и структуры данных, а также изучим несколько алгоритмов посложнее.

Практика по курсу будет разбита на две части: решение теоретических задач и задач на программирование.

Для начала прохождения курса вы должны знать следующие темы:

  • Анализ времени работы алгоритмов, амортизационный анализ
  • Базовые структуры данных: двоичная куча, дерево отрезков, дерево поиска
  • Базовые алгоритмы на графах: обход в глубину, обход в ширину
  • Базовые алгоритмы на строках: КМП, хеши

Примерное содержание курса:

  • Cтруктуры данных: кучи, дерево отрезков, дерево поиска
  • Запросы на деревьях
  • Декомпозиция графа
  • Кратчайшие пути в графах
  • Игры на графах
  • Потоки, паросочетания
  • Алгоритмы на строках
  • Быстрое преобразование Фурье

Оценка будет складываться из:

  • Теоретические задачи (50%)
  • Задачи на программирование (50%)

Преподаватели

Список лекций

1. Кучи
  • Левосторонняя куча
  • Биномиальная куча
  • Фибоначчиева куча
2. Дерево отрезков
  • Дерево отрезков, отложенные операции
  • Метод заметающей прямой
  • Персистентное дерево
4. LCA и RMQ
  • Двоичные подъемы
  • Сведение LCA к RMQ
  • Решение RMQ(+-1) за O(1) с предподсчетом за O(n)
  • Сведение RMQ к LCA
  • Двоичные подъемы + лесенки
  • Микро-макро эвристика
5. Heavy-Light декомпозиция, Link-cut дерево
  • Heavy-Light декомпозиция
  • Link-cut дерево
  • O(log n) со Splay деревом