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.
-
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)
-
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
-
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.
- Reverse List
T~O(N), S~(1)
Reverse the linked list.
-
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.
-
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.
-
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.