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

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