Problem 3: Design and analyze a divide and conquer algorithm that determines the minimum and maximum value in an unsorted list (array). a) Verbally describe and write pseudo-code for the min_and_max algorithm. b) Give the recurrence. c) Solve the recurrence to determine the asymptotic running time of the algorithm. How does the theoretical running time of the recursive min_and_max algorithm compare to that of an iterative algorithm for finding the minimum and maximum values of an array.

Problem 4: Consider the following pseudocode for a sorting algorithm. StoogeSort(A[0 ... n - 1]) if n = 2 and A[0] > A[1] swap A[0] and A[1] else if n > 2 m = ceiling(2n/3) StoogeSort(A[0 ... m - 1]) StoogeSort(A[n - m ... n - 1]) Stoogesort(A[0 ... m - 1]) a) Verbally describe how the STOOGESORT algorithm sorts its input. b) Would STOOGESORT still sort correctly if we replaced k = ceiling(2n/3) with k = floor(2n/3)? If yes prove if no give a counterexample. (Hint: what happens when n = 4?) c) State a recurrence for the number of comparisons executed by STOOGESORT. d) Solve the recurrence to determine the asymptotic running time.