Курс: Advanced Data Structures

Главна

Тема 1

Въведение в абстрактните типове данни.

Темата съдържа описание на основните абстрактни типове данни. Ще бъде обърнато само на необходимите операции, без да се конкретизира реализацията им.

Учебни материали: Абстрактни типове данни

Тема 2

Анализ на структури от данни.

Темата съдържа техники за анализиране на структури от данни. Ще бъдат разгледани подробно различни методи за амортизационен анализ:

Aggregate analysis.
The accounting method.
The potential method.

Учебни материали: Introduction to Algorithms - chapter 18.

Тема 3

Червено черни дървета.

Темата съдържа основните операции на червено чернитее дървета, както и примери за тяхното приложение.

Учебни материали: Introduction to Algorithms - chapter 14.

Тема 4

AVL дървета.

Тема ще съдържа:
1. Техники за разширяване на структури от данни (Augmenting Data Structures). Ще бъдат разгледани Dynamic Ordered Statistics и Interval trees, като за основа ще бъде използвано червено-черно дърво (от минала лекция). Ще се разгледат няколко задачи в решенията на, които се използват разширените структури от данни.

Учебни материали: Introduction to Algorithms - chapter 15.

2. AVL дърво. Ще бъдат разгледани основните операции на AVL дърветата и тяхната ефективност спрямо червено черните дървета.

Учебни материали:
Лекция за AVL дървета

Визуално представяне на няколко вида балансирани дървета (Red-Black, AVL, Splay)

Тема 5

Splay дървета.

Темата съдържа описание на този вид самобалансиращи се дървета. Ще бъдат разгледани основните операции над Splay дървета, както и тяхното приложение.

Учебни материали:

* Материалът не влиза в теста.

Тема 6

B дървета.

Темата съдържа описание и реализация на Б-дърветата. Обрънато е внимание на брой дискови операции при резлизацията на структурата.

Учебни материали: Introduction to Algorithms - chapter 19

бонус: B Tree Задание

Тема 7

Trie.

Тема 8

Суфиксно дърво и суфиксен масив.

упражнение: Suffix Array Задание

Тема 9

Патриции.

Тема 10

Декартово дърво.

Тема 11

Двоична пирамида.

упражнение: Heaps Задание

Тема 12

Биномна пирамида.

Темата съдържа описание на биномни дървета и биномна пирамида.

Учебни материали: Introduction to Algorithms - chapter 20

Тема 13

Фибоначиева пирамида.

Учебни материали: Introduction to Algorithms - chapter 21

Тема 14

Tiered вектор.

Учебни материали: http://debian.fmi.uni-sofia.bg/~dobrev/tiered-vector.pdf

Тема 15

Skip List.

Учебни материали: http://www.csee.umbc.edu/courses/undergraduate/341/fall01/Lectures/SkipLists/skip_lists/skip_lists.html

Тема 16

Хеш таблици.

На http://en.wikipedia.org/wiki/Hash_table има достатъчно материали по темата. Разгледайте самата статия и следните препратки от See Also:
Bloom filter
Hash function
Hash list
Hash tree
За тези на които им е интересно може и Rabin-Karp string search algorithm

Упражение: Хештаблици Задание

Тема 17

Представяне на графи.

Тема 18

Представяне на дървета.

Тема 19

Представяне на други комбинаторни конфигурации.

Тема 20

Структури от данни за представяне на непресичащи се множества.

Учебни материали: Introduction to Algorithms, Chapter 22: "Data Structures for Disjoint Sets"

Тема 21

Откроено

Една задача от международната олимпиада по информатика за ученици.

Учебни материали: IOI2001 Competition Book (страница 38, задача Mobiles).

Упражнение Задание

Представяне по теми