Графы, жадность (11 декабря 2013)

  1. Хаффман
    1. Not read Максимальная глубина дерева
    2. Реализация: декодирование, последний байт.
    3. Конец файла: доп. символ или длина файла.
    4. Как закодировать длину файла? 64 бита и UTF-8-style вариант
    5. Как закодировать дерево? Вариант с 10k-1 бит.
  2. MST
    1. Когда остовное дерево единственно?
    2. Как найти второе по весу минимальное остовное дерево?
    3. Сколько существует минимальных остовных деревьев?
    4. Сколько существует остовных деревьев? Матрица Киргхоффа.
  3. Война и мир
    1. Предподсчет и поиск слова: ищем строки в хеш-таблице
    2. Предподсчет и поиск подстроки: а тут уже нужны суф.структуры
  4. Форд-Беллман. Тестируем на случайном графе.
    1. Стандартная реализация за Θ(VE), V = 105, E = 2 × 105 [код]
    2. Реализация с break − 22 итерации [код]
    3. Реализация с очередью − 1.31 итерация [код]
    4. Потестим [gen]
  5. Отрезки на прямой
    1. Оставить минимальное количество отрезков на прямой так, чтобы объединение не изменилось
    2. Найти для каждого отрезка количество пересекающихся с ним
    3. Структура данных, решение событиями: += на отрезке, offline.
    4. Not read Дана система отрезков: любые два или непересекаются, или вкладываются. Построить дерево.
  6. 2-SAT
    1. Жадное решение за O(nm)
    2. Задача на 2-SAT: падающие прямоугольные деревья