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

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

• Хэширование

• Универсальные хэш функции

• Фильтры Блума

• Балансировка нагрузки — «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