CS3383 Assignment 4

‎

1. Introduction

For general information about assignments in this course, see assignments

2. Union by weight

Consider the following alternative implimentation of the disjoint-sets data structure.

class Partition:
    def __init__(P,n):
      # sometimes called makeset(j)
      P.parent = [j for j in range(n)]
      P.weight = [1] * n

    def find(P, key):
      if P.parent[key] != key:
          key = P.find(P.parent[key])
      return key

    def union(P,x,y):
      rx = P.find(x)
      ry = P.find(y)

      if rx == ry:
          return

      if P.weight[rx] > P.weight[ry]:
          P.parent[ry] = rx
          P.weight[rx] += P.weight[ry]
      else:
          P.parent[rx] = ry
          P.weight[ry] += P.weight[rx]

Prove that after any sequence of union operations, P.find(x) takes \(O(\lg n)\) time.

3. Path Compression

Here is recursive version of find with path compression from the slides.

def find(P, key):
  if P.parent[key] != key:
    P.parent[key] = P.find(P.parent[key])
  return P.parent[key]

Give a non-recursive version, still with path compression, and show that it preserves Property 1 for union-find, namely

For any \(x∈[0..n-1]\) such that P.parent[x] != x, P.rank[x] < P.rank[P.parent[x]]