This PR adds a project_euler directory and a few guidelines to the respective readme. Project Euler solutions were originally requested in #3.

It also adds a solution for problem 3.

This PR adds a project euler section to the repo and includes an example solution for problem 1 This mirrors the python repo seen here https://github.com/TheAlgorithms/Python/tree/master/project_euler

hey, I recently had an assignment where I had to benchmark two sorting algorithms(selection and quick) against each other in order to create a hybrid, and did this using the sorting algorithms from this repository. I wrote the benchmarks using criterion, and was wondering if you would be open to adding benchmarks to this repository, it should be fairly trivial to take the benchmarks I created and refactor them to do benchmark all the comparative based sorting algorithms against each other.

you can find the benchmarks here and I'll be adding the markdown version of the actual report shortly

Cipolla algorithm for Quadratic Residue problem

Solving quadratic residue problem: x^2 = a (mod p) , p is an odd prime with O(M*log(n)) time complexity, M depends on the complexity of complex numbers multiplication.

Wikipedia reference: https://en.wikipedia.org/wiki/Cipolla%27s_algorithm If a is Quadratic Nonresidues, return None; Otherwise return two solutions (x1, x2)

Added Miller Rabin test.

I was wondering if some graph algorithms should be added. I think we are missing quite a few important and useful algorithms (all pairs shortest path, bipartite matching, max flow, ...). What do you think should be implemented first (graph or otherwise)?

The linked_list module stores references to nodes using NonNulls that are never dropped at any point. Unless there is something I missed, this code doesn't ever free the memory allocated to the nodes.

With Hacktoberfest coming, I thought it might be a good idea to devise a strategy beforehand so that our contributors and community can make the most out of this event.

There are many, many algorithms out there, with variable degree of utility, that can be implemented by contributors, but most of them won't be of particular value, even though they can't be rejected. For example we won't be benefiting from yet another sorting algorithm with terrible run time behavior that was mentioned in $textbook.

As such, it might be a good idea to somehow curate a to-do list with tasks of various difficulty levels for participants. The tasks need not be strictly coding related, but I can think of at least a few areas where we could benefit from having lots of new code (bignum, random and crypto to name a few.)

We can also start thinking of a new direction: Something like collecting all the accumulated knowledge here in a book or blog like platform to guide not only new learners, but also enthusiasts that could benefit from "human-readable" implementations of complex systems (like cryptography or random number generation for instance). One thing to keep in mind with this approach is that it will take a lot of polishing before it becomes anything useful.

To summarize, we need a strategy to make the most of this year's hacktoberfest. At very least a to-do list for new code and algorithms, but we may decide (and vote) to start being something more than a "just" repository to store algorithms. I think this issue might be a good place to start discussing our options.

this is something we are covering in my algorithms course. it's possible to create algorithms that switch between different strategies based off the size of the input. for example this hybrid of selection sort and quick sort (using Hoare's partition scheme consistently outperforms a regular quick sort by a constant factor:

`
pub fn hybrid_quick_sort<T>(arr: &mut [T])
where
    T: Ord + Clone,
{
    let len = arr.len();
    if len > 17 {
        _hybrid_quick(arr, 0, len - 1)
    } else {
        selection_sort(arr)
    }
}

fn _hybrid_quick<T>(arr: &mut [T], lo: usize, hi: usize)
where
    T: Ord + Clone,
{
    if lo < hi {
        if hi - lo > 17 {
            let p = partition(arr, lo, hi);
            _hybrid_quick(arr, lo, p);
            _hybrid_quick(arr, p + 1, hi);
        } else {
            selection_sort(&mut arr[lo..hi + 1]) //from first element to include to first element to exclude
        }
    }
}

I remember that rust's index is from 0, and your code is

pub fn add(&mut self, value: T) {
        self.count += 1;
        self.items.push(value);

        // Heapify Up
        let mut idx = self.count;
        while self.parent_idx(idx) > 0 {
            let pdx = self.parent_idx(idx);
            if (self.comparator)(&self.items[idx], &self.items[pdx]) {
                self.items.swap(idx, pdx);
            }
            idx = pdx;
        }
    }

the idx should be self.count - 1 and the parent_index, left_child_index, right_index are wrong too, the parent_index should be (index - 1) / 2, left_child should be 2 * index + 1, right_child should be 2 * index + 2

There are multiple problems in the repo that fall under CSP. Essentially a list of variables and constraints between them. It is not an algorithm but a class of problems that can be modeled in such a way, such as sudoku, n queens, graph coloring. There are multiple ways to solve them, one being backtracking. Could be considered a data structure? Otherwise I don’t know where it would live. I recently did an assignment for school in golang to make a sudoku and killer sudoku solver where we convert to a generic CSP to solve.

Where could this live in the repo? It’s difficult to define every constraint that a problem would use but you can cover most problems with EQUALS and NOT_EQUALS constraints. Or maybe there is a good way to define constraints by passing in some lambda functions. I’m not super experienced in rust but this could be something I’d be interested to contribute.

In the existing logic, if $u == v$, $v$ is considered as unreachable, while the distance (or cost) should be $0$ instead. This PR is to add that logic and corresponding test cases.

Generic matrix struct and macro

Description

As a personal exercise, I tried to implement a Matrix struct which encompasses all matrix operations defined in the matrix_ops.rs file and also some custom ones. I used a custom trait MatrixElement to make it generic and you can build matrices idiomatically using the "matrix!" macro.

I'm not quite sure how useful this is, it was made as a learning experience for myself, but I'm making a pull request just in case. Also, any feedback is very much appreciated as rust is very new to me still.

Type of change

• [x] New feature (non-breaking change which adds functionality)

Checklist:

• [x] I ran bellow commands using the latest version of rust nightly.
• [x] I ran cargo clippy --all -- -D warning just before my last commit and fixed any issue that was found.
• [x] I ran cargo fmt just before my last commit.
• [x] I ran cargo test just before my last commit and all tests passed.
• [x] I checked COUNTRIBUTING.md and my code follows its guidelines.

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

• [x] Big number support (#371)
• [ ] Chinese remainder theorem (WIP @Logicless-Coder)
• [ ] Elliptic curve operations

Graph

• [x] 2-SAT (#345 )
• [ ] Eulerian path
• [x] All pairs shortest path (#366)
• [ ] Bipartite matching
• [ ] A*

Strings

• [ ] Suffix array
• [ ] Suffix tree

Cryptography

• [x] A generic implementation for HMAC (#351)
• [x] Salsa20 and Chacha20 (#363)
• [x] Poly1305 message authentication code (#371)