Представяне по теми
-
Въведение в абстрактните типове данни.
Темата съдържа описание на основните абстрактни типове данни. Ще бъде обърнато само на необходимите операции, без да се конкретизира реализацията им.
Учебни материали: Абстрактни типове данни
-
Анализ на структури от данни.
Темата съдържа техники за анализиране на структури от данни. Ще бъдат разгледани подробно различни методи за амортизационен анализ:- Aggregate analysis.
- The accounting method.
- The potential method.
-
Червено черни дървета.
Темата съдържа основните операции на червено чернитее дървета, както и примери за тяхното приложение.
Учебни материали: Introduction to Algorithms - chapter 14.
-
AVL дървета.
Тема ще съдържа:
1. Техники за разширяване на структури от данни (Augmenting Data Structures). Ще бъдат разгледани Dynamic Ordered Statistics и Interval trees, като за основа ще бъде използвано червено-черно дърво (от минала лекция). Ще се разгледат няколко задачи в решенията на, които се използват разширените структури от данни.
Учебни материали: Introduction to Algorithms - chapter 15.
2. AVL дърво. Ще бъдат разгледани основните операции на AVL дърветата и тяхната ефективност спрямо червено черните дървета.
Учебни материали:
Лекция за AVL дървета
Визуално представяне на няколко вида балансирани дървета (Red-Black, AVL, Splay) -
Splay дървета.
Темата съдържа описание на този вид самобалансиращи се дървета. Ще бъдат разгледани основните операции над Splay дървета, както и тяхното приложение.
Учебни материали:
- http://www.eli.sdsu.edu/courses/fall96/cs660/notes/splay/splay.html
- http://www.eli.sdsu.edu/courses/fall96/cs660/notes/splayPerf/splayPerf.html*
* Материалът не влиза в теста.
-
B дървета.
Темата съдържа описание и реализация на Б-дърветата. Обрънато е внимание на брой дискови операции при резлизацията на структурата.
Учебни материали: Introduction to Algorithms - chapter 19
-
Trie.
-
Суфиксно дърво и суфиксен масив.
-
Патриции.
-
Декартово дърво.
-
Двоична пирамида.
-
Биномна пирамида.
Темата съдържа описание на биномни дървета и биномна пирамида.
Учебни материали: Introduction to Algorithms - chapter 20
-
Фибоначиева пирамида.
Учебни материали: Introduction to Algorithms - chapter 21
-
-
Skip List.
Учебни материали: http://www.csee.umbc.edu/courses/undergraduate/341/fall01/Lectures/SkipLists/skip_lists/skip_lists.html
-
Хеш таблици.
На http://en.wikipedia.org/wiki/Hash_table има достатъчно материали по темата. Разгледайте самата статия и следните препратки от See Also:
Bloom filter
Hash function
Hash list
Hash tree
За тези на които им е интересно може и Rabin-Karp string search algorithm -
Представяне на графи.
-
Представяне на дървета.
-
Представяне на други комбинаторни конфигурации.
-
Структури от данни за представяне на непресичащи се множества.
Учебни материали: Introduction to Algorithms, Chapter 22: "Data Structures for Disjoint Sets" -
Една задача от международната олимпиада по информатика за ученици.
Учебни материали: IOI2001 Competition Book (страница 38, задача Mobiles).