minikin / algorithm

Algorithms written in Rust

Overview

This repository contains the Rust source code for the algorithms in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

The official Java source code is here.

Goals

Make a Rust implementation of the library so that a Rust programmer can follow this book easily or prefer to demonstrate the algorithms using Rust.

Try to keep the interface and variable name consistent with the original book while writing idiomatic rust code.

I hope that this project helped you understand why Rust is so wonderful and loved right now. Rust is proving to be a productive tool for reliable and efficient software. In Rust, the compiler plays a gatekeeper role by refusing to compile code with these elusive bugs, including concurrency bugs. By working alongside the compiler, you can spend your time focusing on the program’s logic rather than chasing down bugs. After you finish a day's work, go home and rest, can be at ease a good night's sleep, never worry about system crash.

Index

The table index follow.

1	FUNDAMENTALS
1.2	Stack	LIFO stack
1.3	Queue	FIFO queue
1.4	LinkedList	multiset (linked list)
1.5	QuickFindUF	quick find
-	QuickUnionUF	quick union
-	WeightedQuickUnionUF	weighted quick union
-	UF	union-by-rank with path halving
2	SORTING
2.1	insert.rs	insertion sort
2.2	selection.rs	selection sort
2.3	shell.rs	shellsort
2.4	merge.rs	Merge Sort
2.5	quick.rs	quicksort
-	Quick3Way	quicksort with 3-way partitioning
2.6	PQ::new_max_pq	max heap priority queue
-	PQ::new_min_pq	min heap priority queue
-	IndexPQ::new_min_pq	index min heap priority queue
-	IndexPQ::new_max_pq	index max heap priority queue
-	TopM	Find the largest M elements
2.7	floyd.rs	heapsort
3	SEARCHING
3.4	rb2.rs	red-black tree
3.6	SparseVector	sparse vector
4	GRAPHS
-	Graph	undirected graph
-	DepthFirstSearch	depth-first search in a graph
-	NonRecursiveDFS	DFS in a graph (nonrecursive)
4.1	DepthFirstPaths	paths in a graph (DFS)
4.2	BreadthFirstPaths	paths in a graph (BFS)
4.3	CC	connected components of a graph
-	Bipartite	bipartite or odd cycle (DFS)
-	Cycle	cycle in a graph
-	SymbolGraph	symbol graph
-	Digraph	directed graph
4.4	DepthFirstPaths	paths in a digraph (DFS)
-	BreadthFirstPaths	paths in a digraph (BFS)
-	DirectedCycle	cycle in a digraph
4.5	Topological	topological order in a DAG
-	TransitiveClosure	transitive closure
4.6	KosarajuSCC	strong components (Kosaraju–Sharir)
-	EWGraph	edge-weighted graph
-	LazyPrimMST	MST (lazy Prim)
4.7	PrimMST	MST (Prim)
4.8	KruskalMST	MST (Kruskal)
-	EdgeWeightedDigraphCycle	edge-weighted digraph
4.9	DijkstraSP	shortest paths (Dijkstra)
-	DijkstraAllPairsSP	all-pairs shortest paths
4.10	AcyclicSP	shortest paths in a DAG
-	AcyclicLP	longest paths in a DAG
-	CPM	critical path method
4.11	BellmanFordSP	shortest paths (Bellman–Ford)
-	Arbitrage	arbitrage detection
5	STRINGS
-	Alphabet	alphabet
-	count.rs	alphabet client
5.1	LSD	LSD radix sort
5.2	MSD	MSD radix sort
5.3	Quick3String	3-way string quicksort
5.4	TrieST	multiway trie symbol table
5.5	TST	ternary search trie
5.6	KMP	substring search (Knuth–Morris–Pratt)

Running

# setup Rust Toolchain
make test

Roadmap

• Implement algorithms in the textbook Algorithms, 4th Edition
• Algorithms visualization (Easy to study and short learning curve)