Задача 1A. Лабораторная работа по алгоритму ≡

Максимальный балл:	1		Ограничение времени:	1 сек
			Ограничение памяти:	512 Мб

Условие

Требуется разработать и описать реализацию одного из выбранных алгоритмов. Реализация должна сопровождаться автоматическими тестами и пакетом в формате CATS. Описание должно содержать презентацию и реферат. Рекомендуется использовать систему подготовки документов TeX.

Список тем/алгоритмов

Число в скобках обозначает количество индивидуальных подтем/алгоритмов, по одному на человека.

Распределение тем

1. Сжатие цветков
2. Алгоритм Дийкстры с деревом Фибоначчи
3. Алгоритм A*
4. Укладка планарного графа
5. Алгоритм Эдмонда-Карпа
6. Изоморфизм деревьев
7. Динамическая связность оффлайн
8. Алгоритм D*
9. Алгоритм Голдберга-Тарьяна
10. Алгоритм Кристофидеса
11. Арифметическое кодирование
12. Алгоритм Лемпеля-Зива-Велча
13. Алгоритм PPM
14. Эффективная длинная арифметика
15. Алгоритм управления памятью: близнецы + SLAB
16. Дерево B/B+/B*
17. Дерево ван Эмде Боаса
18. Сбалансированные деревья: splay, AA, scapegoat, fusion, tango (2-3)
19. Пространственные деревья (2-3)
20. Алгоритм Укконена
21. Алгоритм Форчуна
22. Пересечение произвольных многоугольников
23. Триангуляция произвольных многоугольников
24. Дерево интервалов
25. Алгоритм Балабана
26. Выделение сообществ в социальных графах (2)

Темы, требующие дополнительного выбора/уточнения:

• Изоморфизм произвольных графов
• Планарная укладка произвольного графа
• Укладка графов в пространстве (?)
• Алгоритмы на кактусах (1-2)
• Сборщик мусора с поколениями

Формат входных данных

Отправьте ссылку на конкретный коммит в репозитории на Github, например

https://github.com/klenin/cats-main/commit/dce22c8348808959881ed7d6852c520a41e47c9a

В качестве среды разработки укажите Answer text.

В файле README укажите свои ФИО, вуз, направление подготовки, год, выбранный алгоритм, инструкции по сбору презентации и запуску автоматических тестов.

---