Browse chapters
Chapter 0
Programming foundations
Language and memory tools used throughout the data-structure notes.
- Read section
0.1 Pointers, memory, and structs
Review the C language tools that the course uses to explain data-structure behavior: pointers, malloc, typedef, and struct layout.
Chapter 1
ADT and operation semantics
From ADT contracts to stack/queue behavior and dictionary-style hashing operations.
- Read section
1.1 ADT operations: stack, queue, and function pointers
Build a precise ADT view of stacks, queues, and function-pointer-based operation dispatch in C data-structure implementations.
- Read section
1.2 Hash tables and collision strategies
Use dictionary operations, hash functions, collisions, and chaining to understand why hash tables trade ordered structure for fast average-case access.
Chapter 2
Lists and recursion
Recursive list contracts, head-tail reasoning, and representation-aware operation cost.
- Read section
2.1 Lists as recursive ADTs
Read lists as recursive head-tail ADTs, then compare iterative and recursive operation implementations.
Chapter 3
Complexity and sorting
Asymptotic growth, cost comparison, and sorting-oriented complexity reasoning.
- Read section
3.1 Complexity growth and algorithmic cost
Interpret asymptotic growth and compare algorithmic costs before implementing sorting or selection routines.
- Read section
3.2 Selection, quickselect, and linear-time sorting
Separate selection from full sorting, then use quickselect, counting sort, and radix sort to understand when extra structure improves complexity.
Chapter 4
Trees and BSTs
Binary tree traversal, reconstruction, and binary-search-tree operations.
- Read section
4.1 Binary tree traversal and reconstruction
Read recursive binary-tree structure through preorder, inorder, and postorder traversal, then reconstruct trees from sufficient traversal information.
- Read section
4.2 Binary search trees and core operations
Maintain the binary-search-tree ordering invariant through search, extrema, insertion, successor, and deletion operations, with costs measured by tree height.
Chapter 5
Graphs
Graph representations and traversals, minimum spanning trees, shortest paths, and topological ordering.
- Read section
5.1 Graph representations, DFS, and BFS
Compare adjacency matrices and lists, then trace DFS and BFS while maintaining correct frontier and visited-state invariants.
- Read section
5.2 Minimum spanning trees: Prim and Kruskal
Construct minimum spanning trees with Prim's and Kruskal's greedy choices while distinguishing the MST objective from shortest paths.
- Read section
5.3 Shortest paths and Dijkstra's algorithm
Use relaxation and settled-vertex reasoning to compute single-source shortest paths with Dijkstra's algorithm under nonnegative edge weights.
- Read section
5.4 Topological sorting of DAGs
Order the vertices of a DAG with Kahn's indegree process and DFS finishing times, using both methods to expose directed cycles.
Chapter 6
Heaps and greedy coding
Binary heaps, priority queues, Huffman coding, and heap-based multiway merging.
- Read section
6.1 Binary heaps and priority queues
Represent a complete binary tree in an array and maintain min-heap order through priority-queue operations and bottom-up construction.
- Read section
6.2 Huffman coding and heap applications
Build a prefix-free Huffman code by repeated minimum-frequency merges, then reuse the heap abstraction for efficient multiway merging.