I started writing this organized collection of classes as part of my preparation for technical interviews. This is for educational purposes only. However, the source code is stable.

This is a .NET solution and it can be opened with both Xamarin Studio (MonoDevelop) and Visual Studio. It has two separate projects: 1) Algorithms, 2) DataStructures. Both of them are class-library projects.

The third project is called MainProgram and it has all the tests for all the implemented algorithms and data structures. It has two main directories:

• Algorithms Tests.
• Data Structures Tests.

• Single-Linked List.
• Double-Linked List.
• Array List. A generic arrays-based list. Implements auto-resizing and handles overflow.
• Stack. Based on my ArrayList<T>.
• Queue. Based on my ArrayList<T>.

• Min-Priority Queue. Based on my MinHeap<T>.
• Keyed Priority Queue. Based on my MaxHeap<T>.

• Binary Min-Heap. Uses the ArrayList<T> class.
• Binary Max-Heap. Uses the ArrayList<T> class.
• Binomial Min-Heap. Uses the ArrayList<T> class as a collection of connected BinomialNode lists. The BinomialNode is a private class inside the Heap data structure class.

• Binary Search Tree. Standard BST.
• Augmented Binary Search Tree. A BST that is augmented to keep track of the subtrees-size for each node. Extends the BinarySearchTree<T> class.
• AVL Tree. The self-balancing AVL binary-search tree. Extends the BinarySearchTree<T> class.

• Prime Hashing Family. Implements a simple family of hash functions using primes. The functions are initialized by randomly selecting primes. Supports re-generation of functions.
• Universal Hashing Family. Implements a family class of simple universal-hashing functions. Supports re-generation of functions. It uses the Common/PrimesList helper class.

• Chained Hash Table. A hash table that implements the Separate-Chaining scheme for resolving keys-collisions. It also implements auto-resizing (expansion and contraction).
• Cuckoo Hash Table. A hash table that implements the Cuckoo Hashing algorithm for resolving keys-collisions. This is a single-table implementation, the source behind this is the work of Mark Allen Weiss, 2014.

• Undirected Graphs:

• Undirected Sparse Graph. An adjacency-list graph representation. Implemented using a Dictionary. The nodes are inserted as keys, and the neighbors of every node are implemented as a doubly-linked list of nodes. This class implements the IGraph<T> interface.

• Undirected Dense Graph. An incidence-matrix graph representation. Implemented using a two dimensional boolean array. This class implements the IGraph<T> interface.

• Directed Graphs / Digraphs:

• Directed Sparse Graph. An adjacency-list digraph representation. Follows almost the same implementation details of the Undirected version, except for managing the directed edges. Implements the IGraph<T> interface.

• Directed Dense Graph. An incidence-matrix digraph representation. Follows almost the same implementation details of the Undirected version, except for managing the directed edges. Implements the IGraph<T> interface.

• Directed Weighted Graphs / Weighted Digraphs:

• Directed Weighted Sparse Graph. An adjacency-list weighted digraph representation. Shares a good deal of implemention details with the Directed Sparse version (DirectedSparseGraph<T>). Edges are instances of WeightedEdge<T> class. Implements both interfaces: IGraph<T> and IWeightedGraph<T>.

• Directed Weighted Dense Graph. An adjacency-matrix weighted digraph representation. Inherits and extends Directed Dense verion (DirectedDenseGraph<T>). Implements the IWeightedGraph<T> interface.

Sorting algorithms are implemented as an extension method. They support the native Array<T>, and List<T> classes. They can takes value comparers. Insertion Sort supports my ArrayList<T> class.

• Insertion Sort.

• Quick Sort.

• Merge Sort.

• Heap Sort.

• BST Sort. Implements an unbalanced binary search tree sort.

• Counting Sort. Only sorts arrays of integers.

  int[] array = new int[] { 23, 42, 4, 16, 8, 15, 3, 9, 55, 0 };
  List<long> list = new List<long> () { 23, 42, 4, 16, 8, 15, 3, 9, 55, 0 };
  
  // The value comparer object. Can be any value comparer that implmenets IComparer.
  var valueComparer = Comparer<long>.Default;
  
  list.InsertionSort (valueComparer);
  list.QuickSort (valueComparer);
  list.MergeSort (valueComparer);
  list.HeapSort (valueComparer);
  list.UnbalancedBSTSort();
  array.CountingSort();
  

• Depth-First Searcher. Implements the Depth-First Search algorithm in two ways: Iterative and Recursive. Provides multiple functions for traversing graphs: PrintAll(), VisitAll(Action<T> forEachFunc), FindFirstMatch(Predicate<T> match). The VisitAll() applies a function to every graph node. The FindFirstMatch() function searches the graph for a predicate match.
• Breadth-First Searcher. Implements the the Breadth-First Search algorithm. Provides multiple functions for traversing graphs: PrintAll(), VisitAll(Action<T> forEachFunc), FindFirstMatch(Predicate<T> match). The VisitAll() applies a function to every graph node. The FindFirstMatch() function searches the graph for a predicate match.
• Breadth-First Shortest Paths. Calculates Shortest-Paths for Unweighted Graphs using the Breadth-First Search algorithm. It provides the capability to find shortest-paths from a single-source and multiple-sources, in addition to looking up reachable and unreachable nodes.
• Dijkstra's Shortest Paths. Calculates Dijkstra's Shortest-Paths for Directed Weighted Graphs from a single-source to all destinations. This class provides the same API as the BreadthFirstShortestPaths<T>.
• Dijksta's All-Pairs Shortest Paths. Calculates Dijktra's shortest paths for all pairs of vertices in a graph. This is a wrapper class that applies single-source dijkstra shortest paths (DijkstraShortestPaths<TG, TV>) to all vertices of a graph and saves the results in a dictionary index by the vertices.
• Cycles Detector. Detects if a given graph is cyclic. Supports directed and undirected graphs.
• Topological Sorter. Calculates one topological sorting of a DAG (Directed Acyclic Graph). This class depends on the CyclesDetector static class.

• Catalan Numbers. A class that calculates the catalan numbers. A dynamic-programming solution.

• Tree Drawer. Draws any tree that extends my BinarySearchTree<T> class. It is defined as an extension method.

  var avlTree = new AVLTree<int>();
  var treeDataList = new List<int>() { 15, 25, 5, 12, 1, 9, 7, -1, 11, 30, 8, 10, 13, 28, 39 };
  avlTree.Insert(treeDataList);
  
  Console.WriteLine( avlTree.DrawTree() );
  
  /***
   ** Drawer output:
   **           .......9......
   **          /              \
   **       .5       ....12...
   **      /  \     /         \
   **    1   7    11      .25.
   **    /\ / \   /\     /    \
   **  -1     8  10    15    30
   **  /\    /\  /\    /\   / \
   **                 13   28 39
   **                 /\   /\ /\
   */
  

This project is licensed under the MIT License.