Q: In all the algorithms, always explain (more precisely try to prove) the correctness of your algorithm. You always must analyze the running time of any algorithm. The time complexity should be as small as possible. A correct algorithm with large complexity, may not get full credit. Do EVEN THINK OF WRITING PROGRAMS.

Question 5: 1. What needs to happen for the maximum and minimum to be compared in Quick- sort. 2. Is the following true or false and try to prove it. Let A be the i'th smallest number in an array, and let A;+1 be the (i + 1) th smaller number in an array. Then in every algorithm based on comparisons A; and Ai+1 must be compared. 1 3. Answer yes or no and explain: If there are i