Skip to content

Latest commit

 

History

History
285 lines (183 loc) · 39.5 KB

README.md

File metadata and controls

285 lines (183 loc) · 39.5 KB

Note:

Please don't take effort to create pull requests for new algorithms or data structures. This is just a curiosity-driven personal hobby and was 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

Advanced Algorithms

Various important computer science algorithms generically implemented in C#.

.NET Core

Install by nuget

For beta releases on beta branch

Install-Package Advanced.Algorithms -Pre

For stable releases on stable branch

Install-Package Advanced.Algorithms

Supports

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

Development environment

Windows

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

Mac OS

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

Linux

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

Data structures

List

HashSets

Dictionaries

Stack

Queue

Linked list

Heap

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

Binary search trees

B trees (database trees)

Queryable trees

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

Lookup trees

TODO: implement trie compression.

Set

Graph

Adjacency list

Adjacency matrix

Algorithms

Graph algorithms

Articulation points

Bridges

Connectivity

Coloring

Cover

Maximum 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

Cycle

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

Distributed Systems

Numerical methods

Geometry (in 2D)

Bit manipulation