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

Overview

ProAlgos: C++

Travis status

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

Data structures

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:

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.

Comments
  • Implement data structures for graph algorithms

    Implement data structures for graph algorithms

    In order to add graph algorithms, we must first add graph data structures. We'll need data structures for both directed and undirected graphs. We'll want to be able to add vertices and edges. In the end it'll be valuable to have implementations for both an adjacency list and an adjacency matrix.

    If you're interested in adding this please explain your plan below so that we can get started. 🙂

    See #70 for previous conversation on the subject.

    Data structure Graph Inactive 
    opened by alxmjo 24
  • Testing sorting algorithms

    Testing sorting algorithms

    I'm trying to write tests for the sorting algorithms. I'm new to Catch (and unit testing in general), but based on my research I would expect this code (along with the rest of the setup you describe in UNIT_TESTS.md) to work:

    TEST_CASE("Normal cases", "[bubble_sort]") {
    	vector<int> unsorted1 {4, 3, 5, 2, 1};
    	bubble_sort(unsorted1, 1, false);
    	vector<int> sorted1 {1, 2, 3, 4, 5};
        REQUIRE(unsorted1 == sorted1);
    }
    

    Unfortunately when I run make test from the C++ directory I receive many, many lines in the terminal that look like this:

    profiling: /Users/alex/Programming/Algos/C++/build/sorting/bubble_sort.test.gcda: cannot merge previous GCDA file: corrupt arc tag (0x74726f70)
    profiling: /Users/alex/Programming/Algos/C++/build/sorting/bubble_sort.test.gcda: cannot merge previous GCDA file: corrupt arc tag (0x534e4573)
    profiling: /Users/alex/Programming/Algos/C++/build/sorting/bubble_sort.test.gcda: cannot merge previous GCDA file: corrupt arc tag (0x00000000)
    profiling: /Users/alex/Programming/Algos/C++/build/sorting/bubble_sort.test.gcda: cannot merge previous GCDA file: corrupt arc tag (0x65526576)
    profiling: /Users/alex/Programming/Algos/C++/build/sorting/bubble_sort.test.gcda: cannot merge previous GCDA file: corrupt arc tag (0x74617453)
    profiling: /Users/alex/Programming/Algos/C++/build/sorting/bubble_sort.test.gcda: cannot merge previous GCDA file: corrupt arc tag (0x00000000)
    profiling: /Users/alex/Programming/Algos/C++/build/sorting/bubble_sort.test.gcda: cannot merge previous run count: corrupt object tag (0x00000000)
    

    If, however, I include a "dummy" test à la REQUIRE(1 == 1) then it works fine.

    Any idea what I'm doing wrong here?

    Sorting Unit test 
    opened by alxmjo 17
  • Created Radix Sort

    Created Radix Sort

    I have created the code for Radix Sort. I hope that you like it. Please give me suggestions if I could have done anything better as this is my first pull request and would love to learn more.

    Sorting Algorithm 
    opened by Rajiv2605 17
  • Mention time and space complexities in comments

    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:

    • [x] N-Queens
    • [x] Kadane
    • [x] Binary search
    • [x] Bubble sort
    • [x] Counting sort
    • [x] Insertion sort
    • [x] Merge sort
    • [x] Quick sort
    • [x] Selection sort
    Good first issue 
    opened by faheel 17
  • Basic BigInteger class to handle big numbers of arbitrary length

    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

    Data structure 
    opened by faheel 14
  • Add BinomialCoeffcients.cpp

    Add BinomialCoeffcients.cpp

    This program computes (N choose K) using a recurrence relation and dynamic programming. I think that this program would be a good addition as it showcases basic dynamic programming, and because I feel as though dynamic programming implementations of this algorithm are hard to find.

    Number theory 
    opened by eskeype 12
  • Linked list algorithms

    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.

    Linked list Algorithm Inactive 
    opened by sarfrazbaig 10
  • Euler Totient function

    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?

    Number theory Algorithm Inactive 
    opened by knotman90 10
  • Update repo to reflect focus on C++

    Update repo to reflect focus on C++

    In short, this PR consolidates our READMEs and contributing documentation and makes several updates to language and folder structure. Please see further commentary in #346. I've elected to keep these as discrete commits (for now) to make it easier to see the specific changes proposed in the PR.

    These are significant changes, so I will leave this open for two weeks for reviews, comments, and suggestions.

    Closes #346 Closes #344

    Enhancement Documentation Reorganise 
    opened by alxmjo 9
  • Add data conversion functions

    Add data conversion functions

    Test cases for data validation function

    #99

    Unit test Inactive Utility Changes requested 
    opened by beardbytes 9
  • Migrate extended Euclidean algorithm

    Migrate extended Euclidean algorithm

    Migrate extended Euclidean algorithm to header file (as described in #163).

    Reorganise 
    opened by alxmjo 9
  • Algorithm for Reverse an Array

    Algorithm for Reverse an Array

    Creating a New Algorithm for Reversing Elements in an array and We can understand this simple Algorithm easily.

    //CODE

    #include #include using namespace std;

    //Reversing the first and last element then increasing (s) and decreasing (e) to next element and swap then after (s>e) Exit loop void reversearray(vector &arr, int n){ int s=0; int e=n-1; while(s<=e){ swap(arr[s++],arr[e--]); } }

    // Function will print the array void printarray(vector &arr, int n){ for(int i=0;i<n;i++){ cout<<arr[i]<<" "; } cout<<endl; }

    int main(){

    vector v; int a=0; while(cin>>a){ v.push_back(a); } int size=v.size(); reversearray(v,size); // Reverse Function Call printarray(v,size); // Printing Array Call

    return 0; }

    opened by Venerablevivek 0
  • Added Euler's Totient algorithm having square root time complexity wi…

    Added Euler's Totient algorithm having square root time complexity wi…

    opened by omkar-karke 0
  • Create euclid_totient.hpp issue #438

    Create euclid_totient.hpp issue #438

    working code for Euclid totient

    I have created a header file with a function to find Euclid Totient

    Closes #438

    opened by a-dtya 0
  • Euler's Totient

    Euler's Totient

    Euler's totient function (a.k.a. phi function) counts the number of positive integers from 1 to given number N that are coprime to N. That is, phi(N) is a number of positive integer m such that 1 <= m <= N and GCD(m, N) = 1.

    This is my first issue in opensource contribution Consider this as a contribution under hacktoberfest 2022.

    opened by omkar-karke 0
Owner
ProAlgos
Implementations of well-known (and some rare) algorithms, while following good software development practices
ProAlgos
Provide building blocks (software, hardware and algorithms) for implementing SLAM using small sensors

RemoteSLAM The purpose of this repo is to provide the building blocks (software drivers, hardware and algorithms) for implementing SLAM systems using

Autonomous Drones Lab, Tel Aviv University 38 Jan 20, 2022
Benchmarking algebraic effect handler implementations

Benchmarking Effect handlers. Currently supported libraries and languages are: kk (extension .kk), Koka. ml (extension .ml), multi-core OCaml.

Daan 21 Dec 18, 2021
Collection of algorithms and data structures in C++ and Java

Collection of algorithms and data structures in C++ and Java

Andrei Navumenka 1.7k Nov 30, 2022
A library of common data structures and algorithms written in C.

C Algorithms The C programming language includes a very limited standard library in comparison to other modern programming languages. This is a coll

Simon Howard 2.8k Nov 27, 2022
Several algorithms and data structures implemented in C++ by me (credited to others where necessary).

Algorithms This repository contains my implementations of several algorithms and data structures in C++ (credited to others where necessary). It has i

Petar Veličković 588 Nov 26, 2022
Fundamentals of Data structures and algorithms in c++

Data Structures & Algorithms About the repository: Contains theories and programming questions related to fundamentals of data structures and algorith

fifu 45 Oct 6, 2022
CXXGraph is a Header-Only C++ Library for Graph Representation and Algorithms

CXXGraph is a small library, header only, that manages the Graph and it's algorithms in C++. In other words a "Comprehensive C++ Graph Library".

ZigRazor 181 Nov 28, 2022
Header-only C++ library for robotics, control, and path planning algorithms.

Header-only C++ library for robotics, control, and path planning algorithms.

null 357 Nov 25, 2022
c++ library including few algorithms and datastructures

c++ library including few algorithms and datastructures

null 2 Dec 25, 2021
Every week exercises for Introduction to Algorithms and Programming

cen109-algorithms commands to compile and link C and C++ programs gcc filename.c -o executableFileName g++ filename.cpp -o executableFileName filename

null 3 Mar 19, 2022
c language's datastruct and algorithms.

cdsaa 介绍 学习数据结构与算法的C语言实现 主要数据结构 动态字符串 动态数组 单向链表 栈 主要算法 更新中. . . 目录结构 |-- include |---- CArray.h 动态数组 |---- CList.h 单向链表 |---- CStack.h 栈 |---- CString

Ticks 1 Nov 24, 2021
Snowball compiler and stemming algorithms

Snowball is a small string processing language for creating stemming algorithms for use in Information Retrieval, plus a collection of stemming algorithms implemented using it.

Snowball Stemming language and algorithms 600 Dec 1, 2022
An algorithm to compute the coefficients of a function development in a spherical harmonics convergent series

An algorithm to compute the coefficients of a function development in a spherical harmonics convergent series

Gianluca Bianco 20 Sep 18, 2022
Collection of various algorithms in mathematics, machine learning, computer science, physics, etc implemented in C for educational purposes.

The Algorithms - C # {#mainpage} Overview The repository is a collection of open-source implementation of a variety of algorithms implemented in C and

The Algorithms 15k Nov 25, 2022
Algorithms & Data structures in C++.

Algorithms & Data Structures in C++ 目标 ( goal ) : 经典的算法实现 (classical algorithms implementations) 服务器端 (based on linux/gcc) 正确,易于使用和改造, 一个头文件一个算法,并附带一个

xtaci 4.7k Nov 30, 2022
This repository contains path planning algorithms in C++ for a grid based search.

This repository contains path planning algorithms in C++ for a grid based search.

null 239 Nov 30, 2022
Library for building multi-level indoor routes using routing algorithms.

Library for building multi-level indoor routes using routing algorithms. You can easily construct routing graphs and find the shortest path for optimal indoor navigation.

Navigine 5 Nov 21, 2022
This library contains a set of algorithms for working with the routing graph.

Library for building multi-level indoor routes using routing algorithms. You can easily construct routing graphs and find the shortest path for optimal indoor navigation.

Navigine 5 Nov 21, 2022
IntX is a C++11 port of IntX arbitrary precision Integer library with speed, about O(N * log N) multiplication/division algorithms implementation.

IntX IntX is a C++11 port of IntX arbitrary precision Integer library with speed, about O(N * log N) multiplication/division algorithms implementation

Telepati 9 Mar 9, 2022