2024-03-19

Tuesday, March 19th, 2024

Trying to sneak a fastball past Hank Aaron is like trying to sneak the sunrise past a rooster.

— Joe Adcock

ECS122A Notes

• Prim’s algorithm: greedy algorithm for finding minimum spanning tree
  • input: set of vertices $V$ and edges $E$ of an undirected graph
    • negative edge weights allowed
  • output: a minimum spanning tree
  • procedure
    • Start with an empty spanning tree with an arbitrary root.
    • Initialize $Q$, a min priority queue of vertices, where each vertex $v$ are keyed by $d_v$, the weight of shortest edge that joins it to the MST (initially $\infty$). The root node should have a weight of zero.
    • While $Q$ is not empty (i.e., while there are vertices not in the MST)
      • Pop a node $u$ from the queue.
      • If $u$ is not in MST (i.e., $u$ is still in $Q$), add its lowest-weight edge to the spanning tree.
      • Update the distances of $v$‘s neighbors as needed.
    • Return the MST.
• Kruskal’s algorithm: greedy algorithm for finding minimum spanning tree
  • input: set of vertices $V$ and edges $E$ of an undirected graph
    • negative edge weights allowed
  • output: a minimum spanning tree
  • procedure
    • Sort all edges $E$ by weight in descending order.
    • Initialize a Union-Find data structure with all vertices added.
    • For each edge $(u,v)$ in decreasing order of weight
      • If adding this edge doesn’t form a cycle in the MST (Find(u) != Find(v)), add it to the MST and Union(u, v).
      • If there’s $V-1$ edges in the MST
        • Return MST (enables early exit when there are lots of edges)
• Union-Find
  • Union-Find data structure keeps elements in disjoint sets represented as trees. We use the root (i.e., the root node of the tree) to identify the set that an element belongs to. Initially, each element added to the data structure belongs to its own set.
  • operations
    • Union(x, y): Merge the roots of x and y.
    • Find(x): Get the root that x belongs to.
  • Union-Find by rank: an efficient implementation
    • The rank of a set denotes how many subtrees was unioned into this set.
    • When unioning two sets, make the higher ranked set the parent of the lower ranked set.
    • With rank, Find(x) has an amortized cost of $O(\log n)$.
  • path suppression
    • When doing Find(x), it is inefficient to always have to traverse the tree to find the value of root node. So, once the find query acquires the root node value, it updates the parents of previous nodes to point straight at the root, so that the next Find(x) is practically O(1).
  • With both path suppression and rank, Find(x) has an amortized complexity of $O(\alpha (n))$, where $\alpha$ is the inverse of Ackermann function.
• find graph cycles with Union-Find
  • input: set of vertices $V$ and edges $E$ of an undirected graph
  • output: true if there’s a cycle in the graph, false otherwise
  • procedure
    • initialize a Union-Find data structure with all vertices in their own disjoint sets
    • For each edge $(u,v)$:
      • If Find(u) equals Find(v)
        • u and v belong to the same root, and the graph contains a cycle. Return true.
      • Union(u, v)
    • No cycles found. Return false.
• problem (“language”) classes
  • P: Set of decision problems (“yes” or “no” problems) that can be solved in polynomial time
  • NP: Set of decision problems whose solutions can be verified in polynomial time
    • NP-complete: Subset of decision problems in NP, where every other NP problem can be transformed into an NP-completed in polynomial time. For example, every NP problem can be transformed into 3-SAT (an NP-complete problem). If a deterministic polynomial time algorithm is found to be able to solve one NP-complete problem, it means all NP-complete problems can be solved in polynomial time.
  • NP-hard: A set decision problems (not necessarily a subset of NP) that are at least as hard as NP-complete. A problem is NP-hard if there exists an NP-complete problem that can be transformed into it in polynomial time; naturally, any NP-complete problem is also NP-hard.