Algorithms and Data Structures Archive

Contents

• 01 - Data Structures

  • 01.01 - Disjoint Sets

    Data Structure for operation and maintainance on disjoint sets over elements also often called Disjoint Set Union (DSU) or Union Find. O(α(n))

• 02 - Sorting

  • 02.01 - Merge Sort

    Efficient comparison-based sorting algorithm based on divide and conquer. O(n log n)

• 03 - Graphs

  • 03.01 - Depth First Search (DFS)

    Depth First Search (DFS) is a graph traversal algorithm starting at a node and exploring one branch as far as possible before backtracking. O(|V| + |E|)

  • 03.02 - Breadth First Search (BFS)

    Breadth First Search (BFS) is a graph traversal algorithm starting at a node and explores all nodes at the present depth before moving on to the nodes at the next depth level. O(|V| + |E|)

  • 03.03 - Topological Sort (TS)

    Graph traversal algorithm on a directed graph resulting in a topological order where any predecessor of a node is ordered before any of it's postdecessors. O(|V| + |E|)

  • 03.04 - Kruskal's Algorithm

    Constructs a MST of a connected graph by repeatedly adding the next shortest edge not already contained in the subgraph until we have a MST. O(|E| log |E|)

  • 03.05 - Prim's Algorithm

    Constructs a MST of a connected graph by repeatedly adding the shortest edge to the subgraph which connects a node already in the subgraph to a node outside of it until we have a MST. O(|E| + |V| log |V|)

  • 03.06 - Dijkstra's Algorithm

    Finds the Single Source Shortest Path (SSSP) from one node to all other nodes on any graph with non-negative edge weights. O(|E| + |V| log |V|)

  • 03.07 - Bellman-Ford Algorithm

    Finds the Single Source Shortest Path (SSSP) from one node to all other nodes on any graph. O(|V||E|)

  • 03.08 - Floyd-Warshall Algorithm

    Finds the All Pairs Shortest Path (APSP) for any pair of nodes on any graph. O(|V|^3)

• 04 - Trees

  • 04.01 - Trie

    Data Structure used to efficiently store and maintain a set of strings.

  • 04.02 - Segment Tree

    Data Structure used to efficiently store and maintain information about intervals, or segments.

  • 04.03 - Lowest Common Ancestor

• 05 - Maximum Flow

  • 05.01 - Ford-Fulkerson Method

    Finds the maximum flow by repeatedly augmenting an initial flow along augmenting paths until no more augmenting paths exist.

  • 05.02 - Push-Relabel Method

    Finds the maximum flow by successively adapting a preflow that saturates a cut until this preflow is a valid flow.

• 06 - Brute Force

  Technique of systematically iterating over all solution candidates until one satisfies the solution requirements.

• 07 - Greedy

  Technique of approximating the optimal solution to a problem by iteratively choosing locally optimal solutions for its subproblems.

• 08 - Dynamic Programming

  Technique of solving a problem by recursively dividing it into subproblems. After solving a subproblem it's solution is cached for later reuse in case the same subproblem comes up again.

• 09 - Number Theory

• 10 - Euclidean Geometry

• 11 - Projective Geometry

  Greatly simplifies the basic operations in comparison to euclidean geometry and allows for projective transformations.

• 12 - Miscellaneous

  • 12.01 - Binary Search

    Algorithm used for finding a specific value/element in an ordered interval range. O(log n)

Additional References

• cp-algorithms.com
• CLRS