angeld55/data_structures_and_algorithms_fmi-1

Examples for the "Data structures and algorithms" course given by me (2021/22, winter semester) and "Data structures 2" course @ Faculty of Mathematics and Informatics, Sofia University

Теми от семинарите по "Структури от данни и програмиране", зимен семестър 2021/2022, спец. "Компютърни науки", поток 2, група 5

• Тема 1 (07.10.2021) : Анализ на итеративни алгоритми. Нотации. Анализ на сложност и стабилност на сортиращи алгоритми (Bubble sort, Selection sort, Insertion sort).
• Тема 2 (14.10.2021) : Анализ на рекурсивни алгоритми. Анализ на сложност и стабилност на сортиращи алгоритми (Merge sort, Quick sort).
• Тема 3 (21.10.2021) : Увод в линейните структури от данни. Вектор(Динамичен масив). Абстрактни структури от данни. Стек. Реализация на стек чрез динамичен масив. Задачи върху "Стек".
• Тема 4 (28.10.2021) : Свързан списък. Едносвързан списък (Singly Linked List). Двусвързан списък (Doubly Linked List). Опашка (Queue). Реализации на стек и опашка чрез едносвързан списък.
• Тема 5 (04.11.2021) : Задачи върху разгледаните до момента теми (Част 1).
• Тема 6 (16.11.2021) : Задачи върху разгледаните до момента теми (Част 2).
• Тема 7 (18.11.2021) : Итератори. Реазлизации на итератори: VectorIterator, SinglyLinkedListIterator, DoublyLinkedListIterator.
• Тема 8 (25.11.2021) : Увод в йерархичните структури от данни. Дървета. Двоични дървета.
• Тема 9 (11.12.2021) : Двоично наредено дърво (Binary search tree). Задачи върху двоични и двоично наредени дървета.
• Тема 10 (16.12.2021) : Графи. Видове графи. Представяния на графи. Алгоритми за обхождане (BFS/DFS) и приложенията им.
• Тема 11 (23.12.2021) : Алгоритъм за най- къс път в тегловен граф (Dijkstra). Алгоритъм за двуделност на графи. Подготовка за контролно 2.
• Тема 12 (06.01.2022) : Двоична пирамида (Binary Heap). Приоритетна опашка (Priority queue). Сортиращ алгоритъм Heapsort (Пирамидално сортиране).
• Тема 13 (15.01.2022) : Хеш таблица. Collision resolution strategies (CRS). Външно хеширане (Separate chaining). Вътрешно хеширане (Open addressing).

Структури от данни 2 - ФМИ

• Тема : Алгоритъм DSW - алгоритъм за балансиране по височина на двоично наредено дърво.
• Тема : Самобалансиращи се дървета - AVL дърво (поддържащо DoS).
• Тема : Биномна пирамида (Binomial Heap).
• Тема : Deque (Double-ended queue).
• Тема : Слоест вектор (Tiered vector) - структура, поддържаща операциите индексиране, търсене на елемент, добавяне/премахване на елемент за времена съответно O(1), O(lgn), O(sqrt(n)).