Giter Club home page Giter Club logo

cardigan's Introduction

Cardigan

Build Status

This is a repository dedicated to implementing algorithms and data structures in C++.

Contents

Getting started

If you wish to contribute to the repo, then view the contributing guide. Otherwise, you can clone the repo with git clone https://github.com/camilne/cardigan.git. Then, checkout how to build the library and run tests.

Building

Follow these steps (from the root directory of the project) if you wish to build the library.

mkdir build
cd build
cmake ..
make

Testing

Follow these steps (from the root directory of the project) if you with to test the library.

mkdir build
cd build
cmake -Dtests=ON ..
make
./cardigan.test

Implementation status

This section details the current status of the contents of the library.

Feature Implemented Has Tests Location
AVL Tree ☑️ ✅ avl.hpp
Binary Search Tree ☑️ ✅ bst.hpp
Bubble sort ☑️ ✅ bubble_sort.hpp
Euclid's Algorithm ☑️ ✅ euclid.hpp
Fisher-Yates shuffle ☑️ ✅ fisher_yates.hpp
Longest common substring ☑️ ✅ longest_common_substring.hpp
Quicksort ☑️ ✅ quicksort.hpp

cardigan's People

Contributors

camilne avatar

Stargazers

avatar avatar

Watchers

avatar avatar

cardigan's Issues

Bubble sort test cases need unique names

Issue title

Bubble sort test cases need unique names

Issue description

Currently, bubble sort test cases have general names and cause Catch to not run any tests if another sorting algorithm is implemented and has test cases with the same names.

Proposed Fix:

  • Prefix bubble sort test cases with "Bubble sort: "
  • Modify unit test README to require prefixing test case names

Checklist

  • Check for existing issue
  • Check for existing pull request

Add quicksort

Issue title

Add quicksort

Issue description

Quicksort should be added. It should use a random pivot.

Checklist

  • Check for existing issue
  • Check for existing pull request

Add linear search

Issue description

Linear search should be added. It should take a begin and end iterator to a collection and search for a value.

Take a look at the sorting algorithm interfaces for an example.

Checklist

  • Check for existing issue
  • Check for existing pull request

Add binary search tree

Issue title

Add binary search tree

Issue description

A binary search tree should be added. Functionality to include:

  • Insert
  • Search
  • Delete
  • Traversals (Allow predicate to be performed for each node)
  • Lowest common ancestor
  • Should be extendable (to allow for AVL tree, splay tree, red-black tree, etc.)

Checklist

  • Check for existing issue
  • Check for existing pull request

Add Euclid's Algorithm

Issue title

Add Euclid's Algorithm

Issue description

Euclid's Algorithm is an efficient algorithm for finding the GCD of two natural numbers.

Checklist

  • Check for existing issue
  • Check for existing pull request

Add AVL Tree

Issue description

Add an AVL tree as a specialization of the BST.

  • Store height in nodes
  • Rebalance on insertion/deletion

Checklist

  • Check for existing issue
  • Check for existing pull request

Add insertion sort

Issue description

Insertion sort should be added. It should follow the style of already implemented sorting algorithms.

Checklist

  • Check for existing issue
  • Check for existing pull request

Add longest common substring

Issue title

Add longest common substring

Issue description

Finding the longest common substring finds the longest consecutive substring that is common between two input strings. This algorithm should be generalized to work for any ordered container.

Details:
Time: O(nr)-- dynamic programming, where n and r are the lengths of the strings.
Space: O(nr), but can be optimized to O(min(r,n))

Checklist

  • Check for existing issue
  • Check for existing pull request

Add hash table

Issue title

Add hash table

Issue description

A hash table should be added. The hashing algorithm and collision resolution method is unspecified.

Required Functionality:

  • Insert
  • Search
  • Delete
  • Table resizes automatically

Checklist

  • Check for existing issue
  • Check for existing pull request

Add selection sort

Issue description

Selection sort should be added. It should follow the same style as already implemented sorting algorithms.

Checklist

  • Check for existing issue
  • Check for existing pull request

Add quickselect

Issue title

Add quickselect

Issue description

The quickselect algorithm is used to find the k-th smallest element in an unordered sequence.

Details:
Side effects: The sequence becomes partially sorted.
Average-case Time: O(n)
Worst-case Time: O(n^2) --very unlikely
Space: O(n)?, where n is the recursion depth

Checklist

  • Check for existing issue
  • Check for existing pull request

Add merge sort

Issue title

Add merge sort

Issue description

Merge sort should be added. It can also be parallelized.

Checklist

  • Check for existing issue
  • Check for existing pull request

Library should be namespaced

Issue title

Library should be namespaced

Issue description

Currently, the library is in the global namespace. All algorithms and data structures should be placed within the cgn namespace.

Checklist

  • Check for existing issue
  • Check for existing pull request

Add binary search

Issue title

Add binary search

Issue description

Binary search should be added. It should assume the container is sorted and take a begin and end iterator.

Checklist

  • Check for existing issue
  • Check for existing pull request

BST does not have algorithm descriptions

Issue description

Per the contributing guidelines, every algorithm should have a description. This includes algorithms within a data structure.

Checklist

  • Check for existing issue
  • Check for existing pull request

Pull request template should require updating README if necessary

Issue title

Pull request template should require updating README if necessary

Issue description

The pull request template should require that users update the README feature table if necessary. This includes if a new feature is added or if unit tests are added.

Checklist

  • Check for existing issue
  • Check for existing pull request

Configure Clang on Travis-CI to use C++14

Issue description

Clang support on Linux has been temporarily removed due to issues getting the standard library for c++14 working on Travis. The goal is to re-add clang 4.0 and 5.0 support on Linux.

Checklist

  • Check for existing issue
  • Check for existing pull request

Add heap sort

Issue title

Add heap sort

Issue description

Heap sort should be added.

Checklist

  • Check for existing issue
  • Check for existing pull request

Fisher-Yates random test is unnecessarily long

Issue title

Fisher-Yates random test is unnecessarily long

Issue description

The Fisher-Yates shuffle has a test case that shuffles sequences repeatedly and makes sure the shuffle does not duplicate or remove elements. This test case takes a noticeable amount of time, and the same reliability can be guaranteed with fewer tests.

Proposal: Reduce the number of sequences to 50.

Checklist

  • Check for existing issue
  • Check for existing pull request

Bubble sort

Issue title

Bubble sort

Issue description

Bubble sort should be added.

Checklist

  • Check for existing issue
  • Check for existing pull request

Add Timsort

Issue title

Add Timsort

Issue description

Timsort is an adaptive sorting algorithm that takes advantage of existing runs in a sequence to sort the data.

Details:
Best-case Time: O(n)
Average-case Time: O(n log n)
Worst-case Time: O(n log n)
Space: O(n)

Checklist

  • Check for existing issue
  • Check for existing pull request

Add Fisher-Yates shuffle

Issue title

Add Fisher-Yates shuffle

Issue description

The Fisher-Yates shuffle is an algorithm to generate a random permutation of a sequence (or shuffle it).

Details:
Should be implemented to work for any sequence in-place.
Time: O(n)
Space: O(1)

Checklist

  • Check for existing issue
  • Check for existing pull request

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.