версия 0.8

Проекти:

A1. Да се реализира контейнер червено-черно дърво ([1]: 14).

A2. Да се реализира контейнер AVL дърво ([4]).

A3. Да се реализира контейнер Б-дърво. Операциите добавяне и изтриване трябва да се реализират само с едно минаване по дръвото ([1]: 19).

A4. Да се реализира контейнер Splay дърво ([5]). Да се реализира контейнер Tiered Victor ([6]).

A5. Да се реализира контейнер фибоначиева пирамида.

A6. Да се реализира алгоритъма на Прим с двоична пирамида (О(m + m * log m)). Да се реализира алгоритъма на Крускал с Disjoint Sets Forest.

A7. Да се реализира алгоритъма на Дейкстра с биномна пирамида (O(m + m * log n)).

A8. Да се реализира LCA и RMQ със подготовка O(n) и заявка O(1).

Изборни проект:

A9. Да се реализира контейнер Augmentable (разширяемо) червено-черно дърво ([1]: 14, 15). За целта може да се използват Function Objects (C++ templates), function pointers/delegates или interface-i/virtual функции.

A10. Да се реализира контейнер Augmentable (разширяемо) AVL дърво ([1]: 15, [4]). За целта може да се използват Function Objects (C++ templates), function pointers/delegates или interface-i/virtual функции.

А11. Да се реализира контейнер Б-дърво, който да работи с външни файлове (да не зарежда цялата структура в паметта). Операциите добавяне и изтриване трябва да се реализират само с едно минаване по дръвото ([1]: 19).

А12. Да се реализират алгоритъмите на Прим и Дейкстра с фибоначиева пирамида.

Литература:

[1] Introduction to Algorithms (First Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

[2] Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology by Dan Gusfield

[3] The LCA Problem Revisited by Michael A. Bender and Martin Farach-Colton

[4] AVL Tree

[5] Splay Tree

[6] Tiered Vector