Algo 2014 2

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

• Копелиович Сергей (burunduk30@gmail.com, vk.com/burunduk1)

• Колганов Роман (roman.kolganov@gmail.com, vk.com/rokolgan)

• Мишунин Александр (alexander.mishunin@gmail.com, vk.com/amishunin)

Информация

Деление на группы

Результаты практики

Дедлайны:

• практика: 8 дней (дедлайн в среду в 23:59)
• теория: 6 дней (дедлайн в понедельник в 23:59), после этого можно до вторника 23:59 исправлять замечания.

Лекции

Билеты к коллоквиуму

Билеты к коллоквиуму (новая версия)

Конспект (набранный силами студентов)

• 02.10 (вторник) BST
• 02.17 (вторник) BST
• 02.21 (суббота) Дерево отрезков
• 02.24 (вторник) Двухмерные деревья, ScanLine
• 03.03 (вторник) RMQ & LCA
• 03.04 (среда) Функции на путях дерева, MST за O(E)
• 03.10 (вторник) Heavy-Light-Decomposition, Euler-Tour-Trees, LA
• 03.18 (среда) Паросочетания-1
• 03.24 (вторник) Потоки-1
• 03.25 (среда) Паросочетания-2 и раскраски
• 03.26 (четверг) Потоки-2 (LR, Диниц)
• 04.07 (вторник) Потоки-3 (mincost, Венгерка) Конспект от Andrew Goldberg по потокам и mincost тоже
• 04.08 (среда) Потоки-4 (preflow-push, global cut) Конспект от Burunduk1 про preflow-push дополненная версия
• 04.14 (вторник) Строки-1 (КМП, Z, Боер-Мур, Хеши, LCP)
• 04.15 (среда) Строки-2 (алгоритм Манакера, дерево палиндромов)
• 04.21 (вторник) Строки-3 (бор, суффиксное дерево, Ахо-Корасик)
• 04.22 (среда) Строки-4 (Укконен)
• 04.28 (вторник) Строки-5 (Cуффиксный массив)
• 04.29 (среда) Хеширование

Домашние задания

Быстрое считывание в c++

Быстрая аллокация памяти в c++

Решения и условия контестов

• 11 февраля Контест: результаты условия. Теор задачи: AVL, treap, неявный ключ.

• 18 февраля Контест: результаты условия. Теор задачи: STL, BST, RB, B, AA, Persistent.

• 25 февраля Контест: результаты условия. Теор задачи: Дерево отрезков, ScanLine, 2D-деревья.

• 2 марта Контест: результаты условия. Специальный контест про 2D деревья.

• 4 марта Контест: результаты условия. Теор задачи: LCA, RMQ, Euler Tours.

• 11 марта Контест: результаты условия. Теор задачи: Heavy-Light, Euler Tour Trees, задачи на деревьях.

• 18 марта Контест: результаты условия. Теор задачи: Паросочетания.

• 25 марта Контест: результаты условия. Теор задачи: Потоки.

• 8 апреля Контест: результаты условия. Теор задачи: Mincost Потоки.

• 15 апреля Контест: результаты условия. Теор задачи: Строки: база.

• 22 апреля Контест: результаты условия. Теор задачи: Строки: бор и палниндромы.

29 апреля -- суфф. структуры

6 мая -- битовое сжатие + NP-трудные задачи

13 мая -- день Гаусса

20 мая -- день Фурье

29 мая -- теория чисел