Algorithm Visualiser

Interactive Visual Learning
for Advanced Algorithms

This tool teaches three core algorithms from algorithm design and analysis through step-by-step interactive visualisations. Each tab walks you through how the algorithm works, why it works, and what its theoretical guarantees are — with live animation, pseudocode highlighting, and educational explanations at every step.

Topics covered: LP Duality & Network Flow, FFT Polynomial Multiplication, and Pollard’s Rho Factorization.

Algorithms

▴

Part 1 — CLO 1

LP Duality & Network Flow

Visualise the Edmonds-Karp algorithm finding augmenting paths, watch the residual graph update at each step, and see the min-cut highlighted when max-flow is reached. Strong duality is verified live.

Ford-Fulkerson BFS O(VE²) LP Duality

Open visualiser →

∿

Part 2 — CLO 2

FFT: Polynomial Multiplication

Step through the Cooley-Tukey butterfly network level by level. Watch roots of unity animate on the unit circle, see pointwise multiplication, and follow the inverse FFT back to coefficients.

Butterfly Network O(n log n) Roots of Unity

Open visualiser →

Part 3 — CLO 3

Pollard’s Rho Factorization

Animate the pseudo-random sequence forming a rho-shaped graph. Follow the tortoise and hare with Floyd’s cycle detection, watching GCD values at each step until a factor is revealed.

Floyd Detection O(n^¼) Birthday Paradox

Open visualiser →

🔑

Part 4 — Cryptosystems

RSA Cryptosystem

Build an RSA cryptosystem from scratch. Enter two primes, compute n and φ(n), choose a public exponent, derive the private key via the Extended Euclidean Algorithm, then encrypt and decrypt messages step by step. Includes Euler’s theorem correctness proof and a security analysis connecting to Pollard’s Rho.

Modular Arithmetic Extended Euclidean Euler’s Theorem Public-Key Crypto

Open visualiser →

Academic References

[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms, 4th edition. MIT Press, 2022. — Chapters 26 (Maximum Flow), 29 (Linear Programming), 30 (FFT), 31 (Number Theory).

[2] Edmonds, J. and Karp, R. M. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2):248–264, 1972. — Original proof that BFS augmentation gives O(VE²) complexity.

[3] Cooley, J. W. and Tukey, J. W. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90):297–301, 1965. — The foundational paper establishing the O(n log n) FFT algorithm.

[4] Pollard, J. M. A Monte Carlo method for factorization. BIT Numerical Mathematics, 15:331–334, 1975. — Introduces the rho algorithm achieving O(n^¼) expected factorization.

Network Input

Edge list — format: from, to, capacity (one per line) Use s = source | t = sink

Playback Controls

SPEED 1x

Idle Step 0 / 0

Live Statistics

0Max Flow

0Augmentations

0BFS Calls

—Min-Cut Cap.

LP Formulation — Strong Duality

PRIMAL (Max-Flow)

maximize ∑ f(s,v)
s.t. f(u,v) ≤ c(u,v)
∑in = ∑out
f(u,v) ≥ 0

DUAL (Min-Cut)

minimize ∑ c(u,v)·d
s.t. d(u,v) ≥ p(v)−p(u)
p(s)=0, p(t)=1
d(u,v) ≥ 0

Strong Duality: Max-Flow = Min-Cut
Optimal values will match when done.

Pseudocode — Edmonds-Karp (BFS)

1EDMONDS-KARP(G, s, t):

2 for each (u,v) in E: f[u,v] = 0

3 while BFS(Gf, s to t) finds path p:

4 cf = min{ cf(u,v) : (u,v) in p }

5 for each (u,v) in p:

6 f[u,v] = f[u,v] + cf

7 f[v,u] = f[v,u] - cf

8 return sum_v f[s,v] // max flow

9 // Min-Cut S = {reachable from s in Gf}

Step Explanation

Build a network, then press Play or Step to animate.

Step History

#	Type	Path	Total Flow

What is Max-Flow?

Find the maximum flow from source s to sink t in a directed network where each edge has a capacity constraint.

Ford-Fulkerson Method: Repeatedly augment flow along paths in the residual graph. Edmonds-Karp uses BFS (shortest path) to guarantee O(VE²) runtime regardless of capacity values.

Residual Graph

For edge (u,v) with capacity c and flow f: the residual graph has a forward edge with capacity c−f and a backward edge with capacity f. The backward edge allows "undoing" previous flow decisions.

Max-Flow Min-Cut Theorem (LP Duality): Maximum s-t flow = Minimum s-t cut capacity. This follows from LP Strong Duality: max-flow is the primal LP; min-cut is its dual.

Worked Example

Load "Classic CLRS". BFS finds s→a→c→t (bottleneck 4), then s→a→d→t (bottleneck 6), then s→b→d→t (bottleneck 4). Total max flow = 14 = min-cut capacity. ✓

Edmonds-Karp — Flow Network & Residual Graph

Flow Edge

Aug. Path

Min-Cut

Residual

Saturated

◆

Edit the edge list on the left
then press Build Steps

←

Polynomial Input

Polynomial A — coefficients a0, a1, a2, ... (low to high degree) "1,2,3" represents 1 + 2x + 3x² Polynomial B — coefficients b0, b1, b2, ...

Playback Controls

SPEED 1x

Idle Step 0 / 0

Live Statistics

0Multiplications

0Additions

—Naive n² ops

—Phase

Complexity Comparison

NAIVE O(n²)

— ops

FFT O(n log n)

— ops

The n-th roots of unity w_n^k = e^(2pi*i*k/n) satisfy w_n^(n/2) = -1 (cancellation), halving the work at each recursion level.

Pseudocode — Cooley-Tukey FFT

1FFT(a[0..n-1], invert):

2 if n == 1: return

3 a_even = a[0,2,4,...]; a_odd = a[1,3,5,...]

4 FFT(a_even, invert); FFT(a_odd, invert)

5 w = e^(+/-2*pi*i/n) [- sign for IFFT]

6 for k = 0 to n/2 - 1:

7 t = w^k * a_odd[k]

8 a[k] = a_even[k] + t

9 a[k+n/2] = a_even[k] - t

10 if invert: a[k] = a[k] / n

Step Explanation

Enter two polynomials and press Build to begin.

Step History

#	Phase	Detail	Total Ops

Why FFT for Polynomials?

Naive multiplication of degree-n polynomials costs O(n²). FFT evaluates each polynomial at n cleverly chosen points in O(n log n), multiplies pointwise in O(n), then interpolates back.

3-Step Process:
(1) FFT(A) and FFT(B) → value representation at n roots of unity
(2) Pointwise: C[k] = A[k] · B[k] — O(n)
(3) IFFT(C) → coefficient form of the product

Butterfly Network

At each recursion level, n/2 butterfly operations combine adjacent pairs. With log⊂2 n levels total, the overall work is O(n log n).

Divide & Conquer: A(x) = A_even(x²) + x·A_odd(x²). Recurrence: T(n) = 2T(n/2) + O(n) → O(n log n).

Worked Example

A=[1,2,3,4], B=[1,1,1,1]. FFT pads to n=8, evaluates at 8 roots of unity, multiplies pointwise, inverse-FFTs to get C=[1,3,6,10,9,7,4].

FFT Butterfly Network — 3-Step Polynomial Multiplication

Poly A

Poly B

Result C

Active Level

Pending

∿

Enter two polynomials on the left
then press Build Steps

←

Factorization Input

Composite number n Constant c (pseudo-random function: f(x) = x² + c mod n) Starting value x0

Playback Controls

SPEED 1x

Idle Step 0 / 0

Live Statistics

0Steps

0GCDs Computed

—Factor Found

—Expected O(n^0.25)

Pointer State

TORTOISE

—

xi (slow)

HARE

—

x2i (fast)

GCD

—

|xi - x2i|, n

Pseudocode — Pollard's Rho + Floyd Detection

1POLLARD-RHO(n, c=1, x0=2):

2 x = x0; y = x0; d = 1

3 f(x) = (x*x + c) mod n

4 while d == 1:

5 x = f(x) // tortoise: 1 step

6 y = f(f(y)) // hare: 2 steps

7 d = gcd(|x - y|, n)

8 if d == n: FAILURE (retry with new c)

9 return d // non-trivial factor of n

Step Explanation

Enter a composite number and press Build to begin.

Step History

#	Tortoise xi	Hare x2i	gcd

What is Pollard's Rho?

A probabilistic factorization algorithm (John Pollard, 1975) with expected runtime O(n^(1/4)) — far faster than trial division at O(n^(1/2)).

Birthday Paradox: Among about sqrt(p) random values mod p (p = smallest prime factor of n), two will collide with high probability. This collision mod p reveals p via GCD.

Floyd's Cycle Detection

The sequence x0, f(x0), f(f(x0)), ... is eventually periodic modulo p — it forms a rho shape: a tail leading into a cycle. The tortoise moves 1 step per iteration; the hare moves 2.

Key insight: When tortoise x equals hare y mod p, then p divides gcd(|x−y|, n). Since p divides n but p does not equal n, we get 1 < gcd < n — a real non-trivial factor.

Worked Example

n=77, c=1, x0=2. Sequence: 2, 5, 26, 677 mod 77 = 677-8*77=61, ... Eventually gcd(|xi - x2i|, 77) = 7. Factor found: 7 × 11 = 77. ✓

Pollard's Rho — Pseudo-Random Sequence & Floyd's Cycle Detection

Tortoise (slow)

Hare (fast)

Factor Found

Visited

Unvisited

Enter a composite number on the left
then press Build Steps

←

Key Parameters

Prime p Prime q

n = p × q = —
φ(n) = (p−1)(q−1) = —

Public Exponent e

e — must satisfy gcd(e, φ(n)) = 1

Press Generate Keys to validate.

Playback Controls

Idle Step 0 / 0

Message & Operations

Message m (integer, must be < n)

Key Pair

PUBLIC KEY

(e, n)

Share freely

PRIVATE KEY

(d, n)

Keep secret

Live Values

—n = p×q

—φ(n)

—e (public)

—d (private)

Step History

#	Stage	Value	Result

Why does decryption work?

By Euler’s theorem, m^φ(n) ≡ 1 (mod n) for any m coprime to n. Since e × d ≡ 1 (mod φ(n)), we have e × d = kφ(n) + 1 for some integer k. Therefore:

c^d = (m^e)^d = m^ed = m^kφ(n)+1 = (m^φ(n))^k × m ≡ 1^k × m ≡ m (mod n)

Why is RSA secure?

RSA’s security relies on the difficulty of factoring large integers. Given only the public key (e, n), an attacker must factor n into p and q. Only then can they compute φ(n) and find d.

Connection to Pollard’s Rho: Algorithms like Pollard’s Rho can factor numbers in O(n^¼) time. This is why RSA requires primes of 1024+ bits in practice — to make factoring computationally infeasible.

Extended Euclidean Algorithm

The private key d is computed as the modular inverse of e modulo φ(n) using the Extended Euclidean Algorithm, which finds integers x, y such that e×x + φ(n)×y = 1. Then d = x mod φ(n).

RSA Cryptosystem — Key Generation, Encryption & Decryption

Public

Private

Ciphertext

Recovered

Active Step

🔑

Enter two primes and press
Generate Keys to begin

←

Interactive Visual Learning for Advanced Algorithms

What is Max-Flow?

Residual Graph

Worked Example

Why FFT for Polynomials?

Butterfly Network

Worked Example

What is Pollard's Rho?

Floyd's Cycle Detection

Worked Example

Why does decryption work?

Why is RSA secure?

Extended Euclidean Algorithm

Interactive Visual Learning
for Advanced Algorithms