Additional Contents

Disjoint Sets Data Structure (Chap. 21)

• A disjoint-set is a collection ©={S₁, S₂,…, S_k} of distinct dynamic sets.
• Each set is identified by a member of the set, called representative.
• Disjoint set operations:
• MAKE-SET(x): create a new set with only x. assume x is not already in some other set.
• UNION(x,y): combine the two sets containing x and y into one new set. A new representative is selected.
• FIND-SET(x): return the representative of the set containing x.

Multiple Operations

• Suppose multiple operations:
• n: #MAKE-SET operations (executed at beginning).
• m: #MAKE-SET, UNION, FIND-SET operations.
• m≥n, #UNION operation is at most n-1.

An Application of Disjoint-Set

• Determine the connected components of an undirected graph.

CONNECTED-COMPONENTS(G)

1. for each vertex v ∈V[G]
2. do MAKE-SET(v)
3. for each edge (u,v) ∈E[G]
4. do if FIND-SET(u) ≠ FIND-SET(v)
5. then UNION(u,v)

​

​

SAME-COMPONENT(u,v)

1. if FIND-SET(u)=FIND-SET(v)
2. then return TRUE
3. else return FALSE

Linked-List Implementation

• Each set as a linked-list, with head and tail, and each node contains value, next node pointer and back-to-representative pointer.
• Example:
• MAKE-SET costs O(1): just create a single element list.
• FIND-SET costs O(1): just return back-to-representative pointer.

Linked-lists for two sets

head

tail

g

head

tail

c

head

Set {c,h,e}

Set {f, g}

UNION of

two Sets

e

UNION Implementation

• A simple implementation: UNION(x,y) just appends x to the end of y, updates all back-to-representative pointers in x to the head of y.
• Each UNION takes time linear in the x’s length.
• Suppose n MAKE-SET(x_i) operations (O(1) each) followed by n-1 UNION
• UNION(x₁, x₂), O(1),
• UNION(x₂, x₃), O(2),
• …..
• UNION(x_n-1, x_n), O(n-1)
• The UNIONs cost 1+2+…+n-1=Θ(n²)
• So 2n-1 operations cost Θ(n²), average Θ(n) each.
• Not good!! How to solve it ???

Weighted-Union Heuristic

• Instead appending x to y, appending the shorter list to the longer list.
• Associated a length with each list, which indicates how many elements in the list.
• Result: a sequence of m MAKE-SET, UNION, FIND-SET operations, n of which are MAKE-SET operations, the running time is O(m+nlg n). Why???

• Hints: Count the number of updates to back-to-representative pointer

for any x in a set of n elements. Consider that each time, the UNION

will at least double the length of united set, it will take at most lg n

UNIONS to unite n elements. So each x’s back-to-representative pointer

can be updated at most lg n times.

​

Disjoint-set Implementation: Forests

• Rooted trees, each tree is a set, root is the representative. Each node points to its parent. Root points to itself.

d

d

h

e

c

c

Set {c,h,e}

Set {f,d}

UNION

Straightforward Solution

• Three operations
• MAKE-SET(x): create a tree containing x. O(1)
• FIND-SET(x): follow the chain of parent pointers until to the root. O(height of x’s tree)
• UNION(x,y): let the root of one tree point to the root of the other. O(1)
• It is possible that n-1 UNIONs results in a tree of height n-1. (just a linear chain of n nodes).
• So n FIND-SET operations will cost O(n²).

Union by Rank & Path Compression

• Union by Rank: Each node is associated with a rank, which is the upper bound on the height of the node (i.e., the height of subtree rooted at the node), then when UNION, let the root with smaller rank point to the root with larger rank.
• Path Compression: used in FIND-SET(x) operation, make each node in the path from x to the root directly point to the root. Thus reduce the tree height.

Path Compression

f

e

d

c

f

e

d

c

Algorithm for Disjoint-Set Forest

MAKE-SET(x)

1. p[x]←x
2. rank[x]←0

LINK(x,y)

1. if rank[x]>rank[y]
2. then p[y] ←x
3. else p[x] ←y
4. if rank[x]=rank[y]
5. then rank[y]++

​

FIND-SET(x)

1. if x≠ p[x]
2. then p[x] ←FIND-SET(p[x])
3. return p[x]

Worst case running time for m MAKE-SET, UNION, FIND-SET operations is:

O(mα(n)) where α(n)≤4. So nearly linear in m.

UNION(x,y)

1. LINK(FIND-SET(x),FIND-SET(y))

Analysis of Union by Rank with Path Compression�(by amortized analysis)

• Discuss the following:
• A very quickly growing function and its very slowly growing inverse
• Properties of Ranks
• Proving time bound of O(mα(n)) where α(n) is a very slowly growing function.

A very quickly growing function and its inverse

• For integers k≥0 and j ≥1, define A_k(j):
• A_k(j)= j+1 if k=0
• A_k-1^(j+1)(j) if k≥1
• Where A_k-1⁰(j)=j, A_k-1⁽ⁱ⁾(j)= A_k-1(A_k-1^(i-1)(j)) for i ≥1.
• k is called the level of the function and
• i in the above is called iterations.
• A_k(j) strictly increase with both j and k.
• Let us see how quick the increase is!!

Quickness of Function A_k(j)’s Increase

• Lemma 21.2 (Page 510):
• For any integer j, A₁(j) =2j+1.
• Proof:
• By induction on i, prove A₀ⁱ(j) =j+i.
• So A₁(j)= A₀^(j+1)(j) =j+(j+1)=2j+1.
• Lemma 21.3 (Page 510):
• For any integer j, A₂(j) =2^j+1(j+1)-1.
• Proof:
• By induction on i, prove A₁ⁱ(j) =2ⁱ(j+1)-1
• A₂(j)= A₁^(j+1)(j) = 2^j+1(j+1)-1.

How Quick A_k(j) Increase

• Let us see A_k(1): for k=0,1,2,3,4.
• A₀(1)=1+1=2
• A₁(1)=2*1+1=3
• A₂(1)=2¹⁺¹(1+1)-1=7
• A₃(1)=A₂⁽¹⁺¹⁾(1)=A₂⁽²⁾(1)=A₂(A₂(1))=A₂(7)=2⁷⁺¹(7+1)-1=2⁸*8-1=2047
• A₄(1)=A₃²(1)=A₃(A₃(1)) =A₃(2047)=A₂⁽²⁰⁴⁸⁾(2047)

>> A₂(2047) =2²⁰⁴⁸.2048-1 >2²⁰⁴⁸ =(2⁴)⁵¹² =(16)⁵¹²

• >>10⁸⁰ . (estimated number of atoms in universe)

Inverse of A_k(n):α(n)

• α(n)=min{k: A_k(1) ≥n} (so, A_α(n)(1) ≥n )
• α(n)= 0 for 0≤ n ≤2
• 1 n =3
• 2 for 4≤ n ≤7
• 3 for 8≤ n ≤2047
• 4 for 2048≤ n ≤A₄(1).
• Extremely slow increasing function.
• α(n) ≤4 for all practical purposes.

Another very slow increasing function

O(mα(n)) bound: Property of Ranks

• Lemma 21.4 (page 511):
• For all nodes x, rank[x] ≤rank[p[x]], with strict inequality if x≠p[x].
• Corollary 21.5 (page 511):
• As we follow the path from any node to the root, the node ranks strictly increase.
• Lemma 21.6 (page 512):
• Every node had rank at most n-1.
• Proof: rank begins with 0, increase possibly with only LINK operations, which is at most n-1 time.
• In fact, at most ⎣log(n)⎦.

O(mα(n)) bound proof

• Using amortized analysis (Chap. 17)
• Using LINK instead UNION (every UNION is done by two FIND-SETs and one LINK)
• Lemma 21.7 (page 512):
• Suppose converting a sequence S' of m' MAKE-SET, UNION, and FIND-SET operations into a sequence S of m MAKE-SET, LINK, FIND-SET by turning UNION to two FIND-SETs and one LINK, then if S runs in O(mα(n)), then S' runs in O(m'α(n)).
• Proof: because of m' ≤ m ≤3m' , thus m=O(m').

Potential Function

• For each node x, assign a potential function φ_q(x) after q operations.
• Then potential for entire forest, Φ_q=∑_xφ_q(x)
• Φ₀=0 at the beginning.
• Φ_q will never be negative.
• φ_q(x)= α(n)⋅rank[x] if x is a root or rank[x]=0.
• [α(n)-level(x)]⋅rank[x]-iter(x) otherwise.

level(x) and iter(x)

• level(x)=max{k: rank[p[x]]≥A_k(rank[x])}
• 0≤ Level(x)<α(n), since
• rank[p[x]]≥rank[x]+1=A₀(rank[x]) and
• A_α(n) (rank[x]) ≥ A_α(n) (1) ≥ n > rank[p[x]].
• iter(x)=max{i: rank[p[x]]≥A_level(x)⁽ⁱ⁾(rank[x])}
• 1≤ iter(x) ≤ rank[x], since
• rank[p[x]]≥A_level(x)(rank[x])=A_level(x)⁽¹⁾(rank[x]) and
• A_level(x)^(rank[x]+1)(rank[x])=A_level(x)+1(rank[x])>rank[p[x]].

Relations among rank[p[x]], level(x) and iter(x)

• Since rank[p[x]] monotonically increase over time, in order for iter(x) to decrease, level(x) must increase.
• Or say another way, as long as level(x) remains unchanged, iter(x) must either increase or remains unchanged.

Properties for Potential Function φ_q(x)

• Lemma 21.8 (page 514):
• For every node x, and for all q, 0≤ φ_q(x) ≤ α(n)⋅rank[x]
• Proof:
• if x is a root or rank[x]=0, then correct by definition.
• Suppose x is not a root and rank[x]>0,
• φ_q(x)= [α(n)-level(x)]⋅rank[x]-iter(x) ≥ (α(n)-(α(n)-1))⋅ rank[x]-rank[x] =rank[x]-rank[x]=0.
• φ_q(x)= [α(n)-level(x)]⋅rank[x]-iter(x) ≤ [α(n)-0]⋅rank[x]-1= α(n)⋅rank[x]-1<α(n)⋅rank[x]

Potential Changes of Operations

• Lemma 21.9 (page 515):
• Let x be a node that is not a root, and suppose qth operation is either LINK or FIND-SET. Then after the qth operation, φ_q(x) ≤ φ_q-1(x). Moreover, if rank[x] ≥ 1 and either level[x] or iter(x) changes due to the qth operation, then φ_q(x) ≤ φ_q-1(x)-1.
• Proof:
• x not root 🡪 rank[x] not change
• n not change🡪 α(n) not change.
• If rank[x]=0, then φ_q(x) = φ_q-1(x)=0. suppose rank[x]>0.
• If level(x) not change,
• If iter(x) not change, φ_q(x) = φ_q-1(x), since all keep same
• If iter(x) increase, then at lease by 1, φ_q(x) will decrease at least 1.
• If level(x) increases (at least by 1), then (α(n)-level(x))⋅rank[x] drops at least by rank[x] .
• Suppose iter(x) drops, then, the drop is at most rank[x]-1. so φ_q(x) will drop at least rank[x]-(rank[x]-1)=1. Thus φ_q(x) ≤ φ_q-1(x)-1.

Amortized Costs of Operations

• Lemma 21.10 (page 515):
• The amortized cost of each MAKE-SET operation is O(1).
• Proof: create a single node x with rank 0, so φ_q(x) =0. no other change to the forest, so Φ_q= Φ_q-1. The left is the actual cost, which is O(1).

Amortized Costs of Operations (cont.)

• Lemma 21.11 (page 515):
• The amortized cost of each LINK operation is O(α(n)).
• Proof: (LINK(x,y) makes y the parent of x).
• Actual cost for LINK operation is O(1).
• Considering potential change:
• Three kinds of nodes: x, y, and the old children of y.
• By Lemma 21.9, the potential of y’s old children not increase.
• For x (changed to non-root from a root), φ_q(x)= [α(n)-level(x)]⋅rank[x]-iter(x) ≤ [α(n)-0]⋅rank[x]-1= α(n)⋅rank[x]-1<α(n)⋅rank[x]=φ_q-1(x).
• For y, rank[y] may stay same or increase by 1, so φ_q(y)=α(n)⋅rank[y]=φ_q-1(y) or φ_q-1(y)+α(n).
• Thus the potential increase due to the LINK operation is at most α(n).
• Thus the amortized cost is O(1)+O(α(n))=O(α(n))

Amortized Costs of Operations (cont.)

• Lemma 21.12 (page 516):
• The amortized cost of each FIND-SET operation is O(α(n)).
• Proof: suppose there are s nodes in the find path.
• The actual cost of FIND-SET is O(s).
• Root’s potential does not change and no other node’s potential increases (by Lemma 21.9).
• At least max(0,s-(α(n)+2)) nodes on the find path have their potential decrease by at least 1.
• Thus the amortized cost is at most O(s)-(s-(α(n)+2)) =O(α(n)).

Proof of Lemma 21.12 (cont.)

• Proof that at lease max(0,s-(α(n)+2)) nodes on the find path have their potential decrease by at least 1.
• Let x be a node on the find path:
• rank[x]>0,
• followed somewhere by y that is not a root,
• and level(y)=level(x) just before FIND-SET.
• At most α(n)+2 nodes do not satisfy: 1th node, root node, the last node w for which level(w)=0,1,…, α(n)-1.
• Thus at least max(0,s-(α(n)+2)) nodes satisfy.
• Let us fix x, show x’s potential decreases by at least 1.

Proof of Lemma 21.12 (cont.)

• Let k=level(x)=level(y), Just prior to path compression caused by FIND-SET, we have
• rank[p[x]]≥A_k^(iter(x))(rank[x]) (by iter(x)’s def.)
• rank[p[y]]≥A_k(rank[y]) (by level(y)’s def.)
• rank[y]≥ rank[p[x]] (since y follows x somewhere).
• Let i=iter(x) before path compression, we have
• rank[p[y]]≥A_k(rank[y])

≥A_k(rank[p[x]]) (since A_k(j) is strictly increasing)

≥A_k(A_k^(iter(x))(rank[x]))

=A_k⁽ⁱ⁺¹⁾(rank[x])

• After path compression, rank[p[x]]=rank[p[y]], which not decrease, and rank[x] not change, so rank[p[x]]≥A_k⁽ⁱ⁺¹⁾(rank[x]).
• Which means that either iter(x) increases (to at least i+1), or level(x) to increase. Thus by Lemma 21.9, φ_q(x) ≤ φ_q-1(x)-1. that is x’s potential decreases by at least 1.
• As a result, we prove the lemma 21.12.

Upper bound for Disjoint-sets

• Theorem 21.13 (page 517):
• A sequence of m MAKE-SET, UNION, FIND-SET operations, n of which are MAKE-SET operations, can be performed on a disjoint-set forest with union by rank and path compression in worst cast time O(mα(n)).

Summary

• Disjoint set
• Three operations
• Different implementations and different costs
• Forest implementation:
• Union by rank and path compression
• Properties: rank, level, iter.
• Amortized analysis of the operations:
• Potential function.
• A_k(j) funcion:
• A_k(j)= j+1 if k=0
• A_k-1^(j+1)(j) if k≥1
• Where A_k-1⁰(j)=j, A_k-1⁽ⁱ⁾(j)= A_k-1(A_k-1^(i-1)(j)) for i ≥1.
• k is called the level of the function and
• i in the above is called iterations.
• α(n)=min{k: A_k(1) ≥ n}

A typical example using Disjoint Set –�Kruskal's algorithm (Minimum Spanning Tree)

• Idea
• sort the edges of G in increasing order by length
• keep a subgraph S of G, initially empty
• for each edge e in sorted order
• if the endpoints of e are disconnected in S
• add e to S
• Code
• S=∅
• For each vertex v
• MAKE-SET(v)
• Sort edges in non-decreasing order by weights
• For each edge (u,v) from beginning to end
• If (FIND-SET(u)!=FIND-SET(v))
• S=S ∪ {(u,v)}
• UNION(u,v)
• Return S

​

Minimum Spanning Tree -Prim’s Algorithm,

• Idea
• Begin from any node, each time add a new node which is closest to the existing subtree.
• Code -- MIN-SPT(G, w, r): key: key value and pi: parent
• For each vertex u
• key[u]= ∞
• pi[u]=NIL
• key[r]=0;
• Q =all vertices of G (formed as a priority queue)
• while (Q!=∅)
• u=Extract-MIN(Q)
• for each v ∈ adjacent[u]
• If (v ∈Q and w(u,v)<key[v])
• pi[v]=u;
• key[v]=w(u,v) //update the priority queue

​

• Single source shortest path: Dijkstra’s algorithm
• w(u,v)<key[v] 🡺 key[u]+w(u,v)<key[v]
• key[v]=w(u,v) 🡺 key[v]=key[u]+w(u,v)

​

Shortest paths among all pairs—�Floyd-Warshall algorithm

• Given G=(V, E, w)
• suppose V={1,2,…,n} are vertices and w is weight matrix on edges
• Consider a subset of vertices {1,2,…, k} for some k, for any pair of i and j, consider all the paths from i to j including only vertices from 1,2,…,to k and let p be one of the minimum such paths (also a simple path).

Floyd-Warshall algorithm (cont.)

• There are two cases:
• K is not on path p. In this case, path p will be a minimum path including only vertices of 1,2,…, k-1.
• k is on path p. In this case, the portion of i to k on path p will be a minimum path from i to k including only vertices 1,2, …, k-1, similarly for the pair of k and j.

Floyd-Warshall algorithm (cont.)

• Let D(i,j,k) denote the (length of) minimum path between i and j including only vertices 1,2,…, k.
• D(i,j,n) will be the answer for any pair i and j.
• Recursive definition:

​

​

​

​

• Algorithm:
• Initialize for k=0
• For (k=1 to n)
• For (i=1 to n) and for (j=1 to n) D(i,j,k)=min{D(i,j,k-1), D(i,k,k-1)+D(k,j,k-1)}

​

​

​