main page — CS 566 Efficient Algorithms
Unit 3: Fundamental Data Structures
This unit covers fundamental data structures:
- stacks, queues, and resizable arrays
- priority queues and binary heaps
- binary search trees
- hash tables
Learning outcomes
- Understand and demonstrate the difference between abstract data type (ADT) and its implementation
- Be able to define the ADTs stack, queue, priority queue and dictionary/symbol table
- Understand array-based implementations of stack and queue
- Understand linked lists and the corresponding implementations of stack and queue
- Know binary heaps and their performance characteristics
- Understand binary search trees and their performance characteristics
- Know high-level idea of basic hashing strategies and their performance characteristics
- Know the definition and examples of universal hashing.
Material
- slides
- Resizable Arrays (Amortized)
- Resizable Arrays (Deamortized)
- Binary Heaps
- Binary Search Trees (Unbalanced)
- Internal Path Length of Random BSTs
- Video 3-1 · transcript (2026-10-20, 28:00):
Stacks and Queues
- Video 3-2 · transcript (2026-10-20, 17:17):
Resizing Arrays
- Video 3-3 · transcript (2026-10-26, 11:39):
Resizable arrays deamortized & optimal space
- Video 3-4 · transcript (2026-10-26, 24:28):
Operations on Binary Heaps
- Video 3-4 · transcript (2026-10-26, 14:38):
Priority Queues and Binary Heaps
- Video 3-5 · transcript (2026-10-26, 22:35):
Symbol Tables and Binary Search Trees
- Video 3-6 · transcript (2026-10-27, 30:27):
Analysis of Random BSTs
- Video 3-7 · transcript (2026-10-27, 17:16):
Augmented BSTs
- Video 3-8 · transcript (2026-10-27, 6:20):
Balanced BSTs
- Video 3-9 · transcript (2026-10-27, 18:04):
Uniform Chaining Hashing Analysis
- Video 3-10 · transcript (2026-11-02, 5:42):
Chain Length Distribution
- Video 3-11 · transcript (2026-11-02, 41:19):
Universal Hashing
About this unit
The goal of this unit is twofold: (1) to bring you all on the same page regarding some basics usually covered in a first algorithms and data structures module such as Algorithms and Data Structures; (2) present some more advanced analyses and concepts often left out of such a module.
For the basic recap on stack, queues, binary heaps and binary search trees, if you have never seen the material before, the brief summary I give in the context of this module will not suffice to replace a full first algorithms module. You are highly encouraged to learn more in depth about these gems of computer science. The material below for further reading and sources will help you get started.
Further reading and sources
The sections on stacks, queues, and symbol tables follow the book
- Sedgewick, Wayne: Algorithms 4th ed (2011), Pearson
- Algorithms 4th ed booksite
The presentation of resizable arrays (including deamortized and optimal-space versions), priority queues and heaps is my own. The amortized analysis of the resizable arrays is spelled out in detail in my blog post:
The hashing summary follows our book, which (like Sedgewick and Wayne) has complete Java implementations of the discussed data structures.
For a lovely illustration of how memory management and pointers can be implemented conceptually, I recommend this: