Winter 2019
CSE 431: Algorithm Analysis
School of Computer Science and Engineering
California State University, San Bernardino

Last modified: Tuesday, Mar 12

Evolution of find() and merge()
N items (initially N disjoint sets; one item per set)
n find() operations
m merge() operations
Note m ≤ N-1. If n & N are comparable (d*n = N for some constant d > 0) then all n, m, and N are comparable
find1() Θ(1)
merge1() Θ(N)
 
n find1() Θ(n)
m merge1() Θ(mN)=Θ(n2)
Total Θ(n2)
find2() Θ(N)
merge2() Θ(1)
 
n find2() Θ(n2)
m merge2() Θ(m)=Θ(n)
Total Θ(n2)
find2() Θ(log N)
merge3() Θ(1)
merge3() keeps height ≤ log N
n find2() Θ(n log n)
m merge3() Θ(m)=Θ(n)
Total Θ(n log n)
find3() Θ(log N)
merge3() Θ(1)
find3() performs path compression
n find3()  
m merge3() c = n + m
Total Θ(c α(c,N)) = Θ(c) = Θ(n+m) = Θ(n)


Homework 5. Due Mon, Mar 18 NO LATE SUBMISSION
Problems 5.25, 5.27, 6.4, 6.10, 7.12

Homework 4. Due Wed, Mar 6
Problems 5.7, 5.10, 5.11, 5.22, 5.24

Midterm: Wed, Feb 20

Homework 3. Due Wed, Feb 13
Problems 4.2, 4.5, 4.29, 4.33, 4.37.

Homework 2. Due Mon, Feb 4
Problems 3.2, 3.5, 3.8, 3.10, 3.21.

Homework 1. Due Mon, Jan 28
Problems 1.8 (give an algorithm), 1.17, 1.27, 2.6, 2.11.

Syllabus