1.

Illustrate the execution of QuickSort on the array A =(20, 17, 35, 30, 15, 14, 36, 12). Use the version of Quick Sort presented in the textbook. Regarding the level of illustration, follow the level of illustration done in class but complete the illustration until the end (array is sorted).

2.

Give a recursive version of the algorithm Insertion-Sort based on the following paradigm: to sort A[1..n], we first sort A[1..n1] recursively and then insert A[n] in its appropriate position. Write a pseudocode for the recursive version of Insertion-Sort and analyze its running time by giving a recurrence relation for the running time and then solving it

3.

Suppose that we are given an array A[1..n] of integers (note that integers can be negative) such that A[1] < A[2] < . . . < A[n]. Give an O(lg n) time algorithm to decide if there exists an index 1 i n such that A[i] = i.