• I/O Model and Parameters
• External Sorting (k-way merge)
• B-Trees and Buffer Trees
• Graph Algorithms (BFS/SSSP) in EM
• Cache-Oblivious Algorithms
• Engineering Tips
• Exercises

• External-memory (EM) model: fast memory (RAM) size M, disk (infinite), block size B. Cost = number of I/Os (block transfers).
• Scan(n): Θ(n/B). Sort(n): Θ((n/B) log_{M/B}(n/B)).
• Assumption: M ≥ B^2 often assumed to simplify analyses (tall-cache assumption).

// Outline for external mergesort phases
// 1) Run formation: read M items, sort in-memory, write back (n/M runs)
// 2) Multiway merge: merge up to k ≈ M/B runs using a min-heap of size k

function multiwayMerge(runs, readBlock, writeBlock) {
  // runs: array of run descriptors; readBlock(run) yields next block array; writeBlock outputs block
  // Use a min-heap of current heads across runs; refill when a block is exhausted
}

• I/O complexity: Θ(Sort(n)).
• Tricks: replacement selection to make longer initial runs; double-buffering to overlap I/O and CPU.

B-Tree

• Block-oriented search tree with branching factor Θ(B). Height Θ(log_B n).
• I/O per operation: Θ(log_B n) for search/insert/delete.

Buffer Tree (Arge et al.)

• Augment internal nodes with buffers of size Θ(M). Batch operations to amortize I/O.
• Supports batched updates/queries in O((n/B) log_{M/B}(n/B)) total I/Os.

• BFS: process levels in batches; use edge lists partitioned by source or destination buckets.
• SSSP (non-negative): bucketed variants (Dial/radix heaps) to reduce random I/O; contraction hierarchies for road networks.
• Connectivity/MST: Borůvka-style phases with sorting and scanning dominate I/O.

• Goal: optimal I/O up to constants, without knowing M or B.
• Funnelsort: achieves optimal Θ(Sort(n)).
• Cache-oblivious B-tree (vEB layout): search in O(log_B n) I/Os across unknown hierarchies.
• Layout: recursive divide-and-conquer on arrays/matrices (e.g., blocked matrix multiply) for good locality.

• Use large sequential reads/writes; minimize seeks and random access.
• Batch work; use mmap or async I/O carefully; align blocks to filesystem pages.
• Checksum blocks; compress runs to reduce I/O if CPU is cheap.

1. Implement an external mergesort simulator with parameters M and B; measure I/Os.
2. Build an in-browser B-tree visualizer with block size parameter B and show I/O counts for searches.
3. Implement a cache-oblivious matrix transpose and compare cache miss counts vs. naive.