You can assume the programming language is Python.

Consider the following code for checking if the input array A is a max-heap: over A CON 1 // Assume arrays are zero-indexed 2 // and A.size() returns number of elements in A 3 CheckMaxHeap (A): for i from 0 to floor (A. size ()/2)-1: if CheckMax HeapHelper (A, i) == False return false return True 12 9 CheckMaxHeapHelper (A, i): 10 if 2i+1 A[i]: return false if 2i+2 A[i]: return false return True 5 16 (b) (8 points) Now consider an array A with five elements (suppose A is (-indexed). Suppose the elements of A are filled with a random permutation of {1, 2, 3, 4, 5}. i. (2 points) What is the probability that CheckMaxHeapHelper(A, 0) returns True? Justify your answer care- fully: show your work and explain your calculation. ii. (4 points) What is the probability that CheckMaxHeap(A) returns True? Justify your answer carefully: show your work and explain your calculation. Enumeration is not a justification. iii. (2 points) If we run CheckMaxHeap(A), what is the expected number of times CheckMaxHeapHelper is called? Justify your answer carefully: show your work and explain your calculation. Consider the following code for checking if the input array A is a max-heap: over A CON 1 // Assume arrays are zero-indexed 2 // and A.size() returns number of elements in A 3 CheckMaxHeap (A): for i from 0 to floor (A. size ()/2)-1: if CheckMax HeapHelper (A, i) == False return false return True 12 9 CheckMaxHeapHelper (A, i): 10 if 2i+1 A[i]: return false if 2i+2 A[i]: return false return True 5 16 (b) (8 points) Now consider an array A with five elements (suppose A is (-indexed). Suppose the elements of A are filled with a random permutation of {1, 2, 3, 4, 5}. i. (2 points) What is the probability that CheckMaxHeapHelper(A, 0) returns True? Justify your answer care- fully: show your work and explain your calculation. ii. (4 points) What is the probability that CheckMaxHeap(A) returns True? Justify your answer carefully: show your work and explain your calculation. Enumeration is not a justification. iii. (2 points) If we run CheckMaxHeap(A), what is the expected number of times CheckMaxHeapHelper is called? Justify your answer carefully: show your work and explain your calculation