A collection of classic data structures and algorithms, emphasizing beauty and clarity over full generality. As such, this should not be viewed as a blackbox library, but as a whitebox cookbook demonstrating the translation of abstract concepts into executable code. I hope it will be useful to students and educators, as well as competition programmers.
This repository is distributed under the MIT License. The license text need not be included in contest submissions, though I would appreciate linking back to this repo for others to find. Enjoy!
When learning a new algorithm or data structure, it's often helpful to see or play with a concrete implementation. As such, this repository catalogues several classic algorithms in their simplest forms.
In addition, the Rust language has outstanding pedagogical attributes. Its compiler acts as a teacher, enforcing strict discipline while pointing to clearer ways to structure one's logic.
The original intent of this project was to build a reference for use in programming competitions such as Codeforces and the Google Code Jam. As a result, it contains algorithms that are frequently useful to have in one's toolkit, with an emphasis on making the code concise and easy to modify under time pressure.
Most competitive programmers use C/C++ because it allows for fast coding as well as fast execution. However, these languages are notoriously unsafe, wasting a considerable share of the contestant's time and attention on accident prevention and debugging. Java is the next most popular choice, offering a bit of safety at some expense to coding and execution speed. To my delight, I found that Rust provides a lot more safety than Java without the visual clutter, and it's fast. A proficient Rust programmer stands to gain a competitive advantage as well as a more pleasant experience!
My other goal is to appeal to developers who feel, as I once did, trapped between the lesser of headaches (e.g., C++ and Java), to raise awareness that it doesn't have to be this way. Rather than trying to persuade you with words, this repository aims to show by example and ease the learning curve a bit. See Jim Blandy's Why Rust? for a brief introduction, or just dive in!
- Basic graph representations: adjacency lists, minimum spanning tree, Euler path, disjoint set union
- Network flows: Dinic's blocking flow, Hopcroft-Karp bipartite matching, min cost max flow
- Connected components: 2-edge-, 2-vertex- and strongly connected components, bridges, articulation points, topological sort, 2-SAT
- Associative range query: known colloquially as segtrees
- Math: Euclid's GCD algorithm, Bezout's identity
- Scanner: utility for reading input data
- String processing: Knuth-Morris-Pratt string matching, Manacher's palindrome search