## 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
```