proalgos / proalgos-cpp

C++ implementations of well-known (and some rare) algorithms, while following good software development practices

ProAlgos: C++

This project is focused on implementing algorithms and data structures in C++, while following good software engineering practices, such as:

• Writing well-documented code
• Adhering to code guidelines
• Writing and passing unit tests
• Reviewing each other's code

Goals

1. Implement algorithms and data structures
2. Learn to be better software developers
3. Guide one another on version control, unit testing, and algorithms

How to get involved

There are a few ways to get involved.

Want to contribute to open-source and get involved with the project?

1. Read the contribution guidelines
2. Fork the repo
3. Create an issue describing what you'd like to add, or claim an issue that's up for grabs
4. Create a branch and add your code
5. Submit a pull request and reference the issue it closes

You can find more details regarding the steps above in the contribution guidelines, so be sure to check them out.

Just want to suggest a new algorithm or report a bug?

Create a new issue and we'll handle it from there. 😄

Contents

✅ = has unit tests

Algorithms

• Backtracking

  • N-Queens ✅

• Dynamic programming

  • 0-1 knapsack ✅
  • Coin change ✅
  • Longest decreasing subsequence ✅
  • Matrix chain multiplication ✅
  • Maximum sum contiguous subarray: Kadane's algorithm ✅
  • Rod cutting ✅
  • Weighted activity selection ✅

• Number theory

  • Binomial coefficient ✅
  • Euclidean algorithms
    • Greatest common divisor (GCD) ✅
    • Extended Euclidean algorithm (Bézout coefficients) ✅
  • Fast exponentiation ✅
  • Nth Fibonacci number
    • Linear time algorithm ✅
    • Logarithmic time algorithm ✅
  • Perfect number check ✅
  • Prime numbers
    • Primorial ✅
    • Sieve of Eratosthenes (simple) ✅

• Searching

  • Binary search ✅
  • Linear search ✅
  • Ternary search ✅

• Sorting

  • Bubble sort ✅
  • Bucket sort ✅
  • Comb sort ✅
  • Counting sort (stable) ✅
  • Heap sort ✅
  • Insertion sort ✅
  • Merge sort ✅
  • Quick sort ✅
  • Radix sort
  • Selection sort ✅
  • Shell sort ✅

• String

  • Longest common subsequence ✅
  • Searching (pattern matching)
    • Knuth-Morris-Pratt ✅
  • Edit Distance Problem ✅
  • Shunting yard ✅
  • Permutation
    • Heap's Algorithm ✅

Data structures

• Linked List

  • Singly linked list ✅
  • Doubly linked list ✅

• Queue

  • Queue ✅

• Set

  • Disjoint-set ✅

• Stack

  • Stack ✅

• Tree

  • Binary search tree ✅
  • Fenwick tree ✅

Compiling

To compile the source files, run make from the C++ directory. Doing so will create executable binaries in the bin directory.

To compile and run all tests, run make test. This will compile all the tests (in the same way as described above) and will run them, displaying the results.

In order to run a specific test and see its results, run it manually from the bin directory after calling make. For example, this command (executed from bin) would run only the unit tests for the N Queens algorithm:

$ ./n_queens

To remove all of the files created during compilation, run make clean. You need not do this every time you make some changes to a file and want to recompile it. Just run make and it will re-compile just those files whose contents have changed.

To see what happens in the background during compilation and testing, see the following files:

• Makefile
• CMakeLists.txt
• Testing script

For more information on make, see the GNU make Manual. For more information on CMake, see the CMake Tutorial.

Maintainers

This project is actively maintained by @alxmjo, and inactively by @faheel.

License

This project is licensed under the terms of the MIT license.

proalgos-cpp's Issues

String Processing Algorithms

Hi,
What about String Processing Algorithms, such as the classic Knuth-Morris-Pratt (KMP) and the Needleman-Wunsch? Can I work on those to add to the project?

Median in a stream of integers

I would like to add an algorithm that calculates the median in a stream of running integers.
Time Complexity:O(N^2)

Tests

I'm interested in writing test code for these algorithms, will as much code coverage as possible. Is that something you would like to have in this project?

Heap sort

Hey I'm Satchin, a fellow CE student, I noticed there weren't any algorithms in the repo/pull for heapsort and a few other.

• May I take the task up of adding this?

• And if there are any others do I just simply create the pull request for each?

Unit tests

Add unit tests for the following programs:

• N-Queens
• Kadane
• LCS
• KMP
• Searching
  • Common test for linear search and binary search
  • Ternary search*
• Sorting
  • Common test
  • Radix sort

* Ternary search currently has a unit test but it needs to be refactored.

Continuous integration

To-do

• Reorganise the project
• Write a Makefile to automate compilation, building and testing
• Integrate with Travis CI and AppVeyor

References

• https://github.com/faheel/Sample-Cpp-CI

Median from datastream code for review

Hi, master, I would like to present you my code link for review, if you think it's good enough for contribution, then tell me, I will send a PR for the same.Here is code link:https://github.com/ayushagg31/codelick/blob/master/DSA/Random-Algorithms/median_from_datastream.C

Also if you can review my repo and tell me about which algo I can contribute from this repo of mine https://github.com/ayushagg31/codelick/tree/master/DSA. that would be great help/

Size of input should be a natural number

Sorting programs may crash if size of input values is negative.
Modify the function getInputSize to check that size >= 0. In case it's not, then display:

Invalid input size! Try again.

and prompt to input size again (through a recursive call to getInputSize).

Also add a condition, that if size is 0, the program should display:

Nothing to sort here.

and exit.

Fast Power Algorithm

Fast Power algorithm isn't present in "Number Theory" folder. It's an algorithm for calculating exponentiation in O(log(N)) time.
I'd like to contribute by adding it.

Priority Queue implementation using heaps.

I would like to contribute the priority queue implementation using heaps.
With operations like insert, getmaxpriority, delmaxpriority.

Basic BigInteger class to handle big numbers of arbitrary length

Create a data structure that can handle numbers of arbitrary length by writing a BigInteger class that supports the following basic mathematical functions:

• add
• subtract
• multiply
• divide
• modulo

by overloading existing operators for each function (+, -, *, /, %)

The class should also use overloaded >> and << operators to get input from the standard input stream (std::cin) and to write output to the standard output stream (std::cout) respectively.

The path for the file that contains the class should be DataStructures/BigInteger/BigInteger.hpp

Linked list algorithms

There is no linked list data structure present here. Can I add some commonly used linked list algorithms like reversing a linked list, floyd-cycle finding algortithm etc.

Diameter of a tree using BFS/DFS

Just suggesting, you can add this one too in your repo.

B+ Trees

I would like to add code for B+ trees that supports insertion, traversal, and key search.

Radix Sort

Hello, I noticed you don't have radix sort in here. Would you mind me contributing one?

Can I add these algos, and where?

I want to add algorithms like

• Karastuba's Fast Multiplication
• Fast Power
• GCD
• Is Prime

Where should I add it. Or shouldn't I ?

Add documentation for all data structures and algorithmic functions

Add a README to each directory containing proper documentation for algorithms or data structures in that directory.

Implementation of Linked List's functions?

Red-black trees

I will implement the RedBlack trees and its important features

Merging two Binary Search Trees

I would like to add an algorithm to merge two balanced Binary Search Trees in O(M+N) time, where M is number of nodes in first tree and N is number of nodes in second tree.

make algorithms generic (templated)

I notice it seems like all the functions that implement algorithms take in a specific container as part of the argument (std::vector it seems like). I think these functions should be templated and made generic. If the container cannot be worked on by the function then a compile error should occur.

Various tree data structures and related algorithms

Algorithms on Trees, Union Find, Heaps,Maps,Hashing

Mention time and space complexities in comments

For each algorithm, mention its time complexity and space complexity in the "description comment" of its implementation program.

The format for the "description comment" (which is written at the beginning) should be:

/*
    <Name of algorithm>
    -------------------
    <Brief description>

    Time complexity
    ---------------
    O(...), where <description of variable(s)>    
    
    Space complexity
    ----------------
    O(...), where <description of variable(s)>
*/

Following are the algorithms for which time and space complexity hasn't been added yet:

• N-Queens
• Kadane
• Binary search
• Bubble sort
• Counting sort
• Insertion sort
• Merge sort
• Quick sort
• Selection sort

String algorithms

An issue for adding string algorithms -> Z algo, Manachers algo, Rabin-Karp algo.
If you are good with it, I can add them.

Bit Manipulation algorithms

I would like to implement bit manipulation algorithms, is this something that would fit well with your project? If so, let me know how you would like the files organized and I'll be happy to get started!

Fibonacci search

I would like to implement Fibonacci search on sorted arrays.

Add general contributing guidelines

Create CONTRIBUTING.md containing general contributing guidelines like adding description comment to each file, links to language-specific coding guidelines such as C++ Coding Guidelines, and more.

Matrix Chain Multiplication

Given n matrices A1, A2, ..., An, to be multiplied, determine how to parenthesize the matrices to minimize the total number of multiplications.

(This would be my first contribution, so I had some questions, and also would it work if I code it in Java? Thanks :) )

Binary search tree (Recursive and non recursive)

This needs implementation as discussed in this issue. I will start working on it.

Adding a Tower of Hanoi problem

Tower of hanoi is a classic example of recursion.I think it should be added in the list.

Add Shell sort

I think Shell sort algorithm will be a good add

Edit distance algorithm

I would like to implement edit distance algorithm for strings

Sudoku Solver using Backtracking

I would like to add a program for solving Sudoku using backtracking.

Euler Totient function

What about writing some code for computing the euler totient function?

It is defined as follows:
Given an integer n how many number <n are coprime with it?

It is a very common constant in number theory.

https://en.wikipedia.org/wiki/Euler%27s_totient_function

Would you mind if I submit a PR on this?

Wiki's content is not working

When I click on the links provided in "contents" page, it takes me to 404 error. I think it should be fixed.
I've also realized that it's not up to date.

Refactor code for sorting programs

Refactor code for sorting programs to be consistent with C++ coding guidelines.

Any implementation of depth-first search?

I see there is BFS implementation under review in issue #19, however only mention of DFS is in issue #25 that was closed by its author.
Can I give it a go?

Point QuadTree

I see that there are no point quad tree implementation here. Can I give it a go?

Bucket sort

Hey,
Bucket sort is not included . I would like to include it too.
Also according to issue #36 radix sort is still not there, I would like to add that too.

Adding a Problem that Sorts an Array in the Wave Form

Hey, I haven't come across this one among all the other algos that have been listed.Wanted to know if I could contribute to this one.

Depth First Search

I couldn't find if DFS is done before, if not, I could totally do that. (In java if possible)
Thanks

Construct Mirror Tree

I would like to implement the algorithm for constructing a mirror tree for given binary tree.

Add graph traversal algorithms

Create a folder named Graph in the root directory. Inside it, the following graph traversal algorithms are to be added:

• Breadth-first search (in Traversal/BreadthFirstSearch.cpp)
• Depth-first search (in Traversal/DepthFirstSearch.cpp)

Use either an adjacency list (recommended) or an adjacency matrix to implement an undirected weighted graph.

Use STL containers such as std::queue and std::stack for implementing a queue and stack respectively.

Create a header file named Graph.h (in DataStructures/Graph) and implement the basic functions for getting inputs from the user, such as:

• number of vertices
• number of edges
• starting vertex
• edge info (source, destination and weight)

Graph algorithms

Hello, do you have any graph algorithms implemented. I'd like to contribute with some if u haven't. I'll try to add one algo per week.

Bad Character Algorithm

i would like to add the bad character heuristic of the famous boyer moore algorithm

Add program that implements counting sort

Name the source file RadixSort.cpp and add it to the Sorting directory.

You should use the utility functions from SortingUtils.h.

For an overview of how the code should be structured, view implementations of other sorting algorithms, and also go through the C++ Coding Guidelines, if your implementation is in C++.

Also add proper comments!

References:

1. Counting sort - Wikipedia
2. Counting Sort - GeeksforGeeks

Add implementation of Disjoint Set data structure

Implement data validation

Could we add some data validation functions such as,
make upper case,
make lower case,
get random double,
get random int?

Linked list

Hello, I could add a template LinkedList I made some time ago for my Data Structures and Algs class, updated for C++11 of course. It would require adding both a .cpp and an interface file if that's alright.

Primorial

Implement an algorithm for calculating the primorial of a given prime number P_n