Exercise ( k-th Smallest Element) Given an (unsorted) array A[1..n] containing distinct integers and a parameter 1kn, your task is to find the k-th smallest element in A[1n]. a. Design an algorithm solving this problem in time O(nlogk), using an appropriate dictionary data structure. b. Design a divide-and-conquer algorithm for this problem in time O(n). You may use the fact that a median element of A[1n] (i.e., an array element p such that A contains at most 2n elements which are smaller than p and at most 2n elements which are larger than p ) can be computed in time O(n) Hint: For inspiration, recall the algorithm QuicKSorT from lecture 4