The Perl
Algorithm Field Guide
Twenty-two algorithms in idiomatic Perl — every line run on a real interpreter — with the proofs that say why they work and labs that let you watch them run.
SEC 1Perl for Algorithms
Perl earned its reputation on text, but the same machinery — references, hashes, and slices — makes it a quietly excellent language for data structures. Three idioms carry most of the weight in everything that follows.
\ References build every structure
Perl's arrays and hashes flatten when nested, so a structure of structures is really a structure of references. A reference is a scalar that points at an array or hash; @{ ... } and %{ ... } turn it back into the real thing, and the arrow -> dereferences one level at a time. This is the bedrock for graphs, trees, and DP tables.
# References are how Perl builds nested structures.
my @matrix = ([1, 2, 3], [4, 5, 6]); # array of array-refs
my $cell = $matrix[1][2]; # -> 6 (autoderef of the ref)
my %graph = (a => ['b', 'c'], b => ['c']); # hash of array-refs
push @{ $graph{a} }, 'd'; # @{ ... } dereferences to a real array
my @nbrs = @{ $graph{a} }; # -> ('b', 'c', 'd')% A hash is a set, a multiset, and a counter
Because hash lookup and insertion are expected \(O(1)\), a hash is the right tool whenever you need membership, de-duplication, or frequency counts. The post-increment idiom !$seen{$_}++ is the canonical order-preserving unique filter: the test reads the old value (false, the first time) and the ++ sets it so every later copy is suppressed.
# A hash is Perl's universal set, multiset, and frequency table.
sub uniq { # order-preserving de-duplication
my %seen;
return grep { !$seen{$_}++ } @_; # the post-increment makes the test fire once
}
sub freq { # element -> count
my %count;
$count{$_}++ for @_; # autovivification starts every key at 0
return \%count;
}@ Sort once with the Schwartzian transform
A comparator runs \(O(n\log n)\) times, so any expensive sort key should be computed before sorting, not inside the comparator. The Schwartzian transform — read bottom-to-top as decorate, sort, undecorate — pairs each element with its key once, sorts on the key, then strips it away.
# The Schwartzian transform: decorate, sort, undecorate -- compute the
# expensive sort key exactly once per element instead of on every compare.
sub by_length {
my @words = @_;
return map { $_->[0] } # 3. undecorate
sort { $a->[1] <=> $b->[1] # 2. sort by length,
or $a->[0] cmp $b->[0] } # ties broken alphabetically
map { [$_, length $_] } @words; # 1. decorate with the key
}Perl arrays are 0-based; $#a is the last index and scalar @a is the length. The most common bug porting from a 1-based language (Octave, say) is an off-by-one in a loop bound or a midpoint — check the endpoints first.
SEC 2Searching & Sorting
The classics, with their proofs. We start with the logarithmic search that sortedness buys us, then selection without full sorting, a linear-time sort that uses no comparisons at all, and the heap that underlies both heapsort and the priority queue.
Binary search — O(log n)
sub binary_search {
my ($a, $target) = @_; # $a must be sorted ascending
my ($lo, $hi) = (0, $#$a); # $#$a is the last index of the array-ref
while ($lo <= $hi) {
my $mid = $lo + int(($hi - $lo) / 2);
if ($a->[$mid] == $target) { return $mid; }
elsif ($a->[$mid] < $target) { $lo = $mid + 1; } # discard left half
else { $hi = $mid - 1; } # discard right half
}
return -1;
}On a sorted array of \(n\) elements, binary search returns a correct index (or \(-1\)) in \(O(\log n)\) time.
Correctness. The invariant is: if target is present, its index lies in [lo, hi]. It holds initially over the whole array. Each step inspects a[mid]; if it is smaller than the target then by sortedness every index \(\le\) mid is too, so the answer (if any) lies in [mid+1, hi] — the new window — and symmetrically on the other side. When lo > hi the window is empty and the invariant says the target is absent, so \(-1\) is correct.
Time. The window width \(hi-lo+1\) at least halves each iteration: from \(n\) it reaches \(0\) after at most \(\lfloor\log_2 n\rfloor + 1\) steps, each doing \(O(1)\) work. Writing the midpoint as lo + int((hi-lo)/2) rather than (lo+hi)/2 also sidesteps integer overflow in languages where that matters. \(\;\blacksquare\)
Quickselect — the k-th smallest in expected O(n)
To find one order statistic you need not sort everything. Quickselect partitions around a random pivot and recurses into only the side that contains the answer.
# Quickselect: find the k-th smallest (0-based) in expected O(n) time,
# without sorting the whole array.
sub quickselect {
my ($aref, $k) = @_;
my @a = @$aref;
while (1) {
return $a[0] if @a == 1;
my $pivot = $a[ int rand @a ]; # random pivot avoids worst case
my @lt = grep { $_ < $pivot } @a;
my @eq = grep { $_ == $pivot } @a;
my @gt = grep { $_ > $pivot } @a;
if ($k < @lt) { @a = @lt; } # answer is among the smaller
elsif ($k < @lt + @eq) { return $pivot; } # landed inside the pivots
else { $k -= @lt + @eq; @a = @gt; } # recurse on the larger
}
}With a uniformly random pivot, quickselect runs in \(O(n)\) expected time.
A pivot is good if it falls in the middle half of the values, so that each side has at most \(\tfrac34\) of the elements; a uniform pivot is good with probability \(\tfrac12\). Let \(T(n)\) bound the expected work on \(n\) elements. The partition costs \(cn\). In expectation we try \(2\) pivots before a good one, and a good pivot leaves at most \(\tfrac34 n\) elements to recurse on, so \[ T(n) \le cn + T\!\left(\tfrac34 n\right). \] Unrolling gives \(T(n) \le cn\bigl(1 + \tfrac34 + (\tfrac34)^2 + \cdots\bigr) = cn \cdot \dfrac{1}{1-\frac34} = 4cn = O(n).\) (Sorting first would cost \(O(n\log n)\); this is strictly less work for a single statistic.) \(\;\blacksquare\)
Counting sort — no comparisons, O(n + k)
# Counting sort: no comparisons at all -- O(n + k) for keys in 0..k.
# This version is STABLE: equal keys keep their original relative order.
sub counting_sort {
my ($a, $maxv) = @_; # $a: arrayref of ints in 0..$maxv
my @count = (0) x ($maxv + 1);
$count[$_]++ for @$a; # 1. tally each key
$count[$_] += $count[$_ - 1] for 1 .. $maxv;# 2. prefix sums = end positions
my @out = (0) x scalar @$a;
for my $x (reverse @$a) { # 3. place from the back to stay stable
$out[ --$count[$x] ] = $x;
}
return \@out;
}Counting sort orders \(n\) integer keys drawn from \(\{0,\dots,k\}\) in \(O(n+k)\) time, and it is stable.
Time. The histogram pass is \(O(n)\), the prefix-sum pass is \(O(k)\), and the placement pass is \(O(n)\): total \(O(n+k)\). When \(k=O(n)\) this is linear — beating the \(\Omega(n\log n)\) comparison-sort barrier precisely because it never compares two keys.
Stability. After the prefix sums, count[x] equals the number of keys \(\le x\), i.e. one past the last slot any key of value \(x\) may occupy. Scanning the input right to left and writing each key at --count[x] places later-occurring equal keys into later slots, so equal keys retain their original order. Stability is what lets counting sort serve as the inner pass of radix sort. \(\;\blacksquare\)
The binary heap — heapsort and the priority queue
A binary heap is a complete tree flattened into an array: the children of index \(i\) are \(2i{+}1\) and \(2i{+}2\). A max-heap drives in-place heapsort; a min-heap is the priority queue behind Dijkstra and Huffman coding.
# Heapsort: build a max-heap in place, then repeatedly pull the max to the back.
sub heapsort {
my @a = @{ $_[0] };
my $n = scalar @a;
for (my $i = int($n / 2) - 1; $i >= 0; $i--) { # heapify the whole array
sift_down(\@a, $i, $n);
}
for (my $end = $n - 1; $end > 0; $end--) {
@a[0, $end] = @a[$end, 0]; # max moves to its final seat
sift_down(\@a, 0, $end); # restore the heap on what remains
}
return \@a;
}
sub sift_down {
my ($a, $i, $n) = @_;
while (1) {
my ($l, $r, $big) = (2 * $i + 1, 2 * $i + 2, $i);
$big = $l if $l < $n && $a->[$l] > $a->[$big];
$big = $r if $r < $n && $a->[$r] > $a->[$big];
last if $big == $i; # parent already dominates children
@{$a}[$i, $big] = @{$a}[$big, $i];
$i = $big;
}
}Building a heap by sifting down from the middle takes \(O(n)\), and heapsort runs in \(O(n\log n)\).
Build-heap is linear. A node at height \(h\) costs \(O(h)\) to sift down, and a heap of \(n\) nodes has at most \(\lceil n/2^{\,h+1}\rceil\) nodes at height \(h\). Summing, \[ \sum_{h=0}^{\lfloor\log n\rfloor} \frac{n}{2^{\,h+1}}\,O(h) \;=\; O\!\left(n\sum_{h\ge 0}\frac{h}{2^{h}}\right) \;=\; O(2n) \;=\; O(n), \] using \(\sum_{h\ge0} h/2^h = 2\). The naive bound of \(n\) sift-downs at \(O(\log n)\) each would say \(O(n\log n)\); the sharper sum shows most nodes are shallow.
Heapsort. After the \(O(n)\) build, each of the \(n-1\) extractions swaps the root to the tail and sifts down in \(O(\log n)\): total \(O(n\log n)\), in place, with no recursion. \(\;\blacksquare\)
# A binary min-heap stored in a flat array-ref. Parent of i is (i-1)>>1;
# children are 2i+1 and 2i+2. Both operations are O(log n).
sub heap_push {
my ($h, $x) = @_;
push @$h, $x;
my $i = $#$h;
while ($i > 0) { # bubble up while smaller than parent
my $parent = ($i - 1) >> 1;
last if $h->[$parent] <= $h->[$i];
@{$h}[$i, $parent] = @{$h}[$parent, $i];
$i = $parent;
}
}
sub heap_pop {
my ($h) = @_;
return undef unless @$h;
my $min = $h->[0];
my $last = pop @$h;
if (@$h) {
$h->[0] = $last; # move last element to the root
my $n = scalar @$h;
my $i = 0;
while (1) { # sink down to the smaller child
my ($l, $r, $small) = (2 * $i + 1, 2 * $i + 2, $i);
$small = $l if $l < $n && $h->[$l] < $h->[$small];
$small = $r if $r < $n && $h->[$r] < $h->[$small];
last if $small == $i;
@{$h}[$i, $small] = @{$h}[$small, $i];
$i = $small;
}
}
return $min;
}The same array, read as a min-heap, gives a priority queue with \(O(\log n)\) push and pop. The lab below animates both motions.
Binary Min-Heap
Push values and watch each sift up until its parent is smaller; pop to remove the minimum and watch the last leaf sink back into place. The tree and the flat array are two views of one structure.
SEC 3Strings
Text is Perl's native habitat. Here are the matchers and edit-distance routines that show why — substr, split //, and hashes do most of the work.
Knuth–Morris–Pratt — matching in O(n + m)
Naive matching re-examines text characters after every mismatch. KMP precomputes a prefix table — how much of the pattern is also a suffix of what just matched — so the text pointer never moves backward.
# Knuth-Morris-Pratt: precompute how far to fall back on a mismatch, so the
# text pointer never moves backward. Total work is O(n + m).
sub kmp_table {
my ($pat) = @_;
my @t = (0) x length $pat; # t[i] = length of longest proper prefix
my $k = 0; # of pat[0..i] that is also a suffix
for my $i (1 .. length($pat) - 1) {
$k = $t[$k - 1] while $k > 0 && substr($pat, $i, 1) ne substr($pat, $k, 1);
$k++ if substr($pat, $i, 1) eq substr($pat, $k, 1);
$t[$i] = $k;
}
return \@t;
}
sub kmp_search {
my ($text, $pat) = @_;
return 0 if $pat eq '';
my $t = kmp_table($pat);
my $k = 0;
for my $i (0 .. length($text) - 1) {
$k = $t->[$k - 1] while $k > 0 && substr($text, $i, 1) ne substr($pat, $k, 1);
$k++ if substr($text, $i, 1) eq substr($pat, $k, 1);
return $i - length($pat) + 1 if $k == length $pat; # full match ends at i
}
return -1;
}KMP finds a pattern of length \(m\) in a text of length \(n\) in \(O(n+m)\) time.
Use the matched length \(k\) as a potential. In the search loop, each successful character comparison increases \(k\) by exactly \(1\), and the text pointer \(i\) advances; across the whole text \(k\) can therefore increase at most \(n\) times. Every fallback step k = t[k-1] strictly decreases \(k\), and since \(k\ge 0\) the total number of decreases cannot exceed the total number of increases. Hence the search does \(O(n)\) work; building the table is the same argument on the pattern, \(O(m)\). The total is \(O(n+m)\) — and the text pointer is never rewound. \(\;\blacksquare\)
Rabin–Karp — a rolling hash
Treat each window as a base-256 number modulo a large prime. Sliding the window forward updates the hash in \(O(1)\) by removing the leading character and appending the trailing one. A hash match is then verified with a real eq to rule out the rare collision.
# Rabin-Karp: slide a rolling hash over the text so each window costs O(1)
# to re-hash. A hash hit is verified with eq to rule out collisions.
sub rabin_karp {
my ($text, $pat) = @_;
my ($n, $m) = (length $text, length $pat);
return 0 if $m == 0;
return -1 if $m > $n;
my ($base, $mod) = (256, 1_000_000_007);
my ($hp, $ht, $pow) = (0, 0, 1);
for my $i (0 .. $m - 1) { # hash the pattern and first window
$hp = ($hp * $base + ord substr($pat, $i, 1)) % $mod;
$ht = ($ht * $base + ord substr($text, $i, 1)) % $mod;
$pow = ($pow * $base) % $mod if $i < $m - 1;# $base^(m-1), for removing the front char
}
for my $i (0 .. $n - $m) {
return $i if $hp == $ht && substr($text, $i, $m) eq $pat;
if ($i < $n - $m) { # roll: drop text[i], add text[i+m]
$ht = (($ht - ord(substr($text, $i, 1)) * $pow) * $base
+ ord substr($text, $i + $m, 1)) % $mod;
$ht += $mod if $ht < 0;
}
}
return -1;
}With a good modulus the chance any particular window collides with the pattern's hash is about \(1/\text{mod}\), so the expected number of full verifications is tiny and the search runs in expected \(O(n+m)\). The worst case is \(O(nm)\) (everything collides), which is why the explicit eq check — not the hash — is what guarantees correctness.
Edit distance — the Levenshtein DP
# Edit distance: fewest single-character insertions, deletions, or
# substitutions to turn $s into $t. Two rolling rows keep it O(m) space.
sub levenshtein {
my ($s, $t) = @_;
my @s = split //, $s;
my @t = split //, $t;
my ($n, $m) = (scalar @s, scalar @t);
my @prev = (0 .. $m); # editing "" into t[0..j] costs j
for my $i (1 .. $n) {
my @cur = ($i); # editing s[0..i] into "" costs i
for my $j (1 .. $m) {
my $cost = ($s[$i - 1] eq $t[$j - 1]) ? 0 : 1;
my $del = $prev[$j] + 1;
my $ins = $cur[$j - 1] + 1;
my $sub = $prev[$j - 1] + $cost;
$cur[$j] = $del < $ins ? $del : $ins;
$cur[$j] = $sub if $sub < $cur[$j];
}
@prev = @cur;
}
return $prev[$m];
}The recurrence below computes the minimum number of single-character insertions, deletions, and substitutions turning \(s\) into \(t\), in \(O(mn)\) time.
Let \(D(i,j)\) be the edit distance between the prefixes \(s[1..i]\) and \(t[1..j]\). Consider the last column of an optimal alignment. It is either a deletion of \(s_i\) (cost \(1 + D(i{-}1,j)\)), an insertion of \(t_j\) (cost \(1 + D(i,j{-}1)\)), or a match/substitution of \(s_i\) with \(t_j\) (cost \([s_i\neq t_j] + D(i{-}1,j{-}1)\)). These three cases exhaust the possibilities, so \[ D(i,j)=\min\bigl(1{+}D(i{-}1,j),\;1{+}D(i,j{-}1),\;[s_i\neq t_j]{+}D(i{-}1,j{-}1)\bigr), \] with \(D(i,0)=i\) and \(D(0,j)=j\). Each of the \(mn\) cells is \(O(1)\); the code keeps only two rows, so the space is \(O(m)\). \(\;\blacksquare\)
Longest common subsequence
# Longest common subsequence: fill a table, then walk it backward to
# reconstruct one optimal subsequence. Runs in O(n*m).
sub lcs {
my ($a, $b) = @_;
my @a = split //, $a;
my @b = split //, $b;
my ($n, $m) = (scalar @a, scalar @b);
my @dp;
$dp[$_] = [(0) x ($m + 1)] for 0 .. $n;
for my $i (1 .. $n) {
for my $j (1 .. $m) {
$dp[$i][$j] = $a[$i - 1] eq $b[$j - 1]
? $dp[$i - 1][$j - 1] + 1 # extend the match
: ($dp[$i - 1][$j] > $dp[$i][$j - 1] # or take the better side
? $dp[$i - 1][$j] : $dp[$i][$j - 1]);
}
}
my ($i, $j, $out) = ($n, $m, '');
while ($i > 0 && $j > 0) { # backtrace one solution
if ($a[$i - 1] eq $b[$j - 1]) { $out = $a[$i - 1] . $out; $i--; $j--; }
elsif ($dp[$i - 1][$j] >= $dp[$i][$j - 1]) { $i--; }
else { $j--; }
}
return $out;
}If the last characters match, an LCS must use them, leaving an LCS of the two shorter prefixes; if not, one of the two characters is unused, so the answer is the better of dropping either. That is exactly the recurrence filled in the table, after which the backtrace walks from the corner choosing the move that produced each cell — reconstructing one optimal subsequence in \(O(n+m)\).
Anagram grouping — the signature trick
# Group words that are anagrams of one another. The signature -- the word's
# letters in sorted order -- is identical for every member of a group.
sub anagrams {
my %groups;
for my $w (@_) {
my $sig = join '', sort split //, $w; # canonical key for this word
push @{ $groups{$sig} }, $w;
}
return [ map { $groups{$_} } sort keys %groups ];
}Two words are anagrams iff their multisets of letters are equal, and sorting the letters yields a canonical representative of that multiset. Using that sorted string as a hash key collapses each anagram class to one bucket in \(O(L\log L)\) per word of length \(L\).
KMP String Matcher
Type a text and a pattern, then step the matcher. Green cells are matched; the amber outline is the character under comparison. On a mismatch, watch the pattern slide by the prefix table while the text pointer holds still.
Edit-Distance Table
Edit either word and the dynamic-programming table refills live. The amber path traced from the bottom-right corner back to the origin is one optimal sequence of edits; the corner cell is the distance.
SEC 4Dynamic Programming
When a problem's optimum is built from optima of overlapping subproblems, fill a table once and reuse it. Two more examples beyond edit distance and LCS.
Longest increasing subsequence — O(n log n)
# Longest increasing subsequence in O(n log n): @tails[k] holds the smallest
# possible tail of any increasing subsequence of length k+1.
sub lis_length {
my ($a) = @_;
my @tails;
for my $x (@$a) {
my ($lo, $hi) = (0, scalar @tails); # binary search for first tail >= x
while ($lo < $hi) {
my $mid = ($lo + $hi) >> 1;
if ($tails[$mid] < $x) { $lo = $mid + 1; } else { $hi = $mid; }
}
$tails[$lo] = $x; # extend, or improve an existing length
}
return scalar @tails;
}Maintaining the array tails, where tails[k] is the smallest possible tail of an increasing subsequence of length \(k{+}1\), computes the LIS length in \(O(n\log n)\).
tails is always strictly increasing, because a length-\((k{+}1)\) subsequence contains a length-\(k\) one with a smaller tail. For each incoming \(x\) we binary-search the first entry \(\ge x\) and overwrite it: if \(x\) is larger than every tail it extends the longest run, otherwise it lowers the best tail for that length without changing any length already achievable. The invariant — tails[k] is achievable and minimal — is preserved, so the final length of tails is the LIS length. Each step is one \(O(\log n)\) search over \(n\) items: \(O(n\log n)\). (Note tails itself is not necessarily a real subsequence; its length is the answer.) \(\;\blacksquare\)
Coin change — fewest coins
# Minimum coins to make $amount from unlimited coins of given denominations.
# dp[a] = fewest coins summing to a; returns -1 if a is unreachable.
sub coin_change {
my ($coins, $amount) = @_;
my $INF = 1e9;
my @dp = (0, ($INF) x $amount); # dp[0] = 0; the rest start unreachable
for my $a (1 .. $amount) {
for my $c (@$coins) {
$dp[$a] = $dp[$a - $c] + 1
if $c <= $a && $dp[$a - $c] + 1 < $dp[$a];
}
}
return $dp[$amount] >= $INF ? -1 : $dp[$amount];
}Let \(dp[a]\) be the fewest coins summing to \(a\). Any optimal solution uses some last coin \(c\le a\), leaving an optimal solution for \(a-c\); minimising over the available denominations gives \(dp[a]=1+\min_{c\le a} dp[a-c]\), with \(dp[0]=0\) and unreachable amounts left at infinity. Filling \(a\) from \(1\) to the target is \(O(\text{amount}\times \#\text{coins})\). Greedy would be wrong for denominations like \(\{1,3,4\}\) making \(6\) — the DP is what guarantees optimality.
SEC 5Graphs & Sets
A graph is a hash of array-refs: each key a vertex, each value its neighbour list. From that one shape come traversal, ordering, and connectivity.
Depth-first search
# Iterative depth-first search over a hash-of-arrays graph. Reversing the
# neighbours before pushing makes the visit order match the adjacency order.
sub dfs {
my ($adj, $start) = @_;
my (%seen, @order, @stack);
push @stack, $start;
while (@stack) {
my $u = pop @stack;
next if $seen{$u}++;
push @order, $u;
push @stack, reverse @{ $adj->{$u} // [] };
}
return \@order;
}An explicit stack pops in last-in-first-out order, which would visit neighbours back-to-front. Pushing them reversed makes the iterative traversal match the order a recursive DFS would take — a small but useful fidelity. Each vertex and edge is touched once, so DFS is \(O(V+E)\).
Topological sort — Kahn's algorithm
# Kahn's algorithm: repeatedly emit a vertex with no remaining prerequisites.
# Returns undef when a cycle makes a full ordering impossible.
sub topo_sort {
my ($adj) = @_;
my %indeg;
for my $u (keys %$adj) {
$indeg{$u} //= 0;
$indeg{$_}++ for @{ $adj->{$u} };
}
my @ready = sort grep { $indeg{$_} == 0 } keys %indeg;
my @order;
while (@ready) {
my $u = shift @ready;
push @order, $u;
for my $v (@{ $adj->{$u} // [] }) {
push @ready, $v if --$indeg{$v} == 0;
}
@ready = sort @ready; # keep output deterministic
}
return scalar(@order) == scalar(keys %indeg) ? \@order : undef;
}Kahn's algorithm outputs a valid topological order iff the graph is acyclic, in \(O(V+E)\).
A vertex is emitted only once its in-degree reaches \(0\) — that is, after all of its predecessors have already been emitted — so every edge points from an earlier output to a later one: the order is valid. For termination, each vertex enters the queue exactly once and each edge decrements one in-degree exactly once, giving \(O(V+E)\). Finally, if a cycle exists, none of its vertices ever reaches in-degree \(0\), so fewer than \(V\) vertices are emitted and the routine reports failure; if the graph is acyclic, a source always exists among the remaining vertices, so all \(V\) are emitted. \(\;\blacksquare\)
Union–Find — near-constant set merging
# Disjoint-set forest with path compression and union by rank.
# A sequence of m operations on n elements costs O(m * alpha(n)) -- effectively linear.
sub uf_new {
my ($n) = @_;
return { parent => [0 .. $n - 1], rank => [(0) x $n] };
}
sub uf_find {
my ($uf, $x) = @_;
my $p = $uf->{parent};
$p->[$x] = uf_find($uf, $p->[$x]) if $p->[$x] != $x; # compress on the way up
return $p->[$x];
}
sub uf_union {
my ($uf, $a, $b) = @_;
my ($ra, $rb) = (uf_find($uf, $a), uf_find($uf, $b));
return 0 if $ra == $rb; # already in one set
my $rank = $uf->{rank};
if ($rank->[$ra] < $rank->[$rb]) { $uf->{parent}[$ra] = $rb; }
elsif ($rank->[$ra] > $rank->[$rb]) { $uf->{parent}[$rb] = $ra; }
else { $uf->{parent}[$rb] = $ra; $rank->[$ra]++; } # equal ranks: pick one, bump it
return 1;
}With union by rank, every tree of rank \(r\) contains at least \(2^{r}\) nodes; hence all trees have height \(O(\log n)\) and each operation is \(O(\log n)\). Path compression improves the amortized cost to \(O(\alpha(n))\), effectively constant.
By induction on operations. A fresh singleton has rank \(0\) and \(2^0=1\) node. A root's rank rises only when two equal-rank trees merge: two trees of rank \(r\), each with \(\ge 2^{r}\) nodes by hypothesis, combine into one of rank \(r{+}1\) with \(\ge 2^{r}+2^{r}=2^{r+1}\) nodes. So a rank-\(r\) root governs \(\ge 2^{r}\) nodes, forcing \(r\le\log_2 n\); since height never exceeds rank, find climbs \(O(\log n)\) links. Path compression flattens those links on the way up, and a classic (intricate) accounting then drops the amortized bound to the inverse-Ackermann \(\alpha(n)\le 4\) for any conceivable \(n\). \(\;\blacksquare\)
Connectivity falls straight out of union-find: merge along every edge, then count distinct roots.
# Count connected components of an undirected graph using the union-find above.
sub components {
my ($n, $edges) = @_; # nodes 0..n-1; edges: arrayref of [u,v]
my $uf = uf_new($n);
uf_union($uf, $_->[0], $_->[1]) for @$edges;
my %roots;
$roots{ uf_find($uf, $_) } = 1 for 0 .. $n - 1;
return scalar keys %roots;
}Union–Find Forest
Ten elements, each its own set. union hangs the shorter tree under the taller; find path-compresses, re-parenting every node it passes straight to the root (those edges flash green). Roots are amber; the component count updates live.
SEC 6Number Theory
Three small routines that appear everywhere from cryptography to hashing — each with a clean logarithmic or near-linear bound.
Euclid's algorithm — and Bézout's coefficients
# Euclid's algorithm, plus the extended version that also returns the
# Bezout coefficients x, y with a*x + b*y = gcd(a, b).
sub gcd {
my ($a, $b) = @_;
($a, $b) = ($b, $a % $b) while $b;
return abs $a;
}
sub gcd_ext {
my ($a, $b) = @_;
return ($a, 1, 0) if $b == 0;
my ($g, $x1, $y1) = gcd_ext($b, $a % $b);
return ($g, $y1, $x1 - int($a / $b) * $y1);
}Euclid's algorithm computes \(\gcd(a,b)\), and it terminates.
Correctness. Any common divisor of \(a\) and \(b\) divides \(a - qb = a \bmod b\), and conversely any common divisor of \(b\) and \(a\bmod b\) divides \(a\); so the pair \((a,b)\) and the pair \((b, a\bmod b)\) have exactly the same set of common divisors, and in particular the same greatest one. When \(b\) becomes \(0\), \(\gcd(a,0)=a\) is returned.
Termination. The second argument is a strictly decreasing sequence of non-negative integers (\(a\bmod b < b\)), which cannot decrease forever. The extended version threads back the coefficients \(x,y\) with \(ax+by=\gcd(a,b)\) by substituting each step's identity into the next. \(\;\blacksquare\)
Modular exponentiation — O(log e)
# Modular exponentiation by squaring: base^exp mod m in O(log exp) multiplies.
sub modpow {
my ($base, $exp, $mod) = @_;
my $result = 1 % $mod;
$base %= $mod;
while ($exp > 0) {
$result = ($result * $base) % $mod if $exp & 1; # fold in this bit
$base = ($base * $base) % $mod; # square the base
$exp >>= 1;
}
return $result;
}Exponentiation by squaring computes \(b^{e}\bmod m\) using \(O(\log e)\) modular multiplications.
Write \(e\) in binary, \(e=\sum_i \varepsilon_i 2^{i}\). Then \(b^{e}=\prod_i b^{\varepsilon_i 2^{i}}\). The loop keeps base equal to \(b^{2^{i}}\bmod m\) by squaring it each iteration, and multiplies it into the result exactly when bit \(\varepsilon_i=1\). The number of iterations is the number of bits of \(e\), namely \(\lfloor\log_2 e\rfloor + 1\), each doing \(O(1)\) modular multiplications. Reducing mod \(m\) after every product keeps the operands small. \(\;\blacksquare\)
Sieve of Eratosthenes — O(n log log n)
# Sieve of Eratosthenes: every composite is crossed out by its primes.
# Starting each scan at p*p and stopping at sqrt(n) gives O(n log log n).
sub sieve {
my ($n) = @_;
return [] if $n < 2;
my @is_prime = (1) x ($n + 1);
$is_prime[0] = $is_prime[1] = 0;
for (my $p = 2; $p * $p <= $n; $p++) {
next unless $is_prime[$p];
for (my $m = $p * $p; $m <= $n; $m += $p) {
$is_prime[$m] = 0;
}
}
return [ grep { $is_prime[$_] } 2 .. $n ];
}The sieve lists every prime up to \(n\) in \(O(n\log\log n)\) time.
For each prime \(p\le\sqrt n\) the inner loop crosses out \(n/p\) multiples. The total work is therefore proportional to \[ \sum_{p\le n,\ p\ \text{prime}} \frac{n}{p} \;=\; n\sum_{p\le n}\frac1p \;=\; n\,\bigl(\ln\ln n + O(1)\bigr), \] by Mertens' theorem on the sum of reciprocals of primes — hence \(O(n\log\log n)\). Two details earn the bound: starting each scan at \(p^2\) (smaller multiples already carry a smaller prime factor) and stopping the outer loop at \(\sqrt n\) (any composite \(\le n\) has a factor that small). \(\;\blacksquare\)
Sieve of Eratosthenes
Each step takes the next surviving number — a prime, shown amber — and strikes through its multiples from \(p^2\) upward. Slide \(n\) to resize the field; the surviving cells are exactly the primes.
SEC 7Exercises
Work each with pencil and the Perl interpreter; the solution is one click away.
Using the post-increment idiom, write a one-line grep that returns the elements appearing more than once in a list (each duplicate reported once).
Count first, then keep the keys whose count exceeds one:
sub dups {
my %seen;
return grep { $seen{$_}++ == 1 } @_; # true only on the 2nd sighting
}
# dups(qw(a b a c c c b)) == ('a', 'c', 'b')The trick mirrors uniq: $seen{$_}++ == 1 is true exactly on the second sighting, so each duplicate is emitted once, in first-duplicate order.
Binary search returns an index of the target. Modify it to return the leftmost index of a target that may repeat (or \(-1\)).
Don't stop on the first hit; record it and keep searching left:
sub lower_bound {
my ($a, $target) = @_;
my ($lo, $hi, $ans) = (0, $#$a, -1);
while ($lo <= $hi) {
my $mid = $lo + (($hi - $lo) >> 1);
if ($a->[$mid] == $target) { $ans = $mid; $hi = $mid - 1; } # keep going left
elsif ($a->[$mid] < $target) { $lo = $mid + 1; }
else { $hi = $mid - 1; }
}
return $ans;
}The window still halves each step, so it stays \(O(\log n)\); the only change is that an equal element pushes hi left instead of returning, driving the search to the first occurrence.
Quickselect's expected time is \(O(n)\). What is its worst-case time, and which pivot sequence triggers it?
\(O(n^2)\). If every pivot is the current minimum or maximum (e.g. an already-sorted array with a fixed last-element pivot), each partition shrinks the problem by only one element, giving \(n+(n-1)+\cdots+1=\Theta(n^2)\). The random pivot in the code makes that sequence astronomically unlikely, which is exactly why randomisation buys the \(O(n)\) expected bound. The deterministic median-of-medians pivot achieves \(O(n)\) worst-case at a larger constant.
Compute the KMP prefix table for the pattern ababaca by hand, then check it against kmp_table.
Index the pattern \(0\ldots6\). The longest proper prefix that is also a suffix of each prefix:
a→0 ab→0 aba→1 abab→2 ababa→3 ababac→0 ababaca→1
So t = [0,0,1,2,3,0,1]. The jump from \(3\) back to \(0\) at the c is the table earning its keep: on a later mismatch there, KMP knows to restart rather than crawl back through the text.
Given uf_new, uf_union, and uf_find, decide whether an undirected graph contains a cycle in one pass over its edges.
An edge closes a cycle exactly when its endpoints are already in the same set:
sub has_cycle {
my ($n, $edges) = @_;
my $uf = uf_new($n);
for my $e (@$edges) {
return 1 unless uf_union($uf, $e->[0], $e->[1]); # ends already joined => cycle
}
return 0;
}Each edge whose ends are already connected completes a cycle; otherwise the union merges two trees. Over \(m\) edges this is \(O(m\,\alpha(n))\) — essentially linear — and is the cycle test at the heart of Kruskal's minimum-spanning-tree algorithm.
Use modpow to test whether \(2^{340}\equiv 1 \pmod{341}\). What does the answer say about \(341\)?
modpow(2, 340, 341) returns \(1\), so \(341\) passes the Fermat base-2 test — yet \(341 = 11\times 31\) is composite. It is the smallest base-2 pseudoprime: a composite that fools the Fermat test. The lesson is that \(a^{n-1}\equiv 1\) is necessary but not sufficient for primality, which is why real tests (Miller–Rabin) check more structure and several bases.
SEC 8Reference Card
A pocket card: complexities on one side, Perl idioms on the other.
Complexity at a glance
| Algorithm | Time | Space |
|---|---|---|
| Binary search | O(log n) | O(1) |
| Quickselect (expected / worst) | O(n) / O(n²) | O(n) |
| Counting sort | O(n + k) | O(n + k) |
| Heapsort · heap push/pop | O(n log n) · O(log n) | O(1) · O(n) |
| KMP · Rabin–Karp (exp.) | O(n + m) | O(m) |
| Edit distance · LCS | O(n·m) | O(min(n,m)) |
| Longest increasing subseq. | O(n log n) | O(n) |
| Coin change | O(amount · coins) | O(amount) |
| DFS · topological sort | O(V + E) | O(V) |
| Union–Find (amortized) | O(α(n)) ≈ O(1) | O(n) |
| Euclid · modpow | O(log n) | O(1) |
| Sieve of Eratosthenes | O(n log log n) | O(n) |
Perl idioms for algorithm work
| Task | Idiom |
|---|---|
| Length / last index | scalar @a / $#a |
| Swap two elements | @a[$i,$j] = @a[$j,$i] |
| Slice | @a[$lo .. $hi] |
| Array / hash ref | [ ... ] / { ... } |
| Dereference | @{$ref}, $ref->[$i], $ref->{$k} |
| Frequency count | $count{$_}++ for @list |
| Order-preserving unique | grep { !$seen{$_}++ } @list |
| Numeric sort | sort { $a <=> $b } @a |
| Min of a few values | (sort { $a <=> $b } @v)[0] |
| Split / join a string | split //, $s / join '', @ch |
| Integer halving | $mid = ($lo + $hi) >> 1 |
| Persistent cache | state %memo; ... //= ... |
1 · State the input size your bound is in. 2 · Prove correctness with an invariant before optimising. 3 · Reach for a hash before a nested loop. 4 · Verify a hash match with eq; never trust the hash alone. 5 · A better asymptotic class beats a faster constant almost every time.