lgulich/algo_baselines

Baseline implementations for common algorithms in C++

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 Structures

• Binary Search Tree
  Data structure to allow fast finding and range-queries (here for number of nodes in range).
  Creation: T~O(N*log(N)), S~O(N)
  Finding: T~O(log(N)), S~O(1) Range Count: T~O(log(N)), S~O(1)

• Quick Union
  Data structure that allows to connect nodes and efficiently query if two nodes are connected. Creation: T~O(N), S~O(N)
  Connect: T~O(log(N)), S~O(1) Query: T~O(log(N)), S~O(1)

• 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

Dynamic Programming

• Knapsack
  Find the items to fill a bag s.t. the value of the bag is maximized while constraining the maximum capacity C.
  T~O(N*C), S~O(N*C)

• Mountain Scenes
  Calculate the number of possible ways to draw a mountain scene.
  T~O(W*S), S~O(W*S), with image width W and max rope length S.

• Narrow Art Gallery
  Calculate the maximum sum of gallery rooms, while closing K rooms and keeping a way to walk through the gallery. T~O(N*K), S~O(N*K), with gallery length N

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.

Lists

• Reverse List
  T~O(N), S~(1)
  Reverse the linked list.

Search

• Binary Search
  T~O(log(N)), S~(1)
  Find position of an element in a sorted vector.

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

• Search Smaller Element
  T~O(log(N)), S~(1)
  Find element or next smaller element in a sorted vector.

• Quick Select
  T~O(N*log(N)), S~(1)
  Find k-smallest element in vector and partition around it.

• Range Contains
  T~O(log(N)), S~(1)
  Check is a list of ranges contains a value.

Sort

• Merge Sort
  T~O(N*log(N)), S~(N)
  Recursively split vector in half, sort both halves and then merge sorted halves.

• Quick Sort
  T~O(N*log(N)), S~(log(N))
  Recursively partition array into elements smaller and bigger than pivot.

• Selection Sort
  T~O(N^2), S~(1)
  Sort by putting minimum element to front, continue with remaining vector.

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.