Advanced Algorithm Implementations

Strassen with an empirical threshold

Strassen's algorithm gives a recursive O(n2.807) matrix multiplication, beating the naive O(n3) — but only above a hardware-dependent crossover. Below that size, cache behaviour and recursion overhead make the triple loop faster.

The lab made the threshold an empirical quantity: measure both algorithms on the target machine across N = 2, 4, 8, …, 1024, find the cross-over, and use it as the recursion base case in a threshold-hybrid that falls back to the naïve triple loop below the cutoff. A small thing, but it's the difference between Strassen as a textbook footnote and Strassen as a usable building block.

Red-Black trees → 2-3-4 trees

Implemented the Red-Black tree from scratch — insertion with fixup(), the five rotation cases, color invariants — and then the rarer second half: the equivalence between Red-Black trees and 2-3-4 trees. Each black node with its red children maps to a 2-, 3-, or 4-node, and the rotations in the RB tree correspond to node splits and merges in the 2-3-4 view. Seeing the two as the same structure with different presentations is one of those moments where balanced trees stop feeling like dark magic.

Hash table with tombstone deletion

Open-addressed hash map with linear probing. The hash itself is a polynomial accumulation with prime base p = 31 / 33, followed by Fibonacci compression with A = (√5 − 1) / 2 (the golden-ratio fractional part) — Knuth's multiplicative hash, picked specifically because it spreads clustered keys evenly across a power-of-two table. The English dictionary is the stress test; ≤32-byte string keys live in a 64-slot fixed array.

The subtle part is tombstone deletion. Naively removing a key from an open-addressed table breaks the probe chain for everything inserted after it. Marking the slot with a TOMBSTONE sentinel (distinct from NULL) preserves the chain for lookups while making the slot reusable for inserts. Easy to get wrong; the bug usually surfaces as "this key existed a minute ago and now doesn't."

Leftist heaps

A less common heap variant where every operation reduces to merge(), which runs in O(log n) by maintaining the "leftist" invariant on the null-path-length. Insert is merge-with-singleton; delete-min is merge-of-children. The whole data structure is one function — uncommon enough that it sticks.

Also implemented

• Tries with autocomplete via DFS traversal.
• KMP string matching and a plagiarism checker.
• Graph algorithms — BFS, cycle detection, graph burning.
• MSTs — Kruskal (with DSU using union-by-rank), Prim with a priority queue, plus a linear-time MST variant for a restricted edge-weight setting.
• Ropes for efficient string concatenation.
• TOTP generation (RFC 6238).

What I'd carry forward

Two habits stuck. Write invariant-checkers alongside the data structure itself — a single assertInvariants() walk after every operation catches more bugs than a test suite. And treat asymptotic complexity as a starting point, not a verdict — the Strassen threshold is the small lesson; the big one is that cache behaviour decides most real benchmarks.