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

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

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

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

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

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

• Краткий обзор курса
• Хэширование
• Универсальные хэш функции: Часть 1 и Часть 2
• Совершенные хэш таблицы
• Хэш таблицы применяемые на практике
• Разбор одной задачи про сравнение двух множеств
• Фильтры Блума: Часть 1 и Часть 2
  
• Биномиальные коэффициенты
• Балансировка нагрузки — «the power of two choices»: Часть 1, Часть 2 и Часть 3
• Вероятности больших уклонений. Границы Бернштейна, Чернова и Хёфдинга.
  • Конспект по-английски: TailBounds.pdf
• 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