CSC263H1 Lecture Notes - Lecture 11: Disjoint Sets, Linked List, Iterated Logarithm
18 Oct 2017
School
Department
Course
Professor
Document Summary
Csc 263 lecture summary for week 11 winter 2017. Objects: collection of nonempty disjoint sets s = {s_1,s_2,,s_k} -- each s_i is a nonempty set that has _no_ element in common with any other. S_j (s_i n s_j = {} for all i != j). Each set is identified by a unique element called its representative. Make-set(x): given element x that does not already belong to one of the sets, create a new set {x} that contains only x (and assign x as the representative of that new set). Find-set(x): given element x, return the representative of the set that contains x (or nil if x does not belong to any set). Union(x,y): given two distinct elements x and y, let s_x be the set that contains x and s_y be the set that contains y. Form a new set consisting of s_x u s_y and remove s_x and s_y from the collection (since all the sets must be disjoint).
