CSIT 5500 Advanced Algorithms2021 Spring SemesterWritten Assignment 1Handed out: Feb 15Due: 21:00 on March 1Please submit a soft copy via the canvas system by the due date and time shownabove. Late assignments will not be graded.1. (10 points) This question is about red-black tree.(a) (7 points) Starting from an initially empty red-back tree T , insert the numbers 1, 5, 2,6, 7, 4, 9, 10, 3, 8 in this order into T. Show the tree T after inserting each number.You do not need to show other intermediate steps.(b) (3 points) Starting from the final T that you obtained in (a) above containing thenumbers 1 to 10, delete the numbers 7, 4, 1, in this order. Show the tree T after deletingeach number. You do not need to show other intermediate steps.2. (10 points) Consider the following divide-and-conquer algorithm that works on an arrayA[1..n] of integers.Recursive(A, p, r)(1) k := r − p + 1;(2) If k ≤ 3 then return max{A[p], A[r]};(3) Otherwise, perform the following steps:(a) m := d3k/4e;(b) m1:= Recursive(A, p, p + m − 1);(c) m2:= Recursive(A, r − m + 1, r);(d) m3:= Recursive(A, p, p + m − 1);(e) m4:= −∞;(f) for i = p to p + m doif A[i] > m4then m4:= A[i];(g) return max{m1, m2, m3, m4}Write the recurrence, including the boundary condition, for the worst-case running time ofthe above algorithm. Solve the recurrence to obtain the worst-case running time of the abovealgorithm in terms of the big-Oh notation.3. (10 points) Let X[0..n − 1] and Y [0..n − 1] be two arrays, each containing n numbers inincreasing order. We assume that the numbers in X and Y are distinct. Design an algorithmto find the median of all numbers in X and Y . That is, if we conceptually put all numbersin X and Y in increasing order, the middle number in this list is the desired output. Youralgorithm is required to run in O(log n) time. Explain why your algorithm is correct and whyit runs in O(log n)