A collection of classic data structures and algorithms, emphasizing usability, beauty and clarity over full generality. As such, this should be viewed not as a blackbox library, but as a whitebox cookbook demonstrating the design and implementation of algorithms. I hope it will be useful to students and educators, as well as fans of algorithmic programming contests.
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 contests ranging from Codeforces to Google's Kick Start and Code Jam, LeetCode and HackerRank. As a result, it contains algorithms that are frequently useful to have in one's toolkit, with an emphasis on code that is concise and easy to modify under time pressure.
Most competitive programmers rely on C++ for its fast execution time. However, it's notoriously unsafe, diverting a considerable share of the contestant's time and attention on mistake prevention and debugging. Java is the next most popular choice, offering a little safety at some expense to speed of coding and execution.
To my delight, I found that Rust eliminates entire classes of bugs, while reducing visual clutter to make the rest easier to spot. And, it's fast. There's a learning curve, to be sure. However, a proficient Rust programmer stands to gain a competitive advantage as well as a more pleasant experience!
For help in getting started, you may check out some of my past submissions.
Other online judges that support Rust:
My other goal is to appeal to developers who feel limited by mainstream, arguably outdated, programming languages. Perhaps we have a better option.
Rather than try to persuade you with words, this repository aims to show by example. If you're new to Rust, 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
- GCD Math: canonical solution to Bezout's identity
- Arithmetic: rational and complex numbers, linear algebra, safe modular arithmetic
- FFT: fast Fourier transform, number theoretic transform, convolution
- Scanner: utility for reading input data ergonomically
- String processing: Knuth-Morris-Pratt string matching, suffix arrays, Manacher's palindrome search