Skip to content

100+ algorithm & data structure implementations in C#

License

Notifications You must be signed in to change notification settings

tajwal/Advanced-Algorithms

 
 

Repository files navigation

Advanced Algorithms

Various important computer science algorithms generically implemented in C#

Build Status

Install by nuget

For beta releases on beta branch

Install-Package Advanced.Algorithms -Pre

Not a stable release yet.

Supports

  • .Net Standard 2.0 or above
  • .Net Framework 4.5 or above

Data Structures

List

Hash Set

Hash Dictionaries

Stack

Queue

Priority Queue

Linked List

Heap

Min

Max

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

Tree

Binary Search Trees

B Trees

Queryable Trees

LookUp Trees

Parse Trees

Set

Graph

Adjacency List

Adjacency Matrix

Algorithms

Graph Algorithms

Articulation Points

Bridges

Connectivity

Coloring

Cover

Max Flow

Shortest Path

Matching

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

Cut

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

Search

Topological Sort

Minimum Spanning Tree

String

Pattern Matching

Compression

Sorting and Searching

Sorting Algorithms

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.

Combinatorics

Numerical Methods

Classic Dynamic Programming Problems

All are top down solutions with memoization technique.

Matrix

Counting

Maximizing

Minimizing

Palindrome

Sequence

Sum

String

Geometry (in 2D)

Bit Manipulation

Miscellaneous

About

100+ algorithm & data structure implementations in C#

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages

  • C# 99.7%
  • Other 0.3%