Skip to main content

Book Exercise Lanes

This module's exercise system is book-driven. Use these local chunks for targeted volume after you have already learned the concept from the guide.

How To Use This Page​

  1. Finish the relevant concept page first.
  2. Solve at least one problem of your own from memory.
  3. Only then open the matching exercise lane.
  4. Keep a mistake log with tags such as off-by-one in binary search, assumed stability, forgot tombstones, confused peek and extract, miscounted recurrence level, used linear probing above 0.9 load, treated expected as worst case.

Lane 1: Comparison Sorts (Insertion, Merge, Quick) and Lower Bounds​

Use this lane when you understand mergesort and quicksort at concept level but want fluency at writing partitions, merges, and analyzing their cost.

Target outcomes:

  • 3 mergesort implementations (recursive, iterative bottom-up, linked-list variant)
  • 3 quicksort variants (Lomuto, Hoare, 3-way partition for duplicates)
  • 2 decision-tree drawings for small n
  • 2 recurrence solutions with the recursion-tree method

Lane 2: Linear-Time and Specialized Sorting​

Use this lane when you want practice recognizing when to escape the comparison-sort lower bound.

Target outcomes:

  • 1 counting sort implementation with explicit stability check
  • 1 LSD radix sort on 32-bit integers with 8-bit passes
  • 1 bucket sort implementation for uniform floats in [0, 1)
  • 2 written comparisons of "when does this beat mergesort?"

Lane 3: Searching, Selection, and Hashing​

Use this lane when you can describe the data structure but freeze when coding binary search variants, quickselect, or a hash table.

Target outcomes:

  • 4 binary-search variants written with invariants (search, lower_bound, upper_bound, predicate-based)
  • 2 quickselect implementations (naive recursive and in-place)
  • 1 chaining hash table with resize
  • 1 linear-probing hash table with tombstones
  • 2 applied binary-search-on-answer problems

Lane 4: Heaps and Priority Queues​

Use this lane when you want heap and PQ fluency without guessing at sift logic or library APIs.

Target outcomes:

  • 1 from-scratch binary heap (sift_up, sift_down, push, pop, build)
  • 1 heapsort implementation with trace
  • 1 priority queue with decrease_key (heap + index map)
  • 3 applied problems: Dijkstra on a small graph, top-K, median maintenance
  • 1 Huffman code construction

Self-Curated Problem Set​

Build a custom set with these minimums:

  • 3 sorting problems where you choose the algorithm and justify the choice
  • 3 searching problems that require binary search variants or predicate-based search
  • 3 selection or top-K problems
  • 3 hash table problems (implement, analyze, or attack)
  • 3 priority-queue-shaped problems

Platforms you can pull from locally: Skiena and Sedgewick exercise chunks above. If you use external platforms (LeetCode, HackerRank, Codeforces), track them separately in your own notebook; this module's bookshelf is the default source.

Completion Checklist​

  • Completed at least two lanes in full
  • Logged at least 10 real mistakes and corrections
  • Wrote at least 6 full invariant or recurrence justifications
  • Reattempted at least 3 failed problems after review
  • Implemented at least 8 of the code katas from practice/04-code-katas.md