DO NOT WRITE CODE, WRITE PSEUDOCODE AND PROVE RUNTIME

5) (Reducing k th-smallest to median-finding) (15 points) If we have an algorithm that finds the k th-smallest element of an n element set, we can obtain an algorithm for finding the median element simply by calling the k th-smallest algorithm with k=(n+1)/2. This question asks you to do the converse. Given an algorithm that finds the median element of an n element set in (n) time, design an algorithm that finds the k th-smallest element for arbitrary k in (n) time using the median-finding algorithm. Be sure to analyze the running time of your algorithm. (Note: Do not invoke the linear-time k th-smallest algorithm presented in class and the book. You must reduce the problem of finding the k th-smallest element to the problem of finding the median.)