Vol 2: Data Structures and Algorithms

Arrays, hash tables, and trees suit different operations. This volume uses invariants to check correctness and complexity to compare costs. With ten elements, almost everything looks fast; add a few zeros and the differences become harder to miss.

Prerequisites

• Be able to write loops, functions, and recursion in one language and follow array accesses. Use Programming Basics to fill gaps.
• Know logarithms, sums, and elementary induction. Consult Mathematical Foundations for proof methods as needed.

Coverage

Chapter 1 establishes cost analysis. Chapters 2 through 8 cover data structures and graphs, Chapters 9 through 14 compare algorithms, and Chapter 15 adds structures for specific query needs.

Chapter 1

• 1.1 What Is Complexity?
• 1.2 Common Complexity Analysis
• 1.3 Asymptotic Bounds, Recurrence Relations, and Amortized Analysis

Chapter 2

• 2.1 Arrays
• 2.2 Linked Lists
• 2.3 Choosing Between Arrays and Linked Lists

Chapter 3

• 3.1 Stacks: Last In, First Out
• 3.2 Queues: First In, First Out
• 3.3 Deques: Both Ends and Sliding Windows

Chapter 4

• 4.1 Hash Table Basics
• 4.2 Hash Collisions and Resizing

Chapter 5

• 5.1 Binary Tree Structure and Recursion
• 5.2 Binary Search Trees: Insertion, Deletion, and Search
• 5.3 Tree Traversals: Recursion, Stacks, and Queues

Chapter 6

• 6.1 AVL Trees and Rotations
• 6.2 Red-Black Trees

Chapter 7

• 7.1 Heaps
• 7.2 Priority Queues

Chapter 8

• 8.1 Graph Representation: Put Vertices and Edges in Memory
• 8.2 Graph Search: From a Single Path to the Entire Network
• 8.3 Weighted Shortest Paths: Fewer Edges Can Cost More

Chapter 9

• 9.1 Basic Sorting: Bubble, Selection, Insertion
• 9.2 Advanced Sorting: Shell, Merge, and Divide-and-Conquer

Chapter 10

• 10.1 Quick, Heap, and Non-Comparison Sorts
• 10.2 Sorting Comparison: From Constraints to Selection

Chapter 11

• 11.1 Binary Search and Boundaries
• 11.2 String Matching

Chapter 12

• 12.1 Divide and Conquer
• 12.2 Backtracking

Chapter 13

• 13.1 Introduction to Dynamic Programming
• 13.2 Classic Dynamic Programming Problems

Chapter 14

• 14.1 Greedy Algorithms
• 14.2 Supplement: NP-Completeness and Reductions
• 14.3 Supplement: Amortized Analysis

Chapter 15

• 15.1 Advanced Data Structures Overview
• 15.2 Bloom Filters
• 15.3 Union-Find
• 15.4 Segment Tree

Outcomes

• Choose an implementation for lookup, insertion, sorting, or paths and state its input-size and memory constraints.
• Explain correctness with an invariant, induction, or exchange argument, then look for counterexamples at the boundaries.
• Distinguish worst-case, average, and amortized costs, and state how far a benchmark result can be generalized.

How to use this map

Start with complexity and linear structures, then move to trees, graphs, and algorithms. When reviewing an algorithm, work through an ordinary input and a boundary case by hand before checking the implementation. Correct complexity analysis does not stop an array index from going out of bounds.