9.2-4

9.2-4 Suppose we use RANDOMIZED-SELECT to select the minimum element of the array A = {3, 2, 9, 0, 7, 5, 4, 8, 6, 1}. Describe a sequence of partitions that results in a worst-case performance of RANDOMIZED-SELECT.
Worst case occurs when the recurence is $T(n) = T(n-1)+\theta(n)$ there two ways to do it. Parition from 0 -9 or from 9 -0. ex: {0} {3,2,9,0,7,5,4,8,6,1} {1} {3,2,9,0,7,5,4,8,6,1} .... {9} {9}{0,1,2,3,4,5,6,7,8} ... {0}

9.2-3

Write an iterative version of RANDOMIZED-SELECT. RANDOMIZED-SELECT(A,p,r) while(p < r) If p == r return A[r]; q = RANDOM-PARTITION(A,p,r) k = q-p+1 If i == k return A[i] If i > k p = q+1 i = i - k else q = q-1

9.2-2

Argue that the indicator random variable $X_k$ and the value $T(max(k - 1, n - k))$ are independent.
$X_k$ and $T(max(k - 1, n - k))$ are independent. Because $X_k$(sub array A[p..q] has exactly k elements k=1..n) is dependent on random choice made by the random-partition call and $T(max(k - 1, n - k))$ is making its own random choices because it is a different recursive call. Hence they are independent.

9.2-1

Show that RANDOMIZED-SELECT never makes a recursive call to a 0-length array.
RANDOMIZED-SELECT has two recursive calls for i < k and i >k. If i > k the values q is reduced by (q = q-1 see the method argument). If we assume i > k is called in every recursive call the q is decreased by 1 every time. The base case will return when p = q . The least values q can take is p when (q=p) we have 1-length array. So the recursion returns for 1-length array.

9.1-2

9.1-2 Prove the lower bound of $3\lceil n/2 \rceil - 2$ comparisons in the worst case to find both the maximum and minimum of n numbers. (Hint: Consider how many numbers are potentially either the maximum or minimum, and investigate how a comparison affects these counts.)

We need to analyze even and odd case separately.

n is Even: If n is even we will divide the numbers in to n/2 pairs and compare elements in pairs and keep the small elements in array and larger elements in another array(you can swap with in the array as well if changing the input is allowed). To compare n/2 with n/2 elements we need n/2 comparisons. We now have Small array and large array. The smallest element must be in smallest array and largest element must be in the largest array. We use MINIMUM(A) to find smallest element on small array similarly we can MAXIMUM(A) to find the largest on large array. This will take n/2 - 1 for MINIMUM and MAXIMUM operations. since n is even n/2 = $\lceil n/2 \rceil$ We can now add up all comparisons $$\lceil n/2\rceil+\lceil n/2\rceil-1+\lceil n/2\rceil-1$$ $$3\lceil n/2\rceil-2$$ n is odd: If n is odd assign maximum and minimum to the first element and divide the array in to (n-1)/2 pairs. Let compare elements in pairs and keep the small elements in array and larger elements in another array. To compare (n-1)/2 pairs of elements we need (n-1)/2 comparisons. we now have a small array with small numbers and large array with large numbers. The smallest element must in small array and similarly large element must be in large array. We can use MINIMUM(A) to find a smallest element on small array and MAXIMUM(A) on large array to find the largest element.This needs (n-1)/2 -1 for both arrays. Later we need to compare the first element which we assigned as maximum and minimum element with smallest and largest element to find smallest and largest element. It will take two comparisons. since n is even (n-1)/2 = $\lceil (n-1)/2 \rceil$ We can now add up all comparisons $$\lceil (n-1)/2\rceil+\lceil (n-1)/2\rceil-1+\lceil (n-1)/2\rceil-1+2$$ $$3\lceil (n-1)/2\rceil$$ $$3\lceil n/2 \rceil-3/2$$ since 2 > 3/2 .The no of comparisons are more when n is even. The worst case occurs when n is even.

9.1-1

9.1-1 Show that the second smallest of n elements can be found with n + lg n - 2 comparisons in the worst case. (Hint: Also find the smallest element.)

To find the smallest number n-1 comparisons are made. To find the smallest conduct a tournament every number looses exactly once except the smallest. If we draw a binary tree there are n leaves and n-1 non leaf nodes. Every non leaf node represents a comparison hence we need n-1 comparisons. To find the smallest number the second smallest number must have come out smallest in every comparison except with the smallest number. To find the second smallest number conduct another tournament to compares all these numbers. At most log n elements(the height of binary tree) were compared with smallest number.So finding the smallest of these will take $\lceil log n \rceil - 1$ the total number of comparisions are $n- 1+ \lceil log n \rceil - 1$

8-7