Category: algorithms
-
Union-Find
Say we have an equivalence relation on a set . So, partitions into equivalence classes which are disjoint subsets of . Now, given a pair where , we want to answer: Do and belong to the same equivalence class? As an example, we need to answer this question to build the minimum spanning tree of…
-
Graph Traversal
Say a graph’s vertex set is and edge set is . We want to traverse the graph efficiently, therefore, we want to visit each vertex and each edge exactly once. An edge has two ends: a from and a to. In the edge we can consider as from and as to. The basic traversal strategy…
-
Dynamic Programming
Approach As long as the below two conditions hold, we can use Dynamic Programming to solve a problem: Sub-problem: We can formulate the solution to the original problem as a function of the solutions to “smaller” versions or sub-problems. The “smallest” sub-problems are trivially solved. Node: One node represents one sub-problem. Edge: There is an…
