Algorithms & Data Structures
the bound is a claim, and it is checkable
Depth

Series — page 2

A field says what an essay is about. A series follows one idea essay by essay — from the question that introduces it to the one that assumes all the others.
1,00010,00010³10⁴bits · runs12481632characters in the collection · copies aboven·H₃, bitsr, runs in thetransformEnglish-like · base 512 · divergence 0n·H₃ x15.8 · r x1.00

Repeat

  1. 1 The entropy that cannot see a copy
  2. 2 The index that stores the runs
  3. 3 What is still proportional to n
  4. 4 A floor under a run count
  5. 5 The sampling that follows the runs
  6. +3 more
8 essays · text 110100257amortised 2.000256512append numbercost of that append (log scale)growth factor 2, cost = 1 write + a copy of the array when it resizes9 resizes in 512 appends

Structure

  1. 1 What amortised means
  2. 1 The tree that is a list
  3. 2 Choosing a growth factor
  4. 3 Building a heap from the bottom
  5. 4 The priority nobody supplied
  6. +3 more
8 essays · structures bits per symbolhuffman3.9371.01× the floorarithmetic (adaptive)3.8981.00× the floorLZSS (window 4096)2.1130.54× the floorLZ783.1470.81× the floorH₀ = 3.89216,384 symbols · alphabet 21 · floor shown is H0 = 3.892 bits/symbolmodel: order 0 · Words from a fixed vocabularybest here: 2.113 bits/symbol

Bits

  1. 1 The bits a coder emits
  2. 2 The optimal code that is beaten
  3. 3 The model is the compressor
  4. 4 The dictionary that builds itself
  5. 5 The transform that emits nothing
  6. +2 more
7 essays · floors 10010³10010³10⁴10⁵10⁶ncomparisonsInsertionHeapsortMergeShellsorta power law is a straight line herecomparisons, counted exactly

Bound

  1. 1 What O-notation does not say
  2. 2 The constant the notation drops
  3. 3 A limit is not a prediction
  4. 4 The depth limit that almost never fires
  5. 5 A table wider than its input
  6. +2 more
7 essays · bounds mean 494599th 60304,2825,4136,543comparisonsruns600 independent random inputs, n = 512worst run 1.32× the mean

Distribution

  1. 1 The words "on average" are not a number
  2. 2 What randomising the pivot buys
  3. 2 The probe formula nobody checks
  4. 3 Expected is not average
  5. 4 What derandomising costs
  6. +1 more
6 essays · wrong 01325leading-zero rank keptregister, 0 to 255estimate 7,107truth 7,368error -3.54%0 still empty256 registers × 5 bits = 1,280 bitspredicted ±6.50%

Cardinality

  1. 1 A count read off the leading zeros
  2. 2 The correction that makes it work
  3. 3 The summaries that add
  4. 4 The floor under a summary
  5. 5 The error of a difference
5 essays · streaming above 0.01 of the stream · 13 really areone pass: 18 candidatestwo passes: 13 keys, exactly the heavy ones123456789101112131415161718128 counters · carry 1,376 bits5 of 18 spurious

Pass

  1. 1 The pass that was never a parameter
  2. 2 What a second pass buys
  3. 3 A floor one pass cannot get under
  4. 4 The pass that runs the other way
4 essays · bounds Timsort95,770shipsIntrosort130,863shipspdqsort114,408shipsDual-pivot116,836shipsMerge sort96,145textbookHeapsort187,796textbookQuicksort, median-3119,098textbookalgorithmcomparisonsrandom, n = 8,192comparisons, counted exactly

Practice

  1. 1 The sort the library ships
  2. 2 A run is a property of the input
  3. 3 When galloping pays
  4. 4 The pattern that defeats the pattern
4 essays · practice 50318223749516674879310811positionthe minimum12 values · depth 3answer 6 (1)

Range

  1. 1 The shape a range question is about
  2. 2 Two bits a value, and what undoes them
  3. 3 The table that fits inside a block
  4. 4 Where a crossing moved to
4 essays · structures decayedwindowed060120secondscount attributed to key 0half-life 4 s · window 5.77 s · burstythe same key, two questions

Decay

  1. 1 The counter with no window in it
  2. 2 The fading nobody computes
  3. 3 A decay measured from where it started
3 essays · streaming +1−1keys, most frequent firstΣ s(x)·f(x) = 9,034squared: 81,613,156true F2: 36,931,352121.0% outa polynomial of degree 4 · cash-register model · counts exactone register, 32 bits

Moment

  1. 1 The estimate that squares the stream
  2. 2 The independence an estimator spends
  3. 3 A sketch that is allowed to be under
3 essays · streaming

All essays