The Archive of Interesting Code
The Archive of Interesting Code is an (ambitious) effort on my part to research, intuit, and code up every interesting algorithm and data
structureever invented. In doing so, I hope both to learn the mathematical techniques that power these technologies and to improve my skills as a programmer.
The examples on this site are in a variety of languages. I generally prefer to use C++ for algorithms, since the STL provides
a great framework for expressing algorithms that work on a variety of data types. I code up most data structures in Java, both
because the Collections framework allows them to be integrated in seamlessly with other applications and because automatic
garbage collection simplifies some of the resource management. Every now and then I'll find an algorithm or data structure that
is best represented in a different language like Haskell, in which case I'll forgo my usual language conventions.
In case you're curious what I'm someday hoping to having implemented on this page, you can check out my TODO list.
If you're interested in using any of this code in your applications, feel free to do so! You don't need to cite me or this website as a source, though I would appreciate it if you did. However, please don't plagiarize the code here by claiming authorship
- that would just be dishonest. I also caution you that while I'm fairly confident that the code on this site is correct, I haven't mercilessly tested every line, and so there may be a lurking bug or two here.
Enjoy!
The Code
| Name | Link | Date Added | Language | Description | ||
|---|---|---|---|---|---|---|
| Binomial Heap | (link) | 7‑24‑2010 | C++ | An implementation of a binomial heap data structure for use as a priority queue. | ||
| Bounded Priority Queue | (link) | 7‑24‑2010 | C++ | An implementation of a priority queue with a fixed upper limit to its size.. | ||
| Matrix | (link) | 7‑24‑2010 | C++ | A collection of classes for manipulating matrices. | ||
| VList | (link) | 8‑16‑2010 | Java | An implementation of the List abstraction backed by a VList. | ||
| Function Wrapper | (link) | 8‑16‑2010 | C++ | A C++ wrapper class around unary functions. | ||
| String | (link) | 8‑17‑2010 | C++ | An implementation of a string abstraction that uses the small string optimization. | ||
| nstream | (link) | 8‑31‑2010 | C++ | An stream class that sends and receives data over a network. | ||
| Snake | (link) | 8‑31‑2010 | C++ | An implementation of the game Snake with a rudimentary AI. | ||
| Mergesort | (link) | 9‑14‑2010 | C++ | An implementation of the mergesort algorithm. | ||
| Next Permutation | (link) | 10‑6‑2010 | C++ | An implementation of the next_permutation STL algorithm. | ||
| Interval Heap | (link) | 10‑17‑2010 | Java |
An implementation of a double-ended priority queue using an interval heap. |
||
| Linear-Time Selection | (link) | 10‑18‑2010 | C++ | A deterministic, linear-time selection algorithm using the median-of-medians algorithm. | ||
| Heapsort | (link) | 10‑18‑2010 | C++ | An implementation of the heapsort algorithm. | ||
| Union-Find | (link) | 10‑19‑2010 | Java | An implementation of a disjoint-set data structure using a disjoint set forest. | ||
| Radix Sort | (link) | 10‑19‑2010 | C++ | An implementation of the radix sort algorithm. | ||
| Rational | (link) | 10‑23‑2010 | C++ | A data structure representing a rational number. | ||
| DPLL | (link) | 10‑23‑2010 | Haskell | An implementation of the DPLL algorithm for solving CNF-SAT. | ||
| Smoothsort | (link) | 10‑27‑2010 | C++ | An implementation of the smoothsort algorithm, an adaptive heapsort variant. | ||
| Extendible Array | (link) | 10‑28‑2010 | Java | A dynamic array class with O(1) worst-case runtime lookup and append. | ||
| In-Place Merge | (link) | 10‑29‑2010 | C++ | An implementation of a merge algorithm that runs in-place. | ||
| Random Shuffle | (link) | 10‑29‑2010 | C++ | An algorithm for generating a random permutation of a set of elements. | ||
| Random Sample | (link) | 10‑29‑2010 | C++ | An O(n) time, O(1) space algorithm for randomly choosing k elements out of a stream with uniform probability. | ||
| Natural Mergesort | (link) | 10‑30‑2010 | C++ |
An implementation of natural mergesort, an adaptive variant of mergesort. |
||
| Interpolation Search | (link) | 10‑31‑2010 | C++ | An implementation of the interpolation search algorithm. | ||
| Introsort | (link) | 10‑31‑2010 | C++ |
An implementation of the introsort algorithm, a fast hybrid of quicksort, heapsort, andinsertion sort. |
||
| Hashed Array Tree | (link) | 11‑3‑2010 | Java | An implementation of a dynamic array backed by a hashed array tree. | ||
| Recurrence Solver | (link) | 11‑13‑2010 | C++ |
A fast algorithm for generating terms of a sequence defined by a linear recurrence relation. |
||
| Fibonacci Heap | (link) | 11‑15‑2010 | Java | An implementation of a priority queue backed by a Fibonacci heap. | ||
| Dijkstra's Algorithm | (link) | 11‑16‑2010 | Java | An implementation of Dijkstra's algorithm for single-source shortest paths. | ||
| Prim's Algorithm | (link) | 11‑17‑2010 | Java |
An implementation of Prim's algorithm for computing minimum spanning trees. |
||
| Kruskal's Algorithm | (link) | 11‑17‑2010 | Java |
An implementation of Kruskal's algorithm for computing minimum spanning trees. |
||
| Majority Element | (link) | 11‑17‑2010 | C++ | A fast, linear-time algorithm for finding the majority element of a data set. | ||
| Haar Transform | (link) | 11‑17‑2010 | C++ | A set of functions to decompose a sequence of values into a sum of Haar wavelets. | ||
| Argmax | (link) | 11‑19‑2010 | C++ | A pair of functions to compute the arg min or max of a function on some range. | ||
| Derivative | (link) | 11‑19‑2010 | C++ |
A function object that approximates the derivative of a function. |
||
| Levenshtein Distance | (link) | 11‑19‑2010 | C++ | An algorithm for computing the Levenshtein distance between two sequences. | ||
| Skiplist | (link) | 11‑20‑2010 | C++ | An implementation of a skip list, a randomized data structure for maintaining a sorted collection. | ||
| van Emde Boas Tree | (link) | 11‑26‑2010 | C++ | An implementation of a sorted associative array backed by a van Emde Boas tree. | ||
| Cuckoo HashMap | (link) | 11‑27‑2010 | Java |
An implementation of a hash table using cuckoo hashing. |
||
| Needleman-Wunsch Algorithm | (link) | 11‑28‑2010 | C++ | An implementation of the Needleman-Wunsch algorithm for optimal string alignment. | ||
| Treap | (link) | 11‑28‑2010 | C++ | An implementation of a sorted associative array backed by a treap. | ||
| Floyd-Warshall Algorithm | (link) | 12‑10‑2010 | Java | An implementation of the Floyd-Warshall algorithm for all-pairs shortest paths in a graph. | ||
| Power Iteration | (link) | 12‑10‑2010 | C++ | An implementation of the power iteration algorithm for finding dominant eigenvectors. | ||
| Edmonds's Matching Algorithm | (link) | 12‑15‑2010 | Java |
An implementation of Edmonds's matching algorithm for finding maximum matchings in undirected graphs. |
||
| Kosaraju's Algorithm | (link) | 12‑15‑2010 | Java |
An implementation of Kosaraju's algorithm algorithm for finding strongly connected components of a directed graph. |
||
| 2-SAT | (link) | 12‑15‑2010 | Java | A linear-time algorithm for solving 2-SAT. | ||
| Bellman-Ford Algorithm | (link) | 12‑17‑2010 | Java | An implementation of the Bellman-Ford algorithm for single-source shortest paths. | ||
| Topological Sort | (link) | 12‑17‑2010 | Java | An algorithm for computing a topological sort of a directed acyclic graph. | ||
| Graham Scan | (link) | 12‑19‑2010 | C++ | An implementation of the Graham scan for finding convex hulls in 2D space. | ||
| Bipartite Testing | (link) | 12‑19‑2010 | Java | A linear-time algorithm for checking whether a directed graph is bipartite. | ||
| Johnson's Algorithm | (link) | 12‑19‑2010 | Java | An implementation of Johnson's algorithm for all-pairs shortest paths. | ||
| Strassen Algorithm | (link) | 12‑20‑2010 | C++ | An implementation of the Strassen algorithm for fast matrix multiplication. | ||
| Cartesian Tree Sort | (link) | 12‑21‑2010 | C++ | An implementation of Cartesian tree sort, an adaptive, out-of-place heapsort variant. | ||
| Ford-Fulkerson Algorithm | (link) | 12‑21‑2010 | Java | An implementation of the Ford-Fulkerson maximum-flow algorithm. | ||
| Scaling Ford-Fulkerson | (link) | 12‑22‑2010 | Java | An modification of the Ford-Fulkerson maximum-flow algorithm that uses scaling to achieve polynomial time.. | ||
| Splay Tree | (link) | 12‑27‑2010 | C++ | An implementation of a sorted associative array backed by a splay tree. | ||
| Ternary Search Tree | (link) | 12‑28‑2010 | C++ |
An implementation of a sorted set of strings backed by a ternary sea
|