Algorithms & Data Structures

A deep guide to turning an algorithm into a well-defined cost function, proving Big-O, Big-Omega, Big-Theta, little-o, and little-omega bounds, and knowing exactly what those bounds do not predict.

A correctness proof connects an explicit specification to every execution of an algorithm. Preconditions, postconditions, loop invariants, frame conditions, and well-founded variants divide that argument into local obligations that can be checked by hand or discharged by a verifier.

An abstract data type defines observable values and operations independently of representation. This chapter turns that separation into an engineering method: specify semantics, errors, complexity, stability, ownership, and concurrency; then prove a concrete representation preserves the contract.

Arrays make an index-to-address promise: equal-size elements occupy a contiguous region, so lookup by position is constant time. Dynamic arrays preserve that useful layout while growing geometrically; this chapter derives their costs, invalidation rules, and practical representation choices.

Linked structures encode order through explicit links rather than address arithmetic. This chapter derives singly, doubly, circular, sentinel, and intrusive forms; traces insertion, deletion, and reversal; and makes ownership, iterator stability, locality, and reclamation part of the design.

Stacks, queues, and deques constrain where elements enter and leave a sequence. This chapter derives their LIFO/FIFO contracts, array and linked representations, circular-buffer arithmetic, overflow and blocking policies, invalidation, and concurrent use.

How a hash table actually works — index reduction, load factor and the probe-count laws, chaining versus open addressing, Robin Hood and cuckoo, and the SIMD metadata designs (Swiss tables) that won on modern hardware — plus rehashing, hash flooding, and why you need a randomised seed but not a cryptographic hash.

Trees encode hierarchy; search trees add an ordering invariant; balanced variants control path length. This chapter develops representations, traversals, BST search/update, rotations, deletion, augmentation, AVL, red-black, splay, skip-list, concurrency, and selection tradeoffs.

A priority queue selects an extremal-priority item; a heap is one efficient representation. This chapter derives binary-heap indexing, swim and sink, linear-time heap construction, heapsort, d-ary and binomial variants, stable tie-breaking, handles, and concurrency constraints.

Disjoint-set union maintains a changing partition under set merges and representative queries. A parent forest, union by size or rank, and path compression turn long operation sequences into almost-constant amortized work while preserving a small set of decisive invariants.

Searching begins with a query contract: exact membership, key-to-value lookup, insertion position, predecessor, range, or prefix. This chapter derives boundary-based binary search, separates comparison count from movement and memory cost, and maps symbol-table workloads to arrays, balanced trees, hashes, tries, and external indexes.

Tries index keys by successive symbols and make prefix structure explicit. This chapter derives exact and prefix lookup, terminal markers, fanout representations, radix compression, PATRICIA, ternary search tries, Unicode key semantics, suffix indexes, memory layout, and safe mutation.

External-memory algorithms count block transfers rather than RAM instructions. This chapter derives scan and sort costs, executes multiway external merge sort, explains page-shaped B/B+ trees and buffered LSM trees, and connects their invariants to read, write, and space amplification on real storage.

Recursion solves a state by reducing it to smaller states under the same contract. The useful design questions are what decreases, what remains pending in each activation, how work differs from call depth, and when an explicit stack or tail loop gives safer control over space.

Minimax defines optimal play in finite adversarial games, while alpha–beta search preserves the same decision by carrying bounds that prove which subtrees cannot affect it.

Branch and bound turns exhaustive optimization into a proof-producing search: branches partition the candidate set, valid bounds rule out regions, and an incumbent converts local pruning into a global optimality certificate.

How algorithms use random choices to control expected cost or error, how Las Vegas and Monte Carlo guarantees differ, and how to derive, amplify, reproduce, and audit probabilistic claims.

How to expose independent work as a dependency DAG, derive processor bounds from work and span, reason about speedup and Amdahl's limit, and turn reductions, scans, and sorting networks into efficient parallel schedules.

Evolutionary algorithms search with a population, selection and randomized variation. They are useful when objectives are discontinuous, simulations are opaque or many trade-offs must be explored, but they spend evaluations rather than exploiting problem structure and provide no generic guarantee of a global optimum.

Sorting turns a collection into an order that makes later work cheap, but the right algorithm depends on the order contract, key domain, memory budget, data shape, and required worst-case behavior. This chapter derives the comparison lower bound and explains insertion, merge, heap, quick, radix, and modern hybrid sorting.

Expression processing turns characters into tokens, tokens into one precedence-resolved tree or postfix program, and that structure into values under explicit language semantics. This chapter derives shunting-yard and Pratt parsing, traces postfix evaluation, and isolates associativity, unary operators, side effects, diagnostics, and resource limits.

A precise guide to longest common subsequences, edit distance, and textual diff: what each objective means, how dynamic programs and edit graphs solve it, how to reconstruct an answer, and where tokenization or cost choices change the result.