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
About this unit
This unit is a recap of topics that you will have previously seen in a first algorithms and data structures module, to bring you all on the same page.
In case you have never seen the material before, the brief summary I give in the context of this module will not suffice to replace such a 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.
Material
- slides
- Video 3-0 (2025-10-21):
§3.0 word-RAM vs Python & Java
- Video 3-1 (2025-10-21):
§3.1 ADTs, Stacks and Queues
- Video 3-2 (2025-10-21):
§3.2 Resizable arrays
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: