Data Structure

Lecturer: Armen Kostanyan
Classes: 1 lecture, 1 practical class per week

Short Description

Nonlinear data structures (binary and binominal heaps, search trees, hash-tables, B-trees and disjoint-set systems) will be explored. We pay special attention to complexity estimates and applications. The implementation will be in C++.

Requirements

Background: The course requires
  • knowledge of basic data structures (array, linked list, stack, queues, priority queue),
  • Basic knowledge of C++ (data types, instructions, arrays, pointers, functions, classes, operator overloading)
  • knowledge of basic calculus
Homework:Weekly homework

Assessment

  • 10% participation
  • 40% homework
  • 25% first test
  • 25% second test

Textbooks

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001
  2. Robert Sedgewick. Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching. Addison-Wesley, 1999
  3. H. M. Deitel, P. J. Deitel. C++: How to program. Prentice Hall, 3rd edition, 2001.

    Content
    Lectures
    1. Introduction: Binary tree definition. Binary tree traversals(2 hours)
    2. Binary heap definition. Modeling of priority queue with a binary heap (2 hours)
    3. Binary search trees. Search, insertion, deletion.(4 hours)
    4. The concept of balanced binary tree. Red-Black Trees. Balancing after insertion and deletion of an element in red-black search tree.(4 hours)
    5. Augmenting data structure. Dynamic order statistics trees. Algorithms for finding the rank of an element and finding the element of the given rank.Interval trees.(4 hours)
    6. Hash tables: Open and closed hashing. Search, insertion and deletion operations. Complexity estimates(4 hours)
    7. Binomial Heaps: Operations with binomial heaps. Complexity estimates. (4 hours)
    8. B-trees. Search, insertion and deletion operations. Complexity estimates.(4 hours)
    9. Disjoint-Set Data Structures. Representation via list and a forest. Complexity estimates.(4 hours)

    Practical classes
    1. Implementation of a heap in C++ (2 hours)
    2. Implementation of a binary search tree in C++ (4 hours)
    3. Implementation of a red-black search tree in C++ (4 hours)
    4. Implementation of order statistics operations in red-black search tree in C++ (2 hours)
    5. Implementation of closed hash table in C++ (3 hours)
    6. Implementation of open hash table in C++ (3 hours)
    7. Implementation of binary heap in C++ (4 hours)
    8. Implementation of b-tree in C++ (4 hours)
    9. Implementation of disjoint set systems using lists in C++ (3 hours)
    10. Implementation of disjoint set systems using forests in C++ (3 hours)