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.