Topic outline

  • General

    Collapse all Expand all

  • Topic 1

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


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

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

  • Topic 2

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


    Темата съдържа техники за анализиране на структури от данни. Ще бъдат разгледани подробно различни методи за амортизационен анализ:
    • Aggregate analysis.
    • The accounting method.
    • The potential method.
    Учебни материали: Introduction to Algorithms - chapter 18.

  • Topic 3

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


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

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

  • Topic 4

    AVL дървета.


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

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

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

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

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

  • Topic 5

    Splay дървета.

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

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

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


  • Topic 6

    B дървета.


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

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

  • Topic 7

    Trie.

  • Topic 8

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

  • Topic 9

    Патриции.

  • Topic 10

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

  • Topic 11

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

  • Topic 12

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


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

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

  • Topic 13

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

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

  • Topic 14

    Tiered вектор.

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

  • Topic 15

    Skip List.

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

  • Topic 16

    Хеш таблици.

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

  • Topic 17

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

  • Topic 18

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

  • Topic 19

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

  • Topic 20

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

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

  • Topic 21

    Highlighted

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

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