Algorithms

A collection of classic algorithms implemented in Python as Jupyter notebooks. Each notebook contains an explanation of the algorithm alongside a working implementation and a runnable example.

Contents

The notebooks are grouped below by category. Complexities use n for input size, V for vertices and E for edges.

Searching

Algorithm	Notebook	Time	Space
Binary Search	Binary Search.ipynb	O(log n)	O(log n)
Quickselect (k-th smallest)	Quickselect.ipynb	O(n) avg, O(n²) worst	O(1)
Book Allocation (binary search on answer)	BookAllocation.ipynb	O(n · log(sum))	O(1)

Sorting

Algorithm	Notebook	Time	Space
Insertion Sort	Insertion Sort.ipynb	O(n²)	O(1)
Selection Sort	Selection Sort.ipynb	O(n²)	O(1)
Merge Sort	Merge Sort.ipynb	O(n log n)	O(n)
Quicksort	Quicksort.ipynb	O(n log n) avg	O(log n)
Heap Sort	Heap Sort.ipynb	O(n log n)	O(1)
Counting Sort	Counting Sort.ipynb	O(n + k)	O(k)

Graph traversal & shortest paths

Algorithm	Notebook	Time	Space
Breadth First Search	BFS.ipynb	O(V + E)	O(V)
Depth First Search	DFS.ipynb	O(V + E)	O(V)
Dijkstra's Algorithm	Dijkstra's Algorithm.ipynb	O(V²)	O(V)
Bellman-Ford Algorithm	Bellman Ford.ipynb	O(V · E)	O(V)
Floyd-Warshall Algorithm	Floyd Warshall Algorithm.ipynb	O(V³)	O(V²)
Lee Algorithm (maze routing)	Lee Algorithm.ipynb	O(rows · cols)	O(rows · cols)
Flood Fill	Flood Fill.ipynb	O(rows · cols)	O(rows · cols)

Graph structure

Algorithm	Notebook	Time	Space
Kruskal's Algorithm (MST)	Kruskal's Algorithm.ipynb	O(E log E)	O(V)
Union Find (disjoint set)	Union Find.ipynb	~O(α(n)) per op	O(V)
Topological Sort (DFS)	Topological Sort.ipynb	O(V + E)	O(V)
Kahn's Topological Sort (BFS)	Kahn's Topological Sort.ipynb	O(V + E)	O(V)

Strings & miscellaneous

Algorithm	Notebook	Time	Space
KMP (substring search)	KMP.ipynb	O(m + n)	O(m)
Huffman Coding (compression)	Huffman Coding Compression.ipynb	O(n log n)	O(n)
Kadane's Algorithm (max subarray)	Kadane's Algorithm.ipynb	O(n)	O(1)
Boyer-Moore Majority Vote	Boyer Moore Majority Vote.ipynb	O(n)	O(1)
Floyd's Cycle Detection	Floyd's Cycle Detection Algorithm.ipynb	O(n)	O(1)
Euclid's Algorithm (GCD)	Euclid's Algorithm.ipynb	O(log(min(a, b)))	O(1)

Running the notebooks

Each notebook is self-contained. Open it in Jupyter and run the cells top to bottom:

pip install notebook
jupyter notebook

Several notebooks read their input via input(), so they will prompt for values (array size, elements, search target, etc.) when run.