C# ALGORITHMS

Implementations of Data Structures and Algorithms in C#.

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 Xmarian (MonoDevelop) and Visual Studio. It has two separate projects: 1) Algorithms, 2) DataStructures. Both of them are class-library projects.

Data Structures

Lists:

• 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>.

Priority Queues:

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

Heaps:

• Binary Min-Heap. Uses the ArrayList<T> class.
• Binary Max-Heap. Uses the ArrayList<T> class.
• Binomial Min-Heap. Work in progress.

Trees:

• 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.

Hashing Functions:

• 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.

Hash Tables / Dictionaries:

• 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.

Algorithms

Sorting:

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();
  

Visualization:

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

  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
   **                 /\   /\ /\
   */
  

License

This project is licensed under the MIT License.