Add more algorithms in Rust Language

[r0hit-gupta]

This issue is fairly easy and most beginners should be comfortable implementing algorithms of their choice in Rust. In case of any problem, raise an issue or just discuss it below.

Graphs

• [ ] DFS

Dynamic Programming

• [ ] Longest increasing subsequence()
• [ ] Rod cut
• [ ] Egg Dropping Puzzle

Data Structures

• [ ] Graph
  • [ ] Directed
  • [ ] Undirected
• [ ] Trie
• [ ] AVL Tree

General

• [ ] N-Queens
• [ ] Graph Coloring
• [ ] Run Length Encoding

Project Euler, LeetCode, etc.

• Currently, we don't accept problems from those and similar websites

[0xazure]

@r0hit-gupta I'm still getting my feet wet with Rust, but I wouldn't mind taking a stab at insertion & selection sort along with some tests for them.

[nlynchjo]

@r0hit-gupta I am also looking for a first time contribution! Mind if I take on some of the data structures?

[r0hit-gupta]

@0xazure @nlynchjo Please feel free to contribute and work on anything you like. Take an idea from other repositories if you do not know how to begin. Send a pull request and if there is something not right, we will let you know. Cheers!

[darkkeh]

@r0hit-gupta I'll take a crack at the KMP string pattern matching 👍

[bofh69]

@0xazure - sorry, I didn't read your comment until now. I just added a PR with insertion sort.

[0xazure]

@bofh69 thanks for letting me know! I hadn't actually started implementing it yet, so I'll focus on the selection sort. I'm definitely interested in how you did it in Rust, so I'll have a look at your PR!

[bofh69]

@0xazure Great! I felt a bit stupid not checking the comments here first... My solution is probably not the best, I'm still learning Rust, but now it is decent.

[eisterman]

I'm actually working on Merge Sort

[AnshulMalik]

I think there is already a PR for Merge Sort @eisterman

[Jay9596]

I'd like to work on implementing Queue, if no one has claimed it.

[AnshulMalik]

Go ahead @Jay9596 :)

[teskje]

I'd like to try my hands on heap sort.

[DanielSauve]

I'll take a shot at making a Stack

[BaxterEaves]

I'm up for k-means, but i'm not aware of a dynamic programming algorithm for data with more than one dimension. I can implement the more general iterative algorithm if you like.

[pickfire]

I am interested in caesar cipher.

[AnshulMalik]

Give it a try @BaxterEaves and @pickfire 👍

[elpiel]

I've added another Merge Sort implementation, I will try to do some other as well PR #57 PS: I didn't see that it's already implemented :grin:

Update: Binary tree PR #58

[pickfire]

@AnshulMalik I have added the caesar cipher https://github.com/TheAlgorithms/Rust/pull/55

[leviathanbeak]

@r0hit-gupta I add PR for Longest common subsequence, still not merged ?

[sstadick]

I will take a crack at a few of these! It looks like there's a Radix Sort PR in progress, what's the status there?

[kitlith]

I noticed Linked Lists are listed, I think this does the subject the most justice: https://rust-unofficial.github.io/too-many-lists/

[fabrizzioalco]

Hey I'll try to do Dijkstra algorithm

[douglasvmo]

would like to work on coin change, what's the status?

[pgimalac]

I'm not sure sharing solutions of the Project Euler is a very good idea, I think it goes against the objective of the challenges...

[joao-conde]

@r0hit-gupta Im thinking on contributing. Can I implement the following:

1. dynamic_programming/01_knapsack.rs
2. dynamic_programming/coin_change.rs

[marnagy]

@r0hit-gupta Hello, I am a bit new to Rust, but can I make implementations of:

• Trie
• Graph ?

[ghost]

I wonder if there are enough reviewers in this repository. Some PR is not reviewed for months, and it reduce the committer's motivation.

[pickfire]

@ayaankhan98 If no one is currently maintaining it, I can help to temporary maintain the repo to reduce the amount of open pull requests and help to review them at the same time if I have time.

[ayaankhan98]

@ayaankhan98 If no one is currently maintaining it, I can help to temporary maintain the repo to reduce the amount of open pull requests and help to review them at the same time if I have time.

Yes, sure @pickfire go ahead. Thanks for your support.

[cfvescovo]

If you need any help, count me in too. I would be glad to help you maintain the repo.

[marnagy]

Is there any algorithm I can help with? Contact me if I can help with anything.

[jonakr]

I would like to implement the following algorithms with a fellow student as a project for our Rust lecture at the Corporate University DHBW Stuttgart.

• Transposition Cipher
• n-queens Problem
• Rod cut

[alexfertel]

Hello! I see this repo is unmaintained, but I think it provides a lot of value for the community, so I decided to make my own, which you can find in https://github.com/alexfertel/rust-algorithms.

I started by adding the sorting algorithms but feel free to contribute with your own. 🚀

[siriak]

Hi @alexfertel, I'm cleaning up this repo at the moment and will continually review new submissions, so feel free to contribute here too :)

[shadiakiki1986]

n-queens: https://github.com/insou22/typing-the-technical-interview-rust/

[MatheusMuriel]

Hello, i will work on DFS Graph Algorithm

[iamdejan]

Kruskal is already in PR: https://github.com/TheAlgorithms/Rust/pull/129

[Azeajr]

Hello, I wanted to work on Queue since PR: #25 was closed. Or should I work on a different algorithm?

Forget it just checked the actual repo and I see that queue is implemented. #229

Instead has anyone started working on BFS?

[siriak]

@Azeajr seems like no one is working on that at the moment, but you can check open PRs to be sure

[elpiel]

Dijstra is actually implemented but not marked as one @r0hit-gupta

[github-actions[bot]]

This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[erfan-khadem]

I think we can implement some items on this list:

Math

• [x] Random number generation:
  • Basic implementation (#311)
  • Still many more features can be implemented there (like having other distributions, having random floats, randoms in a range, etc.)
• [x] Integer factorization (#291)
• [x] FFT (#293)
• [x] Integration (for general functions) (#300)
• [ ] Polynomial manipulation:
  • integration
  • differentiation
  • inversion
  • exponentiation, calculating logarithm
  • many more operations
• [ ] Matrix operations:
  • Addition, subtraction, multiplication, transposition (#326, Non generic and doesn't implement traits)
  • LU decomposition
• [x] Gaussian elimination (#328)
• [ ] Big number implementation:
  • At least supporting addition, subtraction, multiplication, conversion to and from strings
  • Division is optional
• [ ] Chinese Remainder Theorem (with big number support)
• [x] Discrete logarithm (#301)
• [ ] Discrete and primitive root

Graph and Trees

• [x] Lowest common ancestor (#294)
• [x] Prufer encoding (#289)
• [x] Huffman encoding (#321)
• [x] Strongly Connected Component tasks (#309)
• [x] Heavy Light Decomposition (#310)
• [x] Centroid, centroid decomposition (#314)
• [x] Max flow:
  • Dinic's algorithm (#323)
  • Push relabel algorithm
  • MPM algorithm
• [ ] Bipartite matching (can be implemented using max flow too)
• [ ] All pairs shortest path
• [ ] Eulerian path
• [ ] 2-SAT

Searching

• [x] Ternary search (#297)

Strings

• [ ] Suffix array, suffix tree

I'm sure I'm missing many algorithms.

[mime8]

Hi, all! I'd like to work on ternary search algorithm, if no one else is working on it.

[erfan-khadem]

Hi, all! I'd like to work on ternary search algorithm, if no one else is working on it.

Awesome! I added your name to the list.

[b42thomas]

Hey y'all, I'm looking to make my first contribution. I would like to work on the matrix operations. Should that be separated into different PRs for addition, subtraction and multiplication?

[siriak]

@b42thomas depending on how complex they are. If you're implementing naive approaches, they can be merged together, if some complex algorithms, better to do them separately

[erfan-khadem]

@siriak I have a question: I want to implement a few graph algorithms, and if they are represented using BTreeMap, a log(n) factor would be added to their time complexity (obviously.) So can I only implement the algorithms for graphs with vertices numbered from 1 to n and having &[Vec<usize>] as their adjacency list?

I know we are supposed to create generic algorithms, but adding a log(n) to max flow wouldn't make anyone happy.

[siriak]

@er888kh, I think we can have both versions. Depending on the task at hand, both can be useful.

[erfan-khadem]

@er888kh, I think we can have both versions. Depending on the task at hand, both can be useful.

That's certainly an option, but it would create a lot of duplication (or at least generics boiler plate)

Another solution is to have a seperate implementation that enumerates graphs represented using BTreeMap to a convenient representation. Then anyone can use that instead. As an added bonus, this solution wouldn't change the time complexity, as iterating over a BTree can be done in O(n).

I will implement the option you choose (my code wouldn't be ready for at least a few days though, I'm too busy)

[siriak]

Agree, let's implement for the from 1 to n case then

[mime8]

While my PR for ternary search is still in review, I'd like to work on Ternary Search Tree. I don't see this data structure in the project.

[mhorst00]

@leonamtmann and me want to implement a couple of algorithms requested here. Right now we are working on these 3:

• Gauss-Elimination
• Newton-Raphson method derivation
• Basic matrix operations: add, subtract, multiply

All of these should be generic.

[erfan-khadem]

Now that I have added (#309), it should be really easy to implement 2-SAT problem's solution. Here is my CPP implementation if anyone is interested.

[erfan-khadem]

@siriak, what is your opinion about moving towards creating a general purpose crate for crates.io? We already have the "basic infrastructure" and people can really benefit from these implementations.

[siriak]

In general, I like the idea, but let's discuss it in more detail on our Discord server https://discord.gg/adJacSyV

[erfan-khadem]

I have an idea for implementing big number support:

First, One can implement a really basic base 10 big number module. It only supports addition and multiplication by 2. It can be formatted as a string and can be created from a string.

After that, a big number module can be implemented that is basically just a BitSet with usual operations (addition, multiplication, division, ...). Converting to and from strings can then be handled using the base 10 implementation.

Right now I am just way too busy, and I will not have time to implement these, plus the second one will have a ton of boring boilerplate. Can someone implement (or even just partially implement) any of the above modules?

Also, there might be simpler approaches to this problem, so other suggestions are welcome.