This repository contains the Rust source code for the algorithms in the textbook Algorithms, 4th Edition

Related tags

Learning Resources rust computer-science algorithm algorithms graph-algorithms interview data-structures rust-lang algs4
Overview

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)
You might also like...
Source code from Atlas, our 64k demo presented at Revision 2019 with Macau Exports

Atlas source code dump This is a dump of the source code for the engine, graphics tool and player for Atlas, our 64k demo released with Macau Exports

Monad 65 Jan 2, 2023
Tool to convert variable and function names in C/C++ source code to snake_case

FixNameCase Tool to convert variable and function names in C/C++ source code to snake_case. Hidden files and files listed in .gitignore are untouched.

AgriConnect 4 May 25, 2023
The ray tracer challenge in rust - Repository to follow my development of
The ray tracer challenge in rust - Repository to follow my development of "The Raytracer Challenge" book by Jamis Buck in the language Rust

The Ray Tracer Challenge This repository contains all the code written, while step by implementing Ray Tracer, based on the book "The Ray Tracer Chall

Jakob Westhoff 54 Dec 25, 2022
A repository for showcasing my knowledge of the Rust programming language, and continuing to learn the language.

Learning Rust I started learning the Rust programming language before using GitHub, but increased its usage afterwards. I have found it to be a fast a

Sean P. Myrick V19.1.7.2 2 Nov 8, 2022
Rust template repository.

Rust template repository. An opinionated starting point for rust projects such as systemd services command line tools client programs server programs

Kris Nóva 42 Dec 28, 2022
This repository serves as the backend for the Torrust Index project.
This repository serves as the backend for the Torrust Index project.

Torrust Index Backend 📢 Important Updates 📢 None at the moment ACCESS ALL UPDATES Index PROJECT DESCRIPTION PROJECT ROADMAP DOCUMENTATION INSTALLATI

Torrust 6 Dec 15, 2022
Download a single file from a Git repository.

git-download Microservices architecture requires sharing service definition files like in protocol buffer, for clients to access the server. To share

Akira Hayakawa 2 Jun 7, 2022
An inquiry into nondogmatic software development. An experiment showing double performance of the code running on JVM comparing to equivalent native C code.
An inquiry into nondogmatic software development. An experiment showing double performance of the code running on JVM comparing to equivalent native C code.

java-2-times-faster-than-c An experiment showing double performance of the code running on JVM comparing to equivalent native C code ⚠️ The title of t

xemantic 49 Aug 14, 2022
Data structures and algorithms for 3D geometric modeling.

geom3d Data structures and algorithms for 3D geometric modeling. Features: Bezier curve and surface B-Spline curve and surface Spin surface Sweep surf

Junfeng Liu 31 Sep 20, 2022
Comments
  • The scope of the unsafe block can be appropriately reduced

    The scope of the unsafe block can be appropriately reduced

    In this function you use the unsafe keyword for many safe expressions.

    We need to mark unsafe operations more precisely using unsafe keyword. Keeping unsafe blocks small can bring many benefits. For example, when mistakes happen, we can locate any errors related to memory safety within an unsafe block. This is the balance between Safe and Unsafe Rust. The separation is designed to make using Safe Rust as ergonomic as possible, but requires extra effort and care when writing Unsafe Rust.

    Hope this PR can help you. Best regards. References https://doc.rust-lang.org/nomicon/safe-unsafe-meaning.html https://doc.rust-lang.org/book/ch19-01-unsafe-rust.html

    opened by peamaeq 0
Owner
chuan
Open source enthusiast working to improve system programming for everyone.
chuan
GitHub
Rust crate to implement a counterpart to the PBRT book's (3rd edition) C++ code.

Rust crate to implement a counterpart to the PBRT book's (3rd edition) C++ code.

Jan Walter 763 Dec 27, 2022
This project contains small exercises to get you used to reading and writing Rust code

rustlings ?? ❤️ Greetings and welcome to rustlings. This project contains small exercises to get you used to reading and writing Rust code. This inclu

Cynthia Tran 1 May 24, 2022
Repository to learn fractal generation algorithms.

Fractalrs Created this project so I can study Rust while programming fractals! I have always wanted to learn fractal generation. Fractals Fractals are

Luke Dias 4 Jun 10, 2023
This Repo Contains my Week Long Journey Trying to Learn Rust Programming Language 🦀.

the-rust-way This Repo Contains my Week Long Journey Trying to Learn Rust Programming Language ?? . ?? Thanks to all Wonderful Contributors Thanks a l

Kanishk Pachauri 7 Oct 20, 2022
This repo contains the schedule for summer paper meetup

21' Summer ?? Paper Meetup Annoucement ?? 6/21/2021: our first summer love paper meetup will start on July 10th, 2021. Papers to contribute ?? Check o

msft system virtual meetup 24 Sep 22, 2022
In this repository you can find modules with code and comments that explain rust syntax and all about Rust lang.

Learn Rust What is this? In this repository you can find modules with code and comments that explain rust syntax and all about Rust lang. This is usef

Domagoj Ratko 5 Nov 5, 2022
Elemental System Designs is an open source project to document system architecture design of popular apps and open source projects that we want to study

Elemental System Designs is an open source project to document system architecture design of popular apps and open source projects that we want to study

Jason Shin 9 Apr 10, 2022
The source code that accompanies Hands-on Rust: Effective Learning through 2D Game Development and Play by Herbert Wolverson

Hands-on Rust Source Code This repository contains the source code for the examples found in Hands-on Rust. These are also available from my publisher

Herbert 261 Dec 14, 2022
Source code for the book Rust in Action

Welcome to Rust in Action source code This source code repository is a companion to the Rust in Action book available from Manning Publications. Suppo

Rust in Action 1.3k Dec 30, 2022
Source code of Ferrocene, safety-critical Rust toolchain

Ferrocene is a toolchain to enable the use of the Rust programming language in safety-critical environments. It is a proper downstream of the main Rus

Ferrocene 530 Oct 7, 2023