Concepts116
Category
Edit Distance
Edit distance (Levenshtein distance) measures the minimum number of inserts, deletes, and replaces needed to turn one string into another.
Longest Increasing Subsequence
The Longest Increasing Subsequence (LIS) is the longest sequence you can extract from an array while keeping the original order and making each next element strictly larger.
2-SAT
2-SAT solves Boolean formulas where every clause has exactly two literals, and it is solvable in linear time relative to the size of the implication graph.
Euler Path and Circuit
An Euler path visits every edge exactly once, and an Euler circuit is an Euler path that starts and ends at the same vertex.
Knapsack Problems
Knapsack problems ask how to pick items under a weight (or cost) limit to maximize value or to check if a target sum is reachable.
Coin Change and Variants
Coin Change uses dynamic programming to find either the minimum number of coins to reach a target or the number of ways to reach it.
Dynamic Programming Fundamentals
Dynamic programming (DP) solves complex problems by breaking them into overlapping subproblems and using their optimal substructure.
DP State Design
Dynamic Programming (DP) state design is the art of choosing what information to remember so that optimal substructure can be reused efficiently.
Bipartite Matching - Hopcroft-Karp
Hopcroft–Karp computes maximum matching in a bipartite graph in O(E \sqrt{V}) time, which is asymptotically faster than repeated DFS (Kuhn's algorithm).
Block-Cut Tree
A Block-Cut Tree decomposes an undirected graph into biconnected components (blocks) and articulation points, forming a bipartite tree.
Hungarian Algorithm
The Hungarian algorithm solves the square assignment problem (matching n workers to n jobs) in O(n^{3}) time using a clever potential (label) function on vertices.
General Matching - Blossom Algorithm
Edmonds' Blossom Algorithm finds a maximum matching in any undirected graph, not just bipartite ones.