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: Given such a DAG, the overall approach is as follows: Observations Explicit DAG Shortest paths Given a DAG with positive edge weights and a source node, we want to find shortest path distances to every other node…
unreasonably effective 