Advanced Data Structures

Lecture addressed to second year students of Computer Science. Here are the links to my lecture notes and lab work assignments.

I welcome your feedback to correct any typos/errors you may find in my lecture notes and related material. Check the latest versions of the lecture notes and related material

  1. Week 1: Lectures 1: Introduction. Binary search trees. Red-Black trees. Template files: BSTree.zip and RBTree.zip
  2. Week 2, Lecture 2: Disjoint set structures (slides). Amortized analysis (slides)
  3. Week 3, Lecture 3: Binomial heaps (slides)
    Lab work, template file: binoheap.zip
  4. Week 4: Computational geometry
  5. Week 5: More about mergeable heaps (slides).
    Programming labwork: kd-trees -- explanations, template files; written homework (here)
  6. Week 6: String matching. The finite automaton approach. The Aho-Corasick algorithm
  7. Week 7: Suffix trees. Applications. Slides
    Labwork
  8. Week 8: Sorting in linear and sublinear time. Sorting networks. Counting sort.
  9. Week 9: Data structures for symbolic computation.
    Homework
  10. Week 10: .
  11. Week 11: Binary heaps. Heapsort and Quicksort
    Homework
  12. Week 13: Summary.
    Last labwork (for those who wish to improve their grade for labwork activity)
  13. Week 14: Colloquium 2020: answers to the written tests A and B

References

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. The MIT Press. 1990.