Algo Baselines

Baseline implementations for common algorithms in C++.

The code in this repo will probably not be generic enough that you can use it for your own problems, but feel free to use the implementations as a guide for your own implementations.

Data Strucutres

• Sparse Table
  Data structure to allow fast range-queries (here for minimum values).
  Creation: T~O(N*log(N)), S~O(N*log(N))
  Query: T~O(1), S~O(1)

Algorithms

Graphs

• Mutation - Invert Adjacency List
  Invert an adjacency list such that every edge points in the other direction.
  T~O(E), S~O(N+E)

• Traversal - Breadth First Search
  Allows to traverse graph in a certain order.
  T~O(N+E), S~O(N)

• Traversal - Depth First Search
  Allows to traverse graph in a certain order.
  T~O(N+E), S~O(N)

• Topological Sort - DFS Approach
  Find a order of the nodes such that all ancestors of a node come before the node itself.
  T~O(N+E), S~O(N)

• Topological Sort - Kahn's Algorithm
  Find a order of the nodes such that all ancestors of a node come before the node itself.
  T~O(N+E), S~O(N)

• Shortest Path - Bellfast Algorithm
  T~O(N*E), S~(N)
  Find the shortest path to all nodes in graph from a start node. Additionally also finds nodes in negative cycles (shortest path = -inf).

• Shortest Path - Dijkstra Algorithm
  T~O(E*log(N)), S~(N)
  Find the shortest path between two nodes.

Search

• Pattern Matching - Knuth-Morris-Pratt Algorithm
  T~O(N+M), S~(M)
  Find if a pattern is contained in a vector. (N is size of vector, M is size of pattern).

Trees

• Find Center
  T~O(N), S~(N)
  Finds the center of a graph with the tree property.

• Hash Tree
  T~O(N*log(N)), S~(N)
  Computes the hash of a tree such that isomorphic trees have the same hash.

• Root Tree
  T~O(N), S~(N)
  Creates a rooted tree from a graph with the tree property.

• Determine Isomorphism
  T~O(N*log(N)), S~(N)
  Determine if two unrooted trees are isomorphic (i.e. have same topology).

• Lowest Common Ancestor
  T~O(N), S~(N)
  Find the lowest common ancestor of two nodes.