it is just disjoint set structure and algorithms

Q3 (15 points) This question is related to disjoint set operations. Assume that we are using union by rank and find with path compression. Suppose that you are given a disjoint set structure described by the following array. The following three sub-questions all refer to this disjoint set (not the disjoint set you obtained after doing some operations). i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 A[i] -3 1 1 3 1 5 5 7 -3 9 9 11 9 13 13 15 (a) On the answer sheet, show the result after applying union(16, 4) to the disjoint set at the start of this question. (b) On the answer sheet, show the result after applying union (6, 14) to the disjoint set at the start of this question. c) On the answer sheet, show the result after applying find-set (7), find-set (15) to the disjoint set at the start of this question. Q4 (8 points) On the answer sheet, answer the following questions. (a) What is the worst-case time complexity of build-heap on n elements? (b) What is the worst-case time complexity of extract-max on a max-heap with n elements? (c) What is the worst-case time complexity of insertion onto a max-heap with n elements? (d) What is the worst-case time complexity of increase-key onto a max-heap with n ele- ments? (e) What is the worst-case time complexity of find-set in a disjoint set data structure, assuming we are using union by rank and find with path compression? (f) What is the worst-case time complexity of link in a disjoint set data structure, assuming we are using union by rank and find with path compression? (g) What is the worst-case time complexity of union in a disjoint set data structure, assuming we are using union by rank and find with path compression? (h) What is the worst-case time complexity of m operations of union, find, and make-set, including n make-set operations at the start? Q3: Read the instructions for question Q3 in the assignment document. For each of the three sub-questions, write your answer to the question in the given space. (a): After performing union(16,4), we have A[1]= A[4= A[9]= A[15]= A[16]= (b): After performing union(6, 14), we have A[1]= A[61- A[9]= A[14]= A[15]- (c): After performing find-set(7) and find-set(15), we have A[1] A[7= A[8]= A[9]= A[15]= Q4: Read the instructions for question Q4 in the question document. For each of the eight sub-questions, check the box that most accurately describes the corresponding time complexity. (a): (logn) 2(logn) (logn) O(n) 12(n) e(n) O(nlogn) 2n logn) Onlogn) None of the above (b): O(logn) S2(logn) (logn) O(n) 12(n) e(n) O(nlogn) 2 (n logn) enlogn) (1) (c): O(logn) 2(logn) (logn) O(n) 12(n) e(n) O(nlogn) S2 (n logn) (alogn) (1) (d): O(logn) 12(logn) (logn) 0(n) S2(n) e(n) O(nlogn) 2n logn) nlogn) (1) (e): O(logn) 2 (logn) (logn) O(n) (n) e(n) Onlogn) Onlogn) nlogn) (1) (f): (logn) 2(logn) (logn) 0(n) 12(n) e(n) O(nlogn) S2(nlogn) en logn) e(1) (g): O(logn) (logn) e(logo) 0(n) 12(n) e(n) Onlogn) L2(n logn) nlog n) (1) (h): (m) S2(m) (m) 0(mlogn) 12(mlogn) emlogn) 0(ma(m,n)), where a(m,n) is the inverse Ackermann function. Q3 (15 points) This question is related to disjoint set operations. Assume that we are using union by rank and find with path compression. Suppose that you are given a disjoint set structure described by the following array. The following three sub-questions all refer to this disjoint set (not the disjoint set you obtained after doing some operations). i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 A[i] -3 1 1 3 1 5 5 7 -3 9 9 11 9 13 13 15 (a) On the answer sheet, show the result after applying union(16, 4) to the disjoint set at the start of this question. (b) On the answer sheet, show the result after applying union (6, 14) to the disjoint set at the start of this question. c) On the answer sheet, show the result after applying find-set (7), find-set (15) to the disjoint set at the start of this question. Q4 (8 points) On the answer sheet, answer the following questions. (a) What is the worst-case time complexity of build-heap on n elements? (b) What is the worst-case time complexity of extract-max on a max-heap with n elements? (c) What is the worst-case time complexity of insertion onto a max-heap with n elements? (d) What is the worst-case time complexity of increase-key onto a max-heap with n ele- ments? (e) What is the worst-case time complexity of find-set in a disjoint set data structure, assuming we are using union by rank and find with path compression? (f) What is the worst-case time complexity of link in a disjoint set data structure, assuming we are using union by rank and find with path compression? (g) What is the worst-case time complexity of union in a disjoint set data structure, assuming we are using union by rank and find with path compression? (h) What is the worst-case time complexity of m operations of union, find, and make-set, including n make-set operations at the start? Q3: Read the instructions for question Q3 in the assignment document. For each of the three sub-questions, write your answer to the question in the given space. (a): After performing union(16,4), we have A[1]= A[4= A[9]= A[15]= A[16]= (b): After performing union(6, 14), we have A[1]= A[61- A[9]= A[14]= A[15]- (c): After performing find-set(7) and find-set(15), we have A[1] A[7= A[8]= A[9]= A[15]= Q4: Read the instructions for question Q4 in the question document. For each of the eight sub-questions, check the box that most accurately describes the corresponding time complexity. (a): (logn) 2(logn) (logn) O(n) 12(n) e(n) O(nlogn) 2n logn) Onlogn) None of the above (b): O(logn) S2(logn) (logn) O(n) 12(n) e(n) O(nlogn) 2 (n logn) enlogn) (1) (c): O(logn) 2(logn) (logn) O(n) 12(n) e(n) O(nlogn) S2 (n logn) (alogn) (1) (d): O(logn) 12(logn) (logn) 0(n) S2(n) e(n) O(nlogn) 2n logn) nlogn) (1) (e): O(logn) 2 (logn) (logn) O(n) (n) e(n) Onlogn) Onlogn) nlogn) (1) (f): (logn) 2(logn) (logn) 0(n) 12(n) e(n) O(nlogn) S2(nlogn) en logn) e(1) (g): O(logn) (logn) e(logo) 0(n) 12(n) e(n) Onlogn) L2(n logn) nlog n) (1) (h): (m) S2(m) (m) 0(mlogn) 12(mlogn) emlogn) 0(ma(m,n)), where a(m,n) is the inverse Ackermann function