Видеокурс по алгоритмам «Advanced Algorithms I»

Смотрите на YouTube канале: Advanced Algorithms

Курс в Computer Science Club по материалам видеолекций: видеокурс

Обзор базовых определений и результатов из теории вероятностей

Лекция по теории вероятностей на английском: Tutorial on Probability Theory

Рандомизированные алгоритмы

  • Краткий обзор курса
  • Хэширование
  • Универсальные хэш функции: Часть 1 и Часть 2
  • Разбор одной задачи с собеседования на работу
  • Фильтры Блума
  • Балансировка нагрузки — «the power of two choices»
  • Вероятности больших уклонений. Границы Бернштейна, Чернова и Хёфдинга
  • Permutation routing in the hypercube

Потоковые алгоритмы

  • Нахождение самого частого элемента в потоке
  • Алгоритм Misra–Gries
  • Count–Min Sketch
  • Подсчёт числа различных элементов в потоке
  • HyperLogLog

Онлайн алгоритмы

  • Задача о прокате лыж
  • Кэш LRU
  • Анализ LRU в модели «resource augmentation»

Динамические алгоритмы на графах

  • Ориентация ребер графа

Параметризованные алгоритмы

  • Введение в FPT алгоритмы
  • FPT алгоритм для задачи о самом длинном пути в графе
  • FPT алоритм для задачи о вершинном покрытии

Приближенные алгоритмы

  • Приближенный алгоритм для задачи о вершинном покрытии
  • Приближенный алгоритм для задачи о покрытии множествами

Линейное программирование

  • Введение в линейное программирование
  • Двойственность в линейном программировании
  • Условия Каруша – Куна – Таккера
  • Лемма Фаркаша и её физическая интерпретация
  • Доказательство леммы Фаркаша

Приложения линейного программирования

  • Минимальные разрезы и максимальные потоки в графах

Другие темы

  • Dimensionality reduction
  • Bourgain's Theorem
  • Cheeger's Inequality
  • Karger's algorithm
  • Principal component analysis