UNB/ CS/ David Bremner/ teaching/ cs3383/ assignments/ CS3383 Assignment 6

Introduction

See the general rules about assignments in this course.

DUE: 2016-11-03, 16:30 in the assignment box.

Questions

1 Prove that Kruskals algorithm (below) is correct by using the Cut Property of minimum spanning trees.

∀u ∈ V makeset(u)
X ← {}
sort edges by weight
for (u, v) ∈ E do
    if find(u) ≠ find(v) then
        X ← X ∪ {(u, v)}
        union(u,v)
    end if
end for

2 (Ex 5.12 in DPV) Suppose you implement the disjoint-sets data structure using union-by-rank but not path compression. Give a sequence of m union and find operations on n elements that take Ω(m log n) time.

3 Below you will find pseudocode for find for disjoint sets that does "path compression". We will analyze this function later; for now, find a non-recursive implimentation that performs the same updates on the disjoint-set data structure.

function find(key)
    if parent[key]≠key then
        parent [key] ← find(parent [key])
    end if
    return parent[key]
end function