1. The disjoint set analysis in Section 8.6 can be re?ned to provide tight bounds for small N.
a. Show that C(M, N, 0) and C(M, N, 1) are both 0.
b. Show that C(M, N, 2) is at most M.
c. Let r ≤ 8. Choose s = 2 and show that C(M, N, r) is at most M + N.
2. Suppose we implement partial path compression on find(i) by making every other node on the path from i to the root link to its grandparent (where this makes sense). This is known as path halving.
a. Write a procedure to do this.
b. Prove that if path halving is performed on the finds and either union-by-height or union-by-size is used, the worst-case running time is O(Mα(M, N)).