davcs86/Advanced-Algorithms

100+ algorithm & data structure implementations in C#

Advanced Algorithms

Various important computer science algorithms generically implemented in C#

Data Structures

List

• Array List (dynamic array) (Implementation | Tests)
• Skip List (Implementation | Tests)

Hash Set

• HashSet (using Separate Chaining optionally Open Address Linear Probing) (Implementation | Tests)
• Tree HashSet (Implementation | Tests)

Hash Dictionaries

• Dictionary (using Separate Chaining optionally Open Address Linear Probing) (Implementation | Tests)
• Tree Dictionary (Implementation | Tests)

Stack

• Stack (Implementation | Tests)

Queue

• Queue (Implementation | Tests)

Priority Queue

• Min Priority Queue (Implementation | Tests)

Linked List

• Singly linked list (Implementation | Tests)
• Doubly linked list (Implementation | Tests)
• Circular linked list (Implementation | Tests)

Heap

Min

• Binary Min Heap (Implementation | Tests)
• d-ary Min Heap (Implementation | Tests)
• Binomial Min Heap (Implementation | Tests)
• Fibornacci Min Heap (Implementation | Tests)
• Pairing Min Heap (Implementation | Tests)

Note: Among the implementations here in practice, with the exclusion of DecrementKey operation regular Binary Heap & d-ary Heap outperforms other in theory superiors. Of course because it don't have pointer juggling nonsense and hey arrays are faster!

Max

• Binary Max Heap (Implementation | Tests)

Tree

• Tree (Implementation | Tests)
• Binary Tree (Implementation | Tests)

Binary Search Trees

• Binary Search Tree (Implementation | Tests)
• AVL Tree (Implementation | Tests)
• Red Black Tree (Implementation | Tests)
• Splay Tree (Implementation | Tests)
• Treap Tree (Implementation | Tests)

B Trees

• B Tree (Implementation | Tests)
• B+ Tree (Implementation | Tests)

Queryable Trees

• Multi-dimensional Interval Tree (Implementation | Tests) using multi-level Red-black tree
• Multi-dimensional Kd Tree (Implementation | Tests) for range and nearest neigbour queries
• Multi-dimensional Range Tree (Implementation | Tests)
• Segment Tree (Implementation | Tests)
• Binary Indexed Tree (Fenwick tree) (Implementation | Tests)

LookUp Trees

• Prefix Tree (Trie) (Implementation | Tests)
• Suffix Tree (Implementation | Tests)
• Ternary Search Tree (Implementation | Tests)

Parse Trees

• Expression Tree (Implementation | Tests)

Set

• Disjoint Set (Implementation | Tests)
• Sparse Set (Implementation | Tests)

Graph

Adjacency List

• DiGraph (Implementation | Tests)
• Graph (Implementation | Tests)
• Weighted DiGraph (Implementation | Tests)
• Weighted Graph (Implementation | Tests)

Algorithms

Graph Algorithms

Articulation Points

• Tarjan's Articulation Points Finder (Implementation | Tests)

Bridges

• Tarjan's Bridge Finder (Implementation | Tests)

Connectivity

• Kosaraju's Strongly Connected Component Finder (Implementation | Tests)
• Tarjan's Strongly Connected Component Finder (Implementation | Tests)
• Tarjan's BiConnected Graph Tester (Implementation | Tests)

Coloring

• M-Coloring (Implementation | Tests)

Cover

• Min Vertex Cover (Implementation | Tests)

Max Flow

• Ford-Fulkerson algorithm (Implementation | Tests)
• Edmonds Karp's improvement (Implementation | Tests) on Ford-Fulkerson algorithm
• Push Relabel algorithm (Implementation | Tests)

Shortest Path

• Bellman-Ford algorithm (Implementation | Tests)
• Dijikstra's algorithm (Implementation | Tests) using Fibornacci Heap.
• Floyd-Warshall algorithm (Implementation | Tests)
• Johnson's algorithm (Implementation | Tests)

Matching

• Max Bipartite Matching (Implementation | Tests) using Edmonds Karp's improved Ford Fulkerson Max Flow algorithm
• Hopcroft Karp algorithm (Implementation | Tests)

Cut

• Minimum Cut (Implementation | Tests) using Edmonds Karp's improved Ford Fulkerson Max Flow algorithm

Search

• Depth First (Implementation | Tests)
• Breadth First (Implementation | Tests)
• Bi-Directional (Implementation | Tests)

Topological Sort

• Depth First Method (Implementation | Tests)
• Kahn's algorithm (Implementation | Tests)

Minimum Spanning Tree

• Kruskal's algorithm (Implementation | Tests) using Merge Sort and Disjoint Set
• Prim's algorithm (Implementation | Tests) using Fibornacci Heap

String

• Permutation (Implementation | Tests)
• Manacher's algorithm for linear time longest Palindrome (Implementation | Tests)

Pattern Matching

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

Compression

• Huffman Coding (Implementation | Tests) using Fibornacci Min Heap

Sorting and Searching

• Median of stream of numbers (Implementation | Tests)
• Array in zig-zag fashion (Implementation | Tests)
• Binary Search (Implementation | Tests)
• Search on almost sorted array (Implementation | Tests)
• Sort an almost sorted array (Implementation | Tests)

Sorting Algorithms

• 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.6 seconds to sort 1 million integers) followed by Radix Sort. Merge Sort, Heap Sort, Quick Sort & Bucket Sort are all winners for +ive & -ive random integer inputs with (~1 seconds to sort 1 million integers). 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 you might have guessed.

Numerical Methods

• kth Smallest (Implementation | Tests)
• Check Primality (Implementation | Tests)
• Generate Primes using Sieve of Eratosthenes (Implementation | Tests)
• Fast Exponentiation (Implementation | Tests)

Classic Dynamic Programming Problems

All are top down solutions with memoization technique.

Matrix

• Max submatrix (Implementation | Tests)
• Min cost matrix path (Implementation | Tests)
• Chain matrix multiplication (Implementation | Tests)
• Max 1s Rectangle in matrix (Implementation | Tests)
• Max 1s Square in matrix (Implementation | Tests)
• Max subsquare with X sides in matrix (Implementation | Tests)

Counting

• Count bool parenthesization (Implementation | Tests)
• Count decoding (Implementation | Tests)
• Dice throw (Implementation | Tests)
• Count possible binary tree from a preorder sequence (Implementation | Tests)
• Ways to cover a distance (Implementation | Tests)
• Staircase problem in Fibornacci Series (Implementation | Tests)

Maximizing

• Knapsack problem (Implementation | Tests)
• Max sum subsequence (Implementation | Tests)
• Max increasing sum sequence (Implementation | Tests)
• Max profit buy/sell stocks in K transactions (Implementation | Tests)
• Box Stacking (Implementation | Tests)
• Building Bridges (Implementation | Tests)
• Burst Balloon (Implementation | Tests)
• Cutting Rod (Implementation | Tests)
• Print Max A's (Implementation | Tests)
• Weighted Job Scheduling (Implementation | Tests)

Minimizing

• Coin change problem (Implementation | Tests)
• Assembly line scheduling (Implementation | Tests)
• Min Egg drop problem (Implementation | Tests)
• Min edit distance (Implementation | Tests)
• Min array jumps (Implementation | Tests)
• Travelling Salesman Problem (Implementation | Tests)

Palindrome

• Longest palindrome (Implementation | Tests)
• Shortest palindrome (Implementation | Tests)
• Palindrome min cut (Min Partitioning) (Implementation | Tests)
• Min deletion to get a palindrome (Implementation | Tests)

Sequence

• Balanced partition (Implementation | Tests)
• Distinct binary strings (Implementation | Tests)
• Longest common subsequence (Implementation | Tests)
• Longest increasing subsequence (Implementation | Tests)
• Longest bitonic sequence (Implementation | Tests)

Sum

• Subset sum (Implementation | Tests)

String

• Wild card matching (Implementation | Tests)
• Regular Expression (Implementation | Tests)
• String interleaving (Implementation | Tests)
• Word Break problem (Implementation | Tests)
• Text Justification (Implementation | Tests)

Other

• Tower of hanoi (Implementation | Tests)
• Fibonacci number generator (Implementation | Tests)
• Optimal game strategy (Implementation | Tests)
• Unique Binary Search Tree (Implementation | Tests)
• Optimal Binary Search Tree (Implementation | Tests)

Bit Algorithms

• Base conversion (Implementation | Tests)
• Find the element that appears once (Implementation | Tests)
• Set bits in all numbers from 1 to n (Implementation | Tests)
• Swap bits (Implementation | Tests)
• Add two numbers (Implementation | Tests)
• Smallest of three (Implementation | Tests)
• A Boolean Array Puzzle (Implementation | Tests)
• Set bits in an (big) array (Implementation | Tests)
• Next higher number with same number of set bits (Implementation | Tests)
• Add 1 to a number (Implementation | Tests)
• Absolute value (abs) without branching (Implementation | Tests)
• Minimum or Maximum of two integers (Implementation | Tests)
• Find the two non-repeating elements in an array (Implementation | Tests)
• Find two repeating elements in an array (Implementation | Tests)
• Reverse Bits of a Number (Implementation | Tests)
• Next Power of 2 (Implementation | Tests)
• Check if a Number is Multiple of 3 (Implementation | Tests)
• Find parity (Implementation | Tests)
• Swap all odd and even bits (Implementation | Tests)
• Karatsuba algorithm for fast multiplication (Implementation | Tests)
• Swap without temp (Implementation | Tests)
• Check if a number is multiple of 9 (Implementation | Tests)
• Maximum Subarray XOR (Implementation | Tests)
• Magic Number (Implementation | Tests)
• Sum of bit differences among all pairs (Implementation | Tests)
• Count number of bits to be flipped to convert A to B (Implementation | Tests)
• Find Next Sparse Number (Implementation | Tests)

Geometry

• Convex hull (Implementation | Tests)
• Line intersection (Implementation | Tests)
• Closest point pair (Implementation | Tests)
• Check if given point inside polygon (Implementation | Tests)
• Rectangle intersection (Implementation | Tests)

Divide & Conquer

• Count Inversions (Implementation | Tests)
• Strassen’s Matrix Multiplication (Implementation | Tests)