Pseudocode

Remarks: 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.

Dont write programs for your solutions.

Question 5:

a. What needs to happen for the maximum and minimum to be compared in Quicksort?

b. Is the following true or false and try to prove it. Let Ai be the I-th smallest number in an array, and let Ai+1 be the (i + 1)-th smaller number in an array. Then in every algorithm based only on comparisons Ai and Ai+1 must be compared.

c. Answer yes or no and explain: If there are i < j so that A[i] = A[j] then in Mergesort A[i] will come before A[j] (namely Mergesort will not change the order of two equal value elements).