Topic outline

  • 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 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"
                              • This topic

                                Topic 21

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

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