Repository files navigation

Please don't take effort to create pull requests for new algorithms or data structures. This is just a curiosity-driven personal hobby andwas originally not intended to be a library. Feel free fork and modify to fit your need if that's what you are looking for. You can however open issues or fix bugs with pull requests, I would be happy to take a look when I get time

Various important computer science algorithms generically implemented in C#.

Install bynuget

For beta releases onbeta branch

Install-Package Advanced.Algorithms -Pre

For stable releases onstable branch

Install-Package Advanced.Algorithms

• API documentation

Supports

• .Net Standard 1.0 or above
• .Net Framework 4.0 or above

• Visual Studio Code as IDE for .NET core
• Visual Studio 2017 as IDE for .NET framework/.NET core

• Visual Studio Code as IDE for .NET core
• Visual Studio 2017 as IDE for Mono

• Visual Studio Code as IDE for .NET core
• Mono develop as IDE for Mono

• Array list (dynamic array) (implementation |tests)
• Skip list (implementation |tests)

• HashSet (usingseparate chaining optionally withopen address linear probing) (implementation |tests)
• Ordered HashSet (implementation |tests)

• Dictionary (usingseparate chaining optionally withopen address linear probing) (implementation |tests)
• Ordered Dictionary (implementation |tests)

• Stack (usingdynamic array and optionally usingsingly linked list) (implementation |tests)

• Queue (usingdynamic array and optionally usingdoubly linked list) (implementation |tests)
• Priority queue (implementation |tests)

• Singly linked list (implementation |tests)
• Doubly linked list (implementation |tests)
• Circular linked list (implementation |tests)

• Binary heap (implementation |tests)
• d-ary heap (implementation |tests)
• Binomial heap (implementation |tests)
• Fibonacci heap (implementation |tests)
• Pairing heap (implementation |tests)

Note: It is observed that among the implementations here, in practice, with the exclusion of UpdateKey (decrement/increment) operation, regular Binary Heap & d-ary Heap outperforms other in theory superiors. Likely because it doesn't have pointer juggling overhead and hey arrays are faster!

• Tree (implementation |tests)
• Binary tree (implementation |tests)

• Binary search tree (implementation |tests)
• AVL tree (implementation |tests)
• Red black tree (implementation |tests)
• Splay tree (implementation |tests)
• Treap tree (implementation |tests)

• B-tree (implementation |tests)
• B+ tree (implementation |tests)

• Segment tree (implementation |tests)
• Binary indexed tree (Fenwick tree) (implementation |tests)
• Multi-dimensional interval tree (implementation |tests) using nested red-black tree
• Multi-dimensional k-d tree (implementation |tests) for range and nearest neigbour queries
• Multi-dimensional range tree (implementation |tests) using nested red-black tree
• R-tree (implementation |tests)
• Quadtree (implementation |tests)

TODO: Support multi-dimentional segment tree & binary indexed tree.

• Prefix tree (Trie) (implementation |tests)
• Suffix tree (implementation |tests)
• Ternary search tree (implementation |tests)

TODO: implement trie compression.

• Disjoint set (implementation |tests)
• Sparse set (implementation |tests)
• Bloom filter (implementation |tests)

• Graph (implementation |tests)
• Weighted Graph (implementation |tests)
• DiGraph (implementation |tests)
• Weighted DiGraph (implementation |tests)

• Graph (implementation |tests)
• Weighted Graph (implementation |tests)
• DiGraph (implementation |tests)
• Weighted DiGraph (implementation |tests)

• Tarjan's articulation points finder (implementation |tests)

• Tarjan's bridge finder (implementation |tests)

• Kosaraju's strongly connected component finder (implementation |tests)
• Tarjan's strongly connected component finder (implementation |tests)
• Tarjan's bi-connected graph tester (implementation |tests)

• M-coloring (implementation |tests)

• Min vertex cover (implementation |tests)

• Ford-Fulkerson algorithm (implementation |tests)
• Edmonds Karp's improvement (implementation |tests) on Ford-Fulkerson algorithm
• Push relabel algorithm (implementation |tests)

• Bellman-Ford algorithm (implementation |tests)
• Dijikstra's algorithm (implementation |tests) using Fibonacci heap.
• Floyd-Warshall algorithm (implementation |tests)
• Johnson's algorithm (implementation |tests)
• Travelling salesman path (implementation |tests)
• A* search algorithm (implementation |tests) using Fibonacci heap.

• Max bipartite matching (implementation |tests) using Edmonds Karp's improved Ford Fulkerson max flow algorithm
• Max bipartite matching (implementation |tests) using Hopcroft Karp algorithm

• Minimum cut (implementation |tests) using Edmonds Karp's improved Ford Fulkerson max flow algorithm

• Cycle detection (implementation |tests)

• Depth first (implementation |tests)
• Breadth first (implementation |tests)
• Bi-directional (implementation |tests)

• Depth first method (implementation |tests)
• Kahn's algorithm (implementation |tests)

• Kruskal's algorithm (implementation |tests) using merge sort and disjoint set
• Prim's algorithm (implementation |tests)

• Manacher's algorithm for linear time longest palindrome (implementation |tests)

• Rabin-Karp string search (implementation |tests)
• Knuth–Morris–Pratt (KMP) string search (implementation |tests)
• Z algorithm for string search (implementation |tests)

• Huffman coding (implementation |tests)

• Binary search (implementation |tests)
• Quick select for kth smallest/largest in unordered collection using median of medians (implementation |tests)
• Majority element using Boyer-Moore voting algorithm (implementation |tests)

• Bubble sort (implementation |tests)
• Insertion sort (implementation |tests)
• Selection sort (implementation |tests)
• Shell sort (implementation |tests)
• Tree sort (implementation |tests)
• Quick sort (implementation |tests)
• Heap sort (implementation |tests)
• Merge sort (implementation |tests)
• Bucket sort (implementation |tests)
• Radix sort (implementation |tests)
• Counting sort (implementation |tests)

Note: On a decent desktop, in given implementations here for +ive random input integers, the clear winner is counting sort (~0.1 seconds to sort 1 million integers) followed by Radix Sort (~0.4 seconds). Merge Sort, Heap Sort, Quick Sort & Bucket Sort are all winners for +ive & -ive random integer inputs. Tree sort has pointer juggling overhead on backing Red-Black Tree, so performs 8 times slower than Merge Sort in practice. Bubble Sort, Insertion Sort, Selection Sort & Shell Sort are among the worst for random input as observed from results.

• Permutations (implementation |tests)
• Combinations (implementation |tests)
• Subsets (implementation |tests)

• Circular queue (ring buffer) (implementation |tests)
• Consistant hash (implementation |tests)
• LRU cache (implementation |tests)
• Asynchronous producer–consumer queue (implementation |tests)

• Check primality (implementation |tests)
• Generate primes using sieve of Eratosthenes (implementation |tests)
• Fast exponentiation (implementation |tests)

• Convex hull using gift wrapping algorithm (implementation |tests)
• Line intersection (implementation |tests)
• Closest point pair (implementation |tests)
• Check if given point inside polygon (implementation |tests)
• Rectangle intersection (implementation |tests)
• Point rotation (implementation |tests)
• Line interesections with Bentley-Ottmann sweep line algorithm using red-black tree and binary minimum heap (implementation |tests)

• Base conversion (implementation |tests)
• Calculate logarithm (base 2 & 10) (implementation |tests)
• GCD (implementation |tests)