Reference and Selective Reading
You do not need to read the source books front-to-back for this module. Use the concept pages and practice pages first. Open these local chunks only when you need alternate exposition, more worked examples, or a deeper exercise lane.
Source Roles
| Source | Role | Why it is here |
|---|---|---|
| The Algorithm Design Manual (Skiena) | Primary -- problem-driven | Best overall framing for "what algorithm do I pick and why" |
| Introduction to Algorithms (CLRS) | Primary -- proofs and bounds | Best for rigorous cost derivations, lower bounds, and amortized arguments |
| Algorithms (Sedgewick) | Selective support | Implementation-focused second pass and visual intuition |
| Grokking Algorithms | First-pass framing | Accessible warm-up on binary search, hashing, and quicksort |
| Competitive Programming | Exercise source | Practice-heavy reinforcement for heaps, hashing, and binary search |
Read Only If Stuck
Cluster 1: Comparison-Based Sorting and the Lower Bound
- CLRS: 2.1 Insertion Sort
- CLRS: 2.1 Insertion Sort (continued)
- CLRS: 2.3 Designing Algorithms (mergesort)
- CLRS: 7.1 Description of Quicksort
- CLRS: 7.2 Performance of Quicksort
- CLRS: 7.3 Randomized Quicksort
- CLRS: 8.1 Lower Bounds for Sorting
- Skiena: 4.5 Mergesort
- Skiena: 4.6 Quicksort
- Sedgewick: Elementary sorting
- Sedgewick: Quicksort
Cluster 2: Linear-Time and Specialized Sorting
- CLRS: 8.2 Counting Sort
- CLRS: 8.3 Radix Sort
- CLRS: 8.3 Radix Sort (continued)
- CLRS: 8.4 Bucket Sort
- Skiena: 4.1 Applications of Sorting
- Skiena: 4.2 Pragmatics of Sorting
- Skiena: 4.7 Distribution Sort
- Sedgewick: Radix sorting
- Sedgewick: External Searching
Cluster 3: Searching in Sorted and Unsorted Data
- Grokking Algorithms: Binary Search
- Skiena: 4.9 Binary Search and Related Algorithms
- Competitive Programming: 3.3.1 Interesting Usages of Binary Search
- CLRS: 9.1 Minimum and Maximum
- CLRS: 9.2 Selection in Expected Linear Time
- CLRS: 9.3 Selection in Worst-Case Linear Time
- Skiena: 3.1 Contiguous vs Linked Data Structures
- Skiena: Unsorted vs Sorted
- CLRS: 10.1 Simple Array-Based Data Structures
- CLRS: 10.2 Linked Lists
- Sedgewick: Elementary searching methods
Cluster 4: Hash Tables as a Dictionary Primitive
- Grokking Algorithms: Hash Tables
- Grokking Algorithms: Collisions, Performance, Load Factor
- CLRS: 11.1 Direct-Address Tables
- CLRS: 11.2 Hash Tables
- CLRS: 11.2 Hash Tables (continued)
- CLRS: 11.3 Hash Functions
- CLRS: 11.4 Open Addressing
- CLRS: 11.5 Practical Considerations
- Skiena: 3.7 Hashing and Strings
- Sedgewick: Hashing
Cluster 5: Heaps and Priority Queues
- CLRS: 6.1 Heaps
- CLRS: 6.2 Maintaining the Heap Property
- CLRS: 6.3 Building a Heap; Heapsort
- CLRS: 6.5 Priority Queues
- Skiena: 3.5 Priority Queues
- Skiena: 4.3 Heapsort
- Skiena: 4.3.2 Constructing Heaps
- Sedgewick: Priority Queues
- Competitive Programming: Non-linear DS with built-in libraries
Optional Deep Dive
- CLRS: 7.4 Analysis of Quicksort -- full probabilistic analysis of random-pivot quicksort
- CLRS: 11.3 Hash Functions (extended) -- universal hashing proofs
- Skiena: 3.7.2 Efficient String Matching via Hashing -- Karp-Rabin and rolling-hash ideas
- Skiena: 4.10 Divide and Conquer -- broader D&C patterns beyond sort
- Sedgewick: Selection and Merging (extended) -- merging strategies, generalizations
Concept-to-Source Map
| Primary concept | Best source if stuck | Why this source |
|---|---|---|
| Mergesort is the divide-and-conquer exemplar | CLRS 2.3 | Clean recurrence derivation and correctness argument |
| Quicksort and why randomization helps | CLRS 7.3 | Best explanation of expected n log n via random pivots |
| Comparison sorting has an Omega(n log n) lower bound | CLRS 8.1 | The decision-tree argument in its canonical form |
| Binary search and its invariant | Skiena 4.9 | Variant-aware problem-driven treatment |
| Selection and order statistics in O(n) | CLRS 9.2 | Quickselect derivation with random pivots |
| Hashing as a randomized model | CLRS 11.2 | Expected-cost analysis with simple-uniform-hashing assumption |
| Collision resolution: chaining vs open addressing | CLRS 11.4 | Probe-sequence costs and tombstone logic |
| The binary heap as an implicit tree | CLRS 6.1 | Standard array-index arithmetic and heap property |
| Heapsort and the priority-queue API | CLRS 6.5 | Canonical PQ operations and decrease_key treatment |