Repository files navigation

This project is focused on implementingalgorithms and data structures in C++, while followinggood software engineering practices, such as:

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

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

There are a few ways to get involved.

1. Read thecontribution guidelines
2. Fork the repo
3. Create an issue describing what you'd like to add, orclaim an issue that'sup for grabs
4. Create abranch andadd your code
5. Submit apull request and reference the issue it closes

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

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

✅ = has unit tests

• 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 ✅

• Linked List

  • Singly linked list ✅
  • Doubly linked list ✅

• Queue

  • Queue ✅

• Set

  • Disjoint-set ✅

• Stack

  • Stack ✅

• Tree

  • Binary search tree ✅
  • Fenwick tree ✅

To compile the source files, runmake from theC++ directory. Doing so will create executable binaries in thebin directory.

To compile and run all tests, runmake 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 thebin directory after callingmake. For example, this command (executed frombin) would run only the unit tests for the N Queens algorithm:

$ ./n_queens

To remove all of the files created during compilation, runmake clean. You need not do this every time you make some changes to a file and want to recompile it. Just runmake 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 onmake, see theGNU make Manual. For more information onCMake, see theCMake Tutorial.

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

This project is licensed under the terms of theMIT license.