Проекти по Advanced Data Structures (0.9)

A: Изследване на структури.

Изследване на структура ще разбираме проектиране и реализация на множество тестове с цел да се определи поведението на дадена структура или да се сравнят няколко структури. Тестовете трябва да бъдат разнообразни и достатъчно големи. Средните тестове трябва да работят поне 30 секунди, за да се отчетат сложността на алгоритъма и константите. Необходимо е да се сравнят поведенията на структурите при произволни данни, както и при данни, при които се достига „най-лошият случай” за дадената структура, например сортирани стойности за двоично наредено дърво. Няма ограничение за сорс кода на структурите, дори е желателно той да бъде взет на готово, необходимо е единствено да цитирате мястото, където е публикуван.

Тестовете трябва да съдържат:

• 1-2 теста които изглеждат практични (подобни на начина по който би се използвала структурата обикновенно)
• 1-2 теста които се опитват да достигнат най лошия случай
• 1-2 теста които са произволно генерирани (но с различни характеристики).

Всеки тест трябва да има по 3 версии - малка, средна и голяма. Малката версия е тест при който предимствата на по-сложните структури от данни не личат (примерно операциите в масив с 4 елемента са по бързи околкото в двоично балансирано дърво). Голямата е версия, която цели да тества по-голямо натоварване (примерно за около 30 секунди). Средната версия е нещо между двете.

Необходимият брой тестове (с вариантите им) е поне 10. Ако искате можете да направите и повече. Вашата програма трябва да извежда кой тест пуска, и колко време е работил. При малките тестове, може да се наложи да ги пуска многократно (например 100 пъти) за да се получи някакво измеримо време (поне 1 секунда).

При желание, може да измерите и други характеристики, като например заета памет, максимална височина, брой реалокации или колизии (според структурата която се тества), стига това да не повлияе на бързодействието, което е главен обект на тестване.

1. Да се изследва поведението на двоично наредено дърво спрямо балансирано двоично наредено дърво. Да се намерят константите в сложностите на операциите. Необходимо е да се включат поне 3 реализации, като поне една е двоично наредено дърво и поне една е балансирано двоично наредено дърво.
2. Да се изследва поведението на червено черно дърво спрямо AVL дърво. Да се намерят константите в сложностите на двете структури. Необходимо е да се включат поне 3 реализации, като поне една е червено черно дърво и поне една е AVL дърво.
3. Да се изследва поведението на биномна пирамида спрямо фибоначиева пирамида. Да се намерят константите в сложностите на операциите.
4. Да се изследва поведението на Dynamic Ordered Statistics реализиран с червено черно дърво и Dynamic Ordered Statistics реализиран с AVL дърво. Да се намерят константите в сложностите на операциите.
5. Да се изследва поведението на Dynamic Ordered Statistics реализиран с балансирано двоично наредено дърво и Dynamic Ordered Statistics реализиран с tiered vector. Да се намерят константите в сложностите на операциите.
6. Да се изследва поведението на балансираните двоични наредени дървета и хеш таблиците. Да се намерят константите в сложностите на операциите. Необходими да е се включи поне по една реализация на балансирано двоично наредено дърво и поне две реализации на хеш таблица.
7. Да се изследват константите в сложностите на фибоначиевата пирамида, за поне 2 различни реализации.
8. Да се изследва поведението на Splay дървото спрямо балансирано двоично наредено дърво. Да се намерят константите в сложностите на операциите.
9. Да се изследва поведението на tiered vector при различни начални размери на опашките и различни множители. Да се намери емпирично оптималната стойност за границата, при която контейнера трябва да се свива. Да се намерят константите в сложностите на операциите.
10. Да се изследва поведението на суфиксен масив, спрямо суфиксно дърво. Да се намерят константите в сложностите на операциите.
11. Да се изследва поведението на 2 реализации на хеш таблица, при различни хеш функции.
12. Да се подберат няколко вероятностни реализации на множества (които дават false positive, но не и false negative) и да се сравни вероятността за грешка при тях, както и бързодействието им.

B: Реализация на структури.

Необходимо е да се реализира указаната структура. Желателно е типа данни да бъде generic (C++ templates) или абстрактен клас или интерфейс. Не се позволява използването на чужд сорс код. Трябва да има програма която демонстрира изоплзването операциите на вашата структура. В проектите, в които е указана конретна задача, тя може да се използва за тази цел. В противен случай трябва да реализирате нещо по ваш избор.

1. Да се реализира контейнер Dynamic Ordered Statistics като за основа се използва червено-черно дърво.
2. Да се реализира контейнер Dynamic Ordered Statistics като за основа се използва AVL дърво.
3. Да се реализира контейнер Б-дърво, който да работи с външни файлове (да не зарежда цялата структура в паметта). Операциите добавяне и изтриване трябва да се реализират само с едно минаване по дървото.
4. Да се реализира алгоритъма на Дейкстра с биномна пирамида (O(m + m * log n)).
5. Да се реализира алгоритъма на Дейкстра с фибоначиева пирамида (O(m + n * log n)).
6. Да се реализират LCA и RMQ с подготовка O(n) и заявка O(1).
7. Да се реализира контейнер Augmentable (разширяемо) червено-черно дърво За целта може да се ползват Function Objects (C++ templates), function pointers/delegates или interface-i/virtual функции.
8. Да се реализира контейнер Augmentable (разширяемо) AVL дърво. За целта може да се използват Function Objects (C++ templates), function pointers/delegates или interface-i/virtual функции.
9. Да се реализира библиотека с различни представяния на графи и дървета.
10. Да се реализира хеш таблица с отворено адресиране, поддържаща изтриване.

Всеки студент прави един проект A и един проект B. Възможно е една от тестваните структури от част A да е точно структурата която сте написали от B.