Advanced Algorithms & Data Structures

A series of algorithm implementations focused on understanding performance trade-offs through experimental analysis. Rather than relying on theoretical Big-O alone, every implementation is benchmarked and visualised against real data.

Sorting & search complexity

Seven sorting algorithms benchmarked across four data distributions — random, ascending, descending, and identical values:

Runtime was normalised against T(n)/n, T(n)/(n log n), and T(n)/n² to empirically verify complexity classes. Key finding: insertion sort consistently outperforms O(n log n) algorithms on nearly-sorted data — a result that only becomes intuitive when you see it in a plot.

Hash tables

• Chaining with linked lists for collision handling
• Open addressing: linear probing, quadratic probing, double hashing
• Benchmarked on datasets up to 100,000 elements — collision rates and lookup times compared across all strategies

Probabilistic filters

• Bloom filter with k = 2, 3, 4 hash functions — false positive rate vs. memory trade-off
• Count-Min Sketch for frequency estimation — precision vs. hash function count

String pattern matching

• Naïve search vs. deterministic finite automaton (DFA) — transition function computation and pattern recognition on randomly generated text
• Performance comparison shows DFA’s advantage grows with text length

Dynamic programming

• Fibonacci: naïve recursion vs. memoisation — exponential-to-linear improvement demonstrated empirically
• Coin change: minimum coin count with full optimal solution reconstruction

Tech stack

• Language: Python
• Libraries: Matplotlib, NumPy
• Focus: Algorithm design, complexity analysis, experimental benchmarking