Algorithms and datastructures road map
erfan-khadem opened this issue · 23 comments
Since #3 is already overcrowded and we need to have our roadmap somewhere visible, I figured I should open a new issue. The list is currently my own to-do list, and maintainers' suggestions, additions, and ideas in general will be incorporated here. Also suggestions from community are welcome.
Maths
- Big number support (#371)
- Chinese remainder theorem (WIP @Logicless-Coder)
- Elliptic curve operations
Graph
Strings
- Suffix array
- Suffix tree
Cryptography
Seems like a cool datastructure!
Should I add it as WIP by you @YurySolovyov ?
No, I'm still relatively new to rust, so I don't want to claim this item, it was purely a suggestion. HAMT combines hashing, trees and some binops, so I was hoping to learn how it can be done, that's all.
No, I'm still relatively new to rust, so I don't want to claim this item, it was purely a suggestion. HAMT combines hashing, trees and some binops, so I was hoping to learn how it can be done, that's all.
Maybe you can start by implementing the hash function for HAMT first, because datastructures are known to be a bit tricky to implement in rust, and this certainly isn't a trivial one.
In any case, you are more than welcome to contribute. Some other options you have are:
1- ChaCha20. Just open RFC8439 and start writing code. This can be implemented in ~30 LoC.
2- All Pairs Shortest Path.
3- Bipartite matching. Use Dinic which is already implemented.
Edit:
No.1 was implemented. Poly1305 specs can be found at the same RFC, but implementing it is a bit more challenging.
@siriak
Can we use a third party library for bignum support? I really want to implement some cool stuff with elliptic curves (e.g. Lenstra ECM, Diffie-Hellman, MQV method, etc.), but creating bignum support from scratch is a big undertaking and a bit futile (either the code won't be readable/educational, or would be prohibitively slow). Maybe we can hide the code that depend on 3-rd party library behind a feature flag, such that "normal" builds don't pull the dependency?
@er888kh Are you talking about
BigIntegerandBigDecimalfromjava.math? Sure
Yes. I'm not sure if using one of the gmp interfaces makes sense (I don't have windows, I'm not sure whether windows users can easily compile gmp C library or whether it can be retrieved automatically), but in case that's possible, it would be the best solution.
The other solution is to use one of the native rust based implementations. But that would come with a hefty performance penalty (nothing beats literally decades of hand optimized assembly code).
Ooops, wrong repo :) I thought it was in the Java repo :) I don't have a Windows pc either, so can't comment about gmp. It's up to your discretion as I don't have an opinion on that matter
@siriak
I implemented poly1305 using num-bigint library. Once that is merged, we can move on to other stuff. For example elliptic curve code shouldn't be that hard once I implement some primitive operations/algorithms.
Could I request the A* (a.k.a. A-star) graph search algorithm wiki?
See the original paper and possibly the NetworkX implementation.
Could you please look at my PR #377 for Bipartite Matching. If found suitable, I can add Hopcroft Karp in a similar fashion
Hi, if anybody could review my PR #378
Hi, if open I would like to pick up "Chinese Remainder Theorem" under the "Math" category.
@Logicless-Coder #413 if you think you can improve it please go ahead and make a commit
@GentBinaku are there any known issues/bugs/improvements?
@Logicless-Coder The test pass and the checks pass, so you might dig more into it if you want too
@GentBinaku The test cases were weak, I found a test which fails and found the problem being in the modinverse function. It requires usage of extended Euclidean algorithm and not just the regular Euclidean algorithm of calculating GCD. I am writing the extended algorithm next to verify this claim.
@Logicless-Coder Please do I would like to see the code
Hi admin,
i would like to work on Eulerian path
Hi , Suffix array can be implemented using external crate "suffix" with lesser lines of code ensuring optimistic code.
So, should i add it to this ? OR implement it using Manber-Myers algorithm which doesn't uses external crate but it can become more complex ?
What do you mean by using suffix crate? Just using their implementation of suffix array? I'd say using Manber-Myers algorithm is preferable because we must see implementation details
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.
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!