C++

Algos: C++

Implementation of well-known (and some rare) algorithms, in C++.

Contents

✅ = has unit tests

Algorithms

• Backtracking
  • N-Queens
• Dynamic programming
  • Matrix chain multiplication ✅
  • Maximum sum contiguous subarray: Kadane's algorithm
• Number theory
  • Binomial coefficient ✅
  • Euclidean algorithms
    • Greatest common divisor (GCD)
    • Extended Euclidean algorithm (Bézout coefficients and GCD)
  • Fast exponentiation ✅
  • Nth Fibonacci number
    • Linear time algorithm ✅
    • Logarithmic time algorithm ✅
  • Perfect number check ✅
  • Prime numbers
    • Sieve of Eratosthenes (simple)
• Searching
  • Binary search ✅
  • Linear search ✅
  • Ternary search ✅
• Sorting
  • Bubble 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

Data structures

• Binary search tree
• Disjoint-set ✅
• Singly linked list

Compiling

To compile the source files, run make all. Doing so will:

• create executable binaries in sub-directories under the bin directory, and
• create intermediate build files in sub-directories under the build directory.

The sub-directories will be the same as they are under source.

To compile and run the tests, run make test. This will compile all the tests (in the same way as described above) and will run them, displaying the results. Note that the test binaries will have .test at the end of their name.

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 all, and it will re-compile just those files whose contents have changed.

To know what happens in the background when make runs, you may read the Makefile. For more information on make, read the GNU make Manual.

Unit tests

If you would like to (and you should) add unit tests for the code you are contributing, or for some of the existing code, read about Adding unit tests for C++ code.

C++ Coding Guidelines

If you want to contribute an algorithm or data structure in C++, make sure to read the C++ Coding Guidelines apart from the general Contributing Guidelines. This will help in ensuring that your code conforms to the style followed in this project.