Algorithms analysis and designs 2. (12 points) For each of the following problems, you have to nd an ecient algorithm, and give a clear description of your algorithm for the problem state (no explanations necessary) what is the worst case time analysis (use the big O notation) of your algorithm. If you can't come up with an algorithm which works within the specied time bounds, try to at least nd a correct, slower algorithm - you will get partial credit for this. (a) Let A be an unsorted array (no repetitions) with n positive integers. You have to nd an O(n) time algorithm which nds the two numbers x; y; x > y from A such that the dierence between them is as a large as possible i.e. x y is maximized. For example, if the input is A = 6; 2; 10000; 8, the output should be x = 10000; y = 2. Show your algorithm and state (no explanation necessary) what the worst-case time is. (b) Let B be a sorted array (no repetitions) with n positive integers. You have to nd an O(n) time algorithm which nds the two numbers x; y; x > y from B such that the dierence between them is as a small as possible i.e. xy is minimized. For example, if the input is B = 2; 6; 8; 10000, the output should be x = 8; y = 6. Show your algorithm and state (no explanation necessary) what the worst-case time is. (c) Let A be an unsorted array (no repetitions) with n positive integers. You have to nd an O(n log n) time algorithm which nds the two numbers x; y; x > y from A such that the dierence between them is as a small as possible i.e. x y is minimized. For example, if the input is A = 6; 2; 10000; 8, the output should be x = 8; y = 6. Show your algorithm and state (no explanation necessary) what the worst-case time is.