7. In this lecture note, the quicksort algorithm is given. (a) Write the pseudocode for quicksort. (Or, a source code program in Java programming language. If this is the case, you are ONLY required to copy your source code in a Word file.) (b) Show that its worst-case running time on an array of size n is (n ). (Or, if you use source code, then create an input array A[0.. 100] as your input, and compute the number of your basic operations to establish t is (n*).) (c) Show that its expected running time satisfies the recurrence relation Then show that the solution to this recurrence is O(n log n) 8. Here we look at an alternative algorithm based on divide-and-conquer if a, b are even if a is odd, b is even if a, b are odd 2 gcd(a/2, b/2) gcd (a, b)gcd(a, b/2) gcd ((a b)/2, b) Show this rule is true (b) Give an efficient divide-and-conquer algorithm for finding greatest common divisor (c) How does the efficiency of your algorithm compare to Euclid's algorithm if a and b are n-bit integers? (In particular, since n might be large you cannot assume that basic arithmetic operations like addition take constant time.) 9. Use Algorithm prod2(x, y) for large integer multiplication to find the product 2506 and 69309. How many multiplication are needed to find the product of the two integers if prob2(x, y) is used