Algorithms and Data Structures

About the project

Running an algorithm

Data Structures

• Binary Search Tree
• Balanced Trees
  • AVL Tree
  • Red-Black Tree
• Splay Tree
• Hash Table
  • Hashtable (Linear Probing)
  • Hashtable (Quadratic Probing)
  • Hashtable (Double Hashing)
  • Hashtable (Separate Chaining)
• Linked List
• Stack
• Priority Queue

Mathematics

Graph Theory

• Dijkstra's Shortest Path (priority queue) - O(|V| + |E| log|V|)
• Kruskal's min spanning tree algorithm (edge list, union find) - O(Elog(E))
• Prim's min spanning tree algorithm (lazy version, adjacency list) - O(Elog(E))
• Traveling Salesman Problem (brute force) - O(n!)

Linear Algebra

• Transpose Of A Matrix
• Matrix determinant (Laplace/cofactor expansion) - O((n+2)!)
• Matrix inverse - O(n3)
• Matrix multiplication - O(n3)

Search Algorithms

• Linear Search - O(n)
• Sorted search - Θ(n*log2 n)
• Binary Search (recursive) - O(log n)

Sorting Algorithms

• Insertion Sort - O(n²)
• Binary Insertion Sort - O(n²)
• Shell Sort - Θ(n*log n)
• Heapsort - O(n*log n)
• Selection Sort - O(n²)
• Merge Sort Top-Down - Θ(n*log n)
• Merge Sort Bottom-Up - Θ(n*log n)
• Quicksort using Lomuto's partition - Θ(n*log n)
• Quicksort using Hoare's partition - Θ(n*log n)
• Counting Sort - O(n+k)
• Radix Sort (LSD) - O(n*w)
• Radix Sort (MSD String Sort) - O(n*w)
• Bucket Sort - O(n)

Divide-and-Conquer

• Merge Sort Top-Down - Θ(n*log n)
• Merge Sort Bottom-Up - Θ(n*log n)

Greedy Algorithms

Dynamic Programming

• Grid Traveler - O(m*n)
• Coin change problem - O(nW)
• Maximum contiguous subarray - O(n)
• Longest Common Subsequence (LCS) - O(nm)
• Traveling Salesman Problem (dynamic programming, iterative) - O(n^22^n)
• Traveling Salesman Problem (dynamic programming, recursive) - O(n^22^n)
• Longest Common Substring (LCS) - O(nlog(n)) bounded by SA construction, otherwise O(n)