Код от семинарите по "Структури от данни и програмиране", зимен семестър 2024/2025, спец. "Информатика"
- Тема 1 : Анализ на итеративни алгоритми. Нотации. Анализ на сложност и стабилност на сортиращи алгоритми (Bubble sort, Selection sort, Insertion sort).
- Тема 2 : Анализ на рекурсивни алгоритми. Merge sort. Quick sort. Сортиране в линейно време. Counting sort.
- Тема 3 : Увод в линейните структури от данни. Вектор (Динамичен масив). Сложност на операциите му. Амортизирана сложност. Locality. New expression, operator new, placement new. Delete, operator delete.
- Тема 4 : Свързан списък. Едносвързан списък (Singly Linked List). Двусвързан списък (Doubly Linked List). Сортиране на списъци.
- Тема 5 : Абстрактна структура от данни Deque. Стек. Опашка.
- Тема 6 : Увод в йерархичните структури от данни. Дървета. Двоични дървета. N-ични дървета.
- Тема 7 : Двоично наредено дърво за търсене (Binary search tree). Итератор за дърво.
- Тема 8 : Самобалансиращи се дървета. Видове. AVL + DoS (select и rank) дърво.
- Тема 9 : Двоична пирамида (Binary Heap). Приоритетна опашка (Priority queue). Сортиращ алгоритъм Heapsort (Пирамидално сортиране).
- Тема 10 : Set и Map. Хеш таблици. Справяне с колизии.
- Тема 11 : Алгоритми върху графи. Обхождания на графи (BFS и DFS). Търсене на цикъл в граф. Намиране на свързани компоненти. Топологична сортировка.
- Тема 12 : Тегловни графи. Най- къс път в тегловен граф. Алгоритми на Dijkstra и Bellman-Ford.
- Тема 13 : Тегловни графи. Минимално покриващо дърво. Алгоритми на Prim и Kruskal.
- Тема : Алгоритъм DSW - алгоритъм за балансиране по височина на двоично наредено дърво.
- Тема : Самобалансиращи се дървета - AVL дърво (поддържащо DoS).
- Тема : Биномна пирамида (Binomial Heap).
- Тема : Deque (Double-ended queue).
-
Тема : Слоест вектор (Tiered vector) - структура, поддържаща операциите индексиране, търсене на елемент, добавяне/премахване на елемент за времена съответно
$\Theta(1), \Theta(\log n), \Theta(\sqrt{n})$ .
- Тема : Intel intrinsics - оптимизация на Двоично търсене.
- Тема : Memory allocator.
- Тема : Timer scheduler - система за управление на еднократни и повтарящи се таймери.