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 😁

Update:
Binary tree PR #58

[pickfire]

@AnshulMalik I have added the caesar cipher #55

[erfan-khadem]

I think we can implement some items on this list:

Math

• Random number generation:
  • Basic implementation (Add Permuted Congruential Generator #311)
  • Still many more features can be implemented there (like having other distributions, having random floats, randoms in a range, etc.)
• Integer factorization (Add Pollard's Rho algorithm #291)
• FFT (Add Fast Fourier Transform #293)
• Integration (for general functions) (Add Simpson's Rule for Integration #300)
• Polynomial manipulation:
  • integration
  • differentiation
  • inversion
  • exponentiation, calculating logarithm
  • many more operations
• Matrix operations:
  • Addition, subtraction, multiplication, transposition (Added matrix operations #326, Non generic and doesn't implement traits)
  • LU decomposition
• Gaussian elimination (Added 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)
• Discrete logarithm (Add Baby-step Giant-step algorithm #301)
• Discrete and primitive root

Graph and Trees

• Lowest common ancestor (Lowest common ancestor #294)
• Prufer encoding (Add prufer-code #289)
• Huffman encoding (Add Huffman Encoding #321)
• Strongly Connected Component tasks (Add Tarjan's Strongly Connected Components algorithm #309)
• Heavy Light Decomposition (Add Heavy Light Decomposition #310)
• Centroid, centroid decomposition (Add Centroid Decomposition #314)
• Max flow:
  • Dinic's algorithm (Add Dinic's Max Flow 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

• Ternary search (Ternary Search Algorithm #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.

[kou-sia]

@siriak
I want to run＿length＿encoding.
This is because 'burrows_wheeler_transform' is already implemented and it would be beneficial to add 'run_length_encoding' (PR369) to the library, which is often performed following this algorithm.

[kou-sia]

I've implemented it before.
So if you want to add run length, I suggest you revamp the existing source code.
What do you think?

https://github.com/TheAlgorithms/Rust/commits/master/src/string/run_length_encoding.rs

[github-actions]

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.

[github-actions]

Please ping one of the maintainers once you add more information and updates here. If this is not the case and you need some help, feel free to ask for help in our Gitter channel. Thank you for your contributions!