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

8-6

8-6 Lower bound on merging sorted lists

The problem of merging two sorted lists arises frequently. We have seen a procedure for it as the subroutine MERGE in Section 2.3.1. In this problem, we will prove a lower bound of 2n - 1 on the worst-case number of comparisons required to merge two sorted lists, each containing n items. First we will show a lower bound of 2n - o(n) comparisons by using a decision tree.

a. Given 2n numbers, compute the number of possible ways to divide them into two sorted lists, each with n numbers.

b. Using a decision tree and your answer to part (a), show that any algorithm that correctly merges two sorted lists must perform at least 2n - o(n) comparisons. Now we will show a slightly tighter 2n - 1 bound.

c. Show that if two elements are consecutive in the sorted order and from different lists, then they must be compared.

d. Use your answer to the previous part to show a lower bound of 2n - 1 comparisons for merging two sorted lists.

a. ${{2n}\choose {n}}$
b. $${{2n}\choose {n}}$$ $$2n!/{n!}^2}$$ using stirling approximation $$\sqrt{4\pi n}. (2n/e)^2/(\sqrt{2\pi n} e^{1/12n})^2$$ for binary tree there will be $2^h$ leaves $$2^h = 2n - log 2\pi n$$ $$2^h = 2n - O(n)$$ c. If two list are sorted by merge procedure and the list needed to be merged. Since the elements are in two different lists we dont know if they are equal or greater or less than to know the relationship we need to compare them and arrange in the final array according to the order.

d. Lets assume the elements in first sorted list $L = {l_1,l_2...1_n}$ and second sorted list as $R= {r_1,r_2,r_3,r_4..r_n}$ if the elements in L list are all equal and greater than every element in R list. Then the merge procedure will compare the first element($l_1$) in the L list to every element in L the number of comparisons are n-1 and also according to c we need to compare two elements if they are consecutive in sorted order and from different list. Now since $l_1$ is greater than every element in R list we compare n times. Hence the running time is 2n -1.

8-5

8-5 Average sorting Suppose that, instead of sorting an array, we just require that the elements increase on average. More precisely, we call an n-element array A k-sorted if, for all i = 1,2....n k, the following holds:

$$ \frac{\sum_{j=i}^{i+k-1} A[j]} {k} \leq \frac{\sum_{j=i+1}^{i+k} A[j]} {k} $$ a. What does it mean for an array to be 1-sorted?
b. Give a permutation of the numbers 1,2...,10 that is 2-sorted, but not sorted. c. Prove that an n-element array is k-sorted if and only if $A[i] \leq A[i + k]$ for all i = 1,2,...,n -k.

d. Give an algorithm that k-sorts an n-element array in $O(n lg.n/k)$ time. We can also show a lower bound on the time to produce a k-sorted array, when k is a constant.
e. Show that we can sort a k-sorted array of length n in $O(n lg k)$ time. (Hint: Use the solution to Exercise 6.5-9. )
f. Show that when k is a constant, k-sorting an n-element array requires $ \Omega(n lg n)$ time. (Hint: Use the solution to the previous part along with the lower bound on comparison sorts.)
a. It is sorted.c has the answer for this puzzle for 1 sorted the it should satisfy $A[i] \leq A[i + 1]$ . hence the i+1 should always be greater than ith element where i is from 1..n.
b. Any permuatation that violates $A[i] \leq A[i+2]$ will work. ex: 1 3 2 4 5 6 7 8 9 10.
c. from the inequality for k - sorted array. $$ \sum_{j=i}^i+k-1 A[j] \over k \leq \sum_{j=i+1}^i+k A[j]$$ cancelling k on both sides $$ \sum_{j=i}^i+k-1 A[j] \leq \sum_{j=i+1}^i+k A[j]$$ expanding summation $$ A[i]+...+A[i+k-1] \leq A[i+1]+..+A[i+k]$$ cancelling elements from A[i+1] to A[i+k-1] $$ A[i] \leq A[i+k]$$ d. if we split the array in to groups of n/k and sort each group of n/k elements using any comparison sort the running time is $O(n/k log n/k )$. but since we do it for k times the running time is $O(k.n/k. log n/k$ = $O(n log n/k )$ e. If we sort the array using d algorithm and we have k sorted list we build MIN-HEAP on first k elements and EXTRACT-MIN-HEAP and repeat this for n/k times the running time is O(n log k). f. we can use the decision tree for calculating the lower bound. The leaves of the decision tree are various permutations of k-sorted array. $$ {{n} \choose {k}} . {{n-k} \choose {k}} . {{n-2k} \choose {k}}..{{k} \choose {k}} $$ $$ n!/k!(n-k)! . (n-k)!/(n-2k!).k! . (n-2k)!/(n-3k)! k! ..... k!/0! k! $$ $$ n!/ {k!}^{n/k} $$ since it is binary the no of leaves at height h is $$ 2^h \geq n!/ {k!}^{n/k} $$ if k were a constant lets replace k with c $$ 2^h \geq n!/ c $$ applying log $$ h \geq log( n!/ c) $$ $$ h \geq log( n!)- log c $$ log c should be negative $$log c < 0$$ $$ c < 1$$ $$ h \geq n log( n)$$

8-4

Water jugs Suppose that you are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, for every red jug, there is a blue jug that holds the same amount of water, and vice versa.

Your task is to find a grouping of the jugs into pairs of red and blue jugs that hold the same amount of water. To do so, you may perform the following operation: pick a pair of jugs in which one is red and one is blue, fill the red jug with water, and then pour the water into the blue jug. This operation will tell you whether the red or the blue jug can hold more water, or that they have the same volume. Assume that such a comparison takes one time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping. Remember that you may not directly compare two red jugs or two blue jugs.

a. Describe a deterministic algorithm that uses $\theta(n^2)$ comparisons to group the jugs into pairs.
b. Prove a lower bound of $ \Omega(n lg n)$ for the number of comparisons that an algorithm solving this problem must make.
c. Give a randomized algorithm whose expected number of comparisons is $O(n lg n)$, and prove that this bound is correct. What is the worst-case number of comparisons for your algorithm?

a. If we compare each red jug with each blue jug since there are n red jugs and n blue jugs we get $\theta(n^2)$.

b. The algorithms has to make a series of comparisons to group the jugs in to groups. We can view the comparisons as a decision tree. Every internal node will have a Red jug and a blue jug and three children less than red jug, greater than red jug and equal to red jug. The height of the decision tree is the worst case of comparisons the algorithm has to make to determine matching.To bound the height lets compute the total number possible matchings of n red and n blue jugs.

If we label n red jugs from 1..n and n blue jugs from 1..n then

${i,\pi(i)}$ for i = 1..n $\pi$ is a permutation on {1..n}

since every permutation of $\pi$ corresponds to a different outcome we have n! outcomes.(if we draw a decision tree it will have to for groupings of jugs). Now since every node has a branching factor of 3.let h be the height of the tree, The tree should have at most $3^h$ leaves. $$ n! \leq 3^h$$ $$ log_3 n! \leq h$$ $$ n log n \leq h$$(Stirling app.) $$h = \Omega(n log n)$$ c. Assuming R jugs are labeled from 1..n and red jugs from 1..n. The output of the algorithm will contain distinct pairs of (i,j) where i corresponds to red and j corresponds blue jug with equal quantity. The procedure Matchjugs needs one condition to be satisfied $|R|=|B|$ Match-Jugs(R,B)

If |R| = 0
then return
If |R| = 1
then return R(1),B(1)
else
$$r \leftarrow a randomly chosen jug in R$$ compare r to every jug of B
$$B_< \leftarrow all elements of B jug less than r$$ $$B_> \leftarrow all elements of B jug greater than r$$ $$b the one jug in b with same size as r$$ $$R_< \leftarrow all elements of B jug less than b$$ $$R_> \leftarrow all elements of B jug greater than b$$ output("r","b")
Match-Jugs($R_<,B_<$)
Match-Jugs($R_>,B_>$)
What about the running time? The analysis of the expected number of comparisons is similar to that of the quicksort algorithm in Section 7.4.2. Let us order the jugs as r1, . . . , rn and b1, . . . , bn where ri < ri+1 and bi < bi+1 for i = 1, . . . , n, and ri = bi . Our analysis uses indicator random variables Xi j = I {red jug $r_i$ is compared to blue jug $b_j$ } .

As in quicksort, a given pair ri and bj is compared at most once. When we compare $r_i$ to every jug in B, jug $r_i$ will not be put in either R< or R>. When we compare bi to every jug in R −{$r_i$ }, jug bi is not put into either B< or B>. The total number of comparisons is $$X = \sum_{i=1}^n−1 \sum_{j=i+1}^n Xij $$.

To calculate the expected value of X, we follow the quicksort analysis to arrive at $$E [X] = \sum_{i=1}^n−1 \sum_{j=i+1}^n Pr {r_i is compared to b_j } .$$ As in the quicksort analysis, once we choose a jug $r_k$ such that $r_i < r_k < b_j$, we will put $r_i$ in $R_<$ and $b_j$ in $B_>$, and so $r_i$ and $b_j$ will never be compared again. Let us denote $R_ij = {r_i , . . . , r_j }$. Then jugs $r_i$ and $b_j$ will be compared if and only if the Þrst jug in Ri j to be chosen is either ri or r j . Still following the quicksort analysis, until a jug from $R_ij$ is chosen, the entire set Ri j is together. Any jug in $R_ij$ is equally likely to be Þrst one chosen. Since $|R_ij |$ = j − i + 1, the probability of any given jug being the Þrst one chosen in $R_ij$ is 1/( j−i+1). The remainder of the analysis is the same as the quicksort analysis, and we arrive at the solution of $O(n lg n)$ comparisons.

Just like in quicksort, in the worst case we always choose the largest (or smallest) jug to partition the sets, which reduces the set sizes by only 1. The running time then obeys the recurrence T (n) = T (n − 1) + (n), and the number of comparisons we make in the worst case is $T (n) = \theta(n2).$

8-3

Sorting variable-length items
a. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is n. Show how to sort the array in O(n) time.
b. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. Show how to sort the strings in O(n) time.
(Note that the desired order here is the standard alphabetical order; for example, a < ab < b.)
a. The radix sort can be used to sort this problem. It would take d passes to sort the numbers in the array which will be equal to the number with highest number of digits. Suppose there m integers $m \leq n$ is always the case the worst case occurs when one integer has n/2 digits and remaining integers have 1 digit each. we assume the range of the single digit is constant. Therefore we would have d = n/2 and m = n/2+1 so the runnning time is $\theta(mn)$ = $\theta(n^2)$

If we assume the numbers will not have leading zeros and all the numbers are positive (if we have negative numbers we have sort them separately from positive numbers)then the number with more digits will always be greater than number with less digits. we can sort the numbers by the no of digits (using counting sort) and then sort each group of numbers with same length using radix sort. Each integer has i = 1..n digits let $m_i$ be the number of integers with i digits since there n digits we have $\sum_{i=1}^n i m_i$ = n.

It takes $O(n)$ to find the no of digits for all the numbers(divide the number 10 until it > 0 and base case for 0) and it will take O(m+n) = O(m) to group numbers with no of digits. To sort the group with $m_i$ number of integers with radix sort it will take $O(i . m_i)$. The time to sort the all groups is therefore $\sum_{i = 1}^n \theta(i . m_i)$ = $ \theta( \sum_{i = 1}^n i . m_i)$ = $\theta(n)$

b. One way to solve this problem is by a radix sort from right to left. Since the strings might have unequal lengths. we may have to pad all the strings smaller than largest string on the right side with character less than any other character. But the issue is we have to change the strings. Also the time required to sort will not run in the required time bound. In the worst case we have a string with n/2 characters and remaining n/2 string have one character. we have d = n/2 and m = n/2+1 the time required to sort using radix sort is $\theta(dm)$ = $\theta(n/2 (n/2+1))$ = $\theta(n^2)$.
we can sort the string based on the first character if the first character of string is lexicographically greater than first character other string then the length doesnt matter.We take advantage of this property and sort strings based on the first character using counting sort. We take empty string as special case and put it first. we gather all the string with same first letter as group.Then we recurse within each group with first letter removed. Running time: Lets count no of times each string is sorted by counting sort. Let $s_i$ be a string to be sorted has a length $l_i$. Then the no of times this string is sorted is $l_i+1$. (the +1 is for the string to be sorted as an empty string). ex. if we have to sort ab,a we need two pass in second pass we need to compare b with empty string for a.because of unequal no of characters. A call to counting sort for t string takes $\theta(t)$ time. The total time for all calls for counting sort is: $O( \sum_{i=1}^m l_i + 1 )$ = $O( \sum_{i=1}^m l_i + m )$
= $O( n + m )$ $m \leq n$

8-2

Suppose that we have an array of n data records to sort and that the key of each record has the value 0 or 1. An algorithm for sorting such a set of records might possess some subset of the following three desirable characteristics:
1. The algorithm runs in O(n) time.
2. The algorithm is stable.
3. The algorithm sorts in place, using no more than a constant amount of storage space in addition to the original array.
a. Give an algorithm that satisfies criteria 1 and 2 above.
b. Give an algorithm that satisfies criteria 1 and 3 above.
c. Give an algorithm that satisfies criteria 2 and 3 above.
d. Can you use any of your sorting algorithms from parts (a)–(c) as the sorting method used in line 2 of RADIX-SORT, so that RADIX-SORT sorts n records with b-bit keys in O(bn) time? Explain how or why not.
e. Suppose that the n records have keys in the range from 1 to k. Show how to modify counting sort so that it sorts the records in place in O(n+k) time. You may use O(k) storage outside the input array. Is your algorithm stable? (Hint: How would you do it for k = 3?)

a. Counting satisfies the both 1 and 2 since it is stable and runs in $\theta(n)$ time.

b. quick sort runs in O(n) if we have only two elements 0,1(repeated multiple times) because it would one pass to sort the elements if we pick 0 or 1 as the pivot.

c. Insertion sort sorts in place if you see lines 5 - 7 it will swap an element only of greater than key. But if it equal to the key it will stay in the same position.

d. yes we can any of the algorithms form a -c as the sorting if the key of each record is in the range 0 to 1. Since each of the intermediate sort runs in $\theta(n)$ time and we need to sort b bits which takes $\theta(bn)$. e. COUNTING-SORT-IN-PLACE(A,k)
let C[0..k] be a new array
for i = 1 to n
C[i] = 0
for i = i to A.length
C[A[i]] = C[A[i]]+1
for i = 1 to k
C[i] = C[i] + 1
i = A.length
while C[i] > 0 and i > 0
  if C[i] > C[i-1]
   A[C[i]] = i
   C[i] = C[i] -1
  else
   i = i-1
i = 0
while C[i] > 0
  A[C[i]] = i
  C[i] = C[i] -1
yes the above sort is stable.

8-1

8-1 Probabilistic lower bounds on comparison sorting In this problem, we prove a probabilistic \Omega(n lg n) lower bound on the running time of any deterministic or randomized comparison sort on n distinct input elements. We begin by examining a deterministic comparison sort A with decision tree TA. We assume that every permutation of A’s inputs is equally likely.
a. Suppose that each leaf of TA is labeled with the probability that it is reached given a random input. Prove that exactly n! leaves are labeled 1/n! and that the rest are labeled 0.
b. Let D(T) denote the external path length of a decision tree T ; that is, D(T) is the sum of the depths of all the leaves of T. Let T be a decision tree with k > 1 leaves, and let LT and RT be the left and right subtrees of T . Show that D(T) = D(LT) + D(RT) + k.
c. Let d(k) be the minimum value of D(T) over all decision trees T with k > 1 leaves. Show that $d(k) = min_{1 \leq i \leq k-1}{d(i)+ d(k - i) +k}.$ (Hint: Consider a decision tree T with k leaves that achieves the minimum. Let i0 be the number of leaves in LT and $k - i_0$ the number of leaves in RT.)
d. Prove that for a given value of k > 1 and i in the range 1 i k 1, the function i lg i + (k - i) lg(k - i) is minimized at i = k/2. Conclude that $d(k) = \Omega(k lg k)$.
e. Prove that $D(T_A) = \Omega(n! lg(n!))$, and conclude that the average-case time to sort n elements is $\Omega(n lg n)$.

a. since there n elements we have n! permutation of inputs being leaves of a decision tree. Each of leaf has a probability 1/n!. Since we have taken in to consideration all possible permutations there are no leaves hence the probability of other leaves is zero.

b. $ D(T) = \sum{l = 1^k}D(l)$
let x be the no of leaves on left sub tree
since the depth for each leaf from the left and right is 1 less than depth for the main tree
$$D(L(T)) = \sum_{l = 1}^ {x} (D(l) - 1 ) $$ $$D(R(T)) = \sum_{l = x+1}^{k} (D(l)- 1) $$ $$D(L(T))+D(R(T)) = \sum_{l = 1}^ {x} (D(l) - 1) + \sum_{l = x+1}^{k} (D(l)- 1)$$ $$D(L(T))+D(R(T)) = \sum_{l = 1}^k D(l) - \sum_{l = 1}^ {x} - \sum_{l = x+1}^{k}$$ $$D(L(T))+D(R(T)) = \sum_{l = 1}^k D(l) - x - (k -x)$$ $$D(L(T))+D(R(T)) = \sum_{l = 1}^k D(l) - x -k +x $$ $$D(L(T))+D(R(T)) = D(T) -k $$ $$D(T) = D(L(T))+D(R(T))+k$$ c. Needs more research. d. To find a where a minimum value we need to see the derivative of the function. $$f(i) = (i lg i + (k-i) lg(k-i))/ lg 2 $$ $$f'(i) = (lg i + 1 - log(k-i)-(k-i)/(k-i) )/ lg 2$$ $$f'(i) = (lg i + 1 - k log(k-i)-1)/ lg 2 $$ $$f'(i) = lg i - log(k-i) = 0 $$ the above equation is zero when i = k/2. To make sure above value is a minimum the second derivative of above should greater than 0. $$f''(i) = 1/i + 1 /k-i = 0 $$ $$f''(k/2) = 2/k + 2 / k = 0 $$ since k > 1 the above equation is greater than zero. Hence k/2 is minimum. we can use substitution method to solve the recursion. base case: $$f(k) = c k log k$$ $$f(1) = c 1 log 1 = 0$$ for base case when k = 1 $$f(1) \geq 0 $$ Similarly for inductive step $$f(i) = (i lg i + (k-i) lg(k-i)) $$ Since minimum for the equation occurs at k/2 we can use to find the lower bound for i = 1 to k -1 $$f(i) = min_{i=1 to k-1} (i lg i + (k-i) lg(k-i)+k) $$ $$f(k/2) = c (k/2 lg k/2 + (k-k/2) lg(k-k/2))+k$$ $$f(k/2) = c (k/2 lg k/2 + k/2 lg(k/2))+k $$ $$f(k/2) = c (k/2 lg k/2 + k/2 lg(k/2))+k$$ $$f(k/2) = c (k lg k/2 )+ k$$ $$f(k/2) = c (k lg k - log 2 k ) + k$$ $$f(k/2) = c (k lg k - k ) + k$$ $$f(k/2) = c (k lg k) - c k + k$$ $$f(k/2) = c (k lg k) - (c k - k)$$ c k - k > 0 if c > 1 then $f(k) =\Omega(k log k)$ e. since the tree has n! leaves substituting n! in eq below $$d(k) = \Omega(k log k)$$ $$d(n!) =D(T_A) = \Omega(n! log n!)$$ since n! permutations have an equal probability of 1/n!. The average case running time for n elements(one permutation. since there will be one permutation for an input). $$D(T_A) = \Omega(n! log n!)/n!$$ $$D(T_A) = \Omega( log n!)$$ $$D(T_A) = \Omega( n log n)$$ f. If we draw a randomized decision tree it will have all possible paths for different permutations of the input. since we are talking about average running time at each randomized node we need to pick smallest subtree(the tree with smallest average no of comparisons that will lead us to the leaf). We need to delete the other children of randomized node and consider the smallest subtree. This will work because this path worked for randomized sort already.The average number of comparisons for the modiÞed algorithm is no larger than the average number for the original randomized tree, since we discarded the higher-average subtrees in each case. In particular, each time we splice out a randomized node, we leave the overall average less than or equal to what it was, because
• the same set of input permutations reaches the modified subtree as before, but those inputs are handled in less than or equal to average time than before, and
• the rest of the tree is unmodified.

The randomized algorithm thus takes at least as much time on average as the corresponding deterministic one. (We’ve shown that the expected running time for a deterministic comparison sort is $\Omega(n lg n)$, hence the expected time for a randomized comparison sort is also $\Omega(n lg n)$

8.4-5

8.4-5 A probability distribution function P(x) for a random variable X is defined by P(x) = P(X \leq x). Suppose that we draw a list of n random variables X1,X2,...Xn from a continuous probability distribution function P that is computable in O(1) time. Give an algorithm that sorts these numbers in linear average-case time.

P(x) is defined as cumulative probability distribution. ex: P(3) = P(0)+P(1)+P(2)+P(3). It is defined as sum of probabilities. These are uniformly distributed(wikipedia). Even if we add all these probabilities they are $\leq $ 1. This meets Bucket sort assumption about input to be uniformly distributed and lies between (0,1]. We can use bucket sort to sort the list of cumulative probabilities. A small adjustment should be made to bucket sort so it can handle 1 as a input as well since it is the maximum value.

8.4-4

We are given n points in the unit circle, $p_i = (xi, yi) $, such that $0 \lt x^2+y^2 \leq 1$ for i = 1,2....n. Suppose that the points are uniformly distributed; that is, the probability of finding a point in any region of the circle is proportional to the area of that region. Design an algorithm with an average-case running time of $\theta(n)$ to sort the n points by their distances $di = \sqrt {x^2_i+y^2_i} $ from the origin. (Hint: Design the bucket sizes in BUCKET-SORT to reflect the uniform distribution of the points in the unit circle.)

For the points to be uniformly distributed we need to divide the Area of the circle in to n parts since we are given n points. The n points needs to be uniformly distributed in to the n parts. Since all the points are with in the limits $0 \lt x^2+y^2 \leq 1 $ the area of the square is $\pi 1^2 = \pi$ we can divide the circle in to n parts by using n concentric circles(circles with same center see mathworld for more details ).

We can use $di = \sqrt {x^2_i+y^2_i} $ to place a point in a bucket but calculating square root of a number will take $\theta( log n)$ time to compute and this needs to be done for n inputs which will give us $\theta(n log n)$. But we need $\theta(n)$ time complexity algorithm.Let $r_0,r_1,r_3....r_n$ be radii of the concentric circles. $r_0$ is circle with 0 radius it is the center of the concentric circles. A point will lie between radii to two adjacent concentric circles. find $r_1$ $$\pi (r_1)^2-(r_0 )^2 = \pi /n $$ $$\pi . r_1^2 = \pi /n $$ $$\ r_1 = \sqrt {1 /n} $$ find $r_2$ $$\pi (r_2)^2-(r_1 )^2 = \pi /n $$ $$\pi (r_2)^2 - (\sqrt {1 /n} )^2 = \pi /n $$ $$ (r_2)^2 = 1/n + 1 /n $$ $$r_2 = \sqrt{2/n} $$ through the induction we can find for the rest of radii $r_i = \sqrt{i/n}$ $$ r_i \leq \sqrt {x^2_i+y^2_i} \lt r_{i+1} $$ $$ r_i \leq \sqrt {x^2_i+y^2_i} $$ $$ r_i = \sqrt {x^2_i+y^2_i} $$ $$\sqrt{i/n} = \sqrt {x^2_i+y^2_i} $$ $$i/n = x^2_i+y^2_i$$ $$i = n(x^2_i+y^2_i)$$ we need to use $n(x^2_i+y^2_i)$ to find the bucket for a point and sort again using insertion sort.
let Point be data structure with x,y,d as variables
bucket-sort-points(Point [] points )
let B[0..n] be the new array
for i =0..n
make B an empty array
for i = 0..points.length
let $x = {points(x)^2+points(y)^2}$
insert point[i] into list $B[ \lfloor x n \rfloor]$
for i = 0..n
sort list B[i] using insertionsort
concatenate B[0] B[1]...B[n] together

8.4-3

8.4-3 Let X be a random variable that is equal to the number of heads in two flips of a fair coin. What is $E[X^2]$ ? What is $E^2[X] $?

Lets calculate $X^2$
we get HT,TH and HH possibilities where get at least one head
The probability of one head is 1/2
The probability of two heads is 1/4 since X is no of heads
$X^2 = 1^2 + 2^2 $
$E[X^2] = 1 . 1/2 + 4 . 1/4$
$E[X^2] = 1.5 $
What is $E^2[X] $?
$$ E[X] = 1. 1/2+2.1/4 $$ $$ E[X] = 1$$ $$ E[E[X] ] = E[1]$$ $$ E^2[X] ] = 1$$

8.4-2

Explain why the worst-case running time for bucket sort is $\theta(n^2)$. What simple change to the algorithm preserves its linear average-case running time and makes its worst-case running time $O(n lg n)$?

The bucket sort assumes the input distribution is uniformly distributed over $0 \leq n \lt 1$. But if the input is not unifornly distributed and if all elements fall in to a single bucket we will get n elements in a single bucket to sort n elements insertion sort needs $\theta(n^2)$. If we replace the sorting algorith by merge sort we will get $O(n log n )$ as the worst-case running time.

Bucket Sort Expected time

The Book skips small but important math during expansion for the square. Below step is transformed to $$ E[n_i^2] = E\Big[ {\Big( \sum_{j = 1}^n X_{ij} \Big)}^2 \Big] $$ $$ = E\Big[ {\Big( \sum_{j = 1}^n \sum_{k = 1}^n X_{ij} X_{ik} \Big)}^2 \Big] $$ expanding below by expanding summation $$ {\Big( \sum_{j = 1}^n X_{ij} \Big) }^2 $$ $$ \sum_{j = 1}^n X_{ij} . \sum_{j = 1}^n X_{ij} $$ $$ (X_{i1}+X_{i2}+X_{i3}+...+X_{in}) (X_{i1}+X_{i2}+X_{i3}+...+X_{in}) $$ multiplying above

$ X_{i1}. X_{i1}+X_{i1} . X{i2}+....+X_{i1}.X_{in} + $
$ X_{i2}. X_{i1}+X_{i2} . X{i2}+....+X_{i2}.X_{in} + $ . . . $ X_{in}. X_{i1}+X_{in} . X{i2}+....+X_{in}.X_{in} + $

we can group all elements with equal subscripts

$ X_{i1}. X_{i1}+X_{i2} . X{i2}+....+X_{in}.X_{in} + $
$ X_{i1}. X_{i2}+X_{i1} . X{i3}+....+X_{i1}.X_{in} + .... $
The first part can be written as $$ \sum_{j = 1} ^ n X_{ij} $$ The second part can be written as $$ \sum_{j = 1} ^ n \sum_{k = 1} ^ n X_{ij} X_{ik} $$ together we can write as $$ \sum_{j = 1} ^ n X_{ij} + \sum_{j = 1} ^ n \sum_{k = 1} ^ n X_{ij} X_{ik} $$

8.3-5

8.3-5 In the first card-sorting algorithm in this section, exactly how many sorting passes are needed to sort d-digit decimal numbers in the worst case? How many piles of cards would an operator need to keep track of in the worst case?

Let recall the procedure from the book. Intuitively, you might sort numbers on their most significant digit, sort each of the resulting bins recursively, and then combine the decks in order. Unfortunately, since the cards in 9 of the 10 bins must be put aside to sort each of the bins, this procedure generates many intermediate piles of cards that you would have to keep track of.

If you see from the above the algorithm will a intermediate sort like counting sort which require $\theta(n+k)$ (we need to sort n cards since k is 10 for decimal numbers(0-9) ) and each of the buckets needs to be recursively solved. In the worst case each bucket on solving will create a new bucket with n values this will happen when we have all equal values (ex: let d =3 and n =3 123,123,123). we need to solve d buckets recursively the worst case running time is $\theta(d(n+10))$. The opertaer need to keep track of nd cards. Since each bin will have n cards if you recursively solve we get a new bin with n cards and this repeats for every digit. Since there are d digits and we have n cards the no of cards is nd.

8.3-4

8.3-4 Show how to sort n integers in the range $0 to n^3 -1$ in $O(n)$ time.


Let n = 10 be the no of integers to be sorted and to represent $n^3 -1$ integers we need 3 digits (ex: 0 -999 needs three digits).Each of the three digits can be represented by 0 to n-1 numbers.

The running time for radix sort is $\theta(d(n+k))$

d = 3 and k = n (0 to n-1 digits)

we have repeat the intermediate sort 3 times for 3 digits

$\theta(3(n+n))$ = $\theta(6n)$ = $\theta(n)$

the constant is absorbed by $\theta(n)$

8.3-3

8.3-3 Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?

Let us assume the sorting works for 1 to d-1 digits if it works for d-1 digits it works for d digits. let $a_d$ and $b_d$ be two digits to be sorted.

If $a_d > b_d$ then the algorithm places $a_d$ ahead of $b_d$ regardless of its lower order digits.

If $a_d < b_d$ then the algorithm places a_d after $b_d$ regardless of its lower order digits.

If $a_d = b_d$ then the algorithm leaves the elements in the same order they were in because it is stable. If d digits are equal the two numbers already sorted for d-1 digits and now for d- digit. If the all the digits are equal for two numbers if the intermediate sort is not stable then for the third case it will not leave the elements in the order same as the input.

8.3-2

8.3-2 Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?
insertion sort is stable because the comparison in the inner while will move elements to right only when they greater than key. if they are equal they dont move to right.

merge sort is stable the comparison in the merge compare L and R array only check if L is less than R . If it is equal it uses the element from L array which is in order with the input.

heap sort is not stable sort because the comparison is between left and right child and picks the greatest element. ex: 5 3 3 4. element 3 is not inserted in the correct order.

quick sort is not stable because we random procedure to get balanced split which can easily pick an similar element in the beginning and make it pivot element.

Give a simple scheme that makes any sorting algorithm stable.How much additional time and space does your scheme entail?

All we need to make sure is save the inserted order in another array and use it to break the tie for similar element values. we need to store indices from 1 to n each will need log n space(since an element has to written in the form 2^x and x will be no of bits ex: 8 needs 3 bits) we pick log n based on the maximum number. All the elements need $\theta(n log n)$ space.
Additional time: the worst case occurs when all elements are same and we need compare indices for every element. But the comparison occurs in constant time.

8.3-1

8.3-1 Using Figure 8.3 as a model, illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX. first sort on the LSB and till MSB to make a valid word. In the sense don't sort only LSB but also the whole word.If you only sort the letter the final output will be an invalid word. Ex: COW SEA SEA DOG DOG COW SEA COW DOG

8.2-4

8.2-4 Describe an algorithm that, given n integers in the range 0 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range $[a..b]$ in $O(1)$ time. Your algorithm should use $\theta(n + k)$ preprocessing time.
We can calculate array C as in counting sort it would take $\theta(n+k)$ to find the no of elements
If a-1 = 0
return c[b]
else
c[b] - c[a-1]
we cannot subtract c[b] and c[a] because we will loose occurrence of c[a](if their is one)

8.2-3

8.2-3
Suppose that we were to rewrite the for loop header in line 10 of the COUNTINGSORT as
10 for j = 1 to A.length
Show that the algorithm still works properly. Is the modified algorithm stable?
The algorithm would still work because we are changing only the order in which the element are processed (they were processed in reverse order earlier). The only thing that changes is the similar value elements are not processed in the same order as the input. So the algorithm works but the algorithm is not stable because of the above reason.

8.2-2

Prove that COUNTING-SORT is stable. COUNTING-SORT is stable because the lines 10 -12 picks the last occurrence of the same value and inserts in the last possible place. All future occurrences will be inserted in front of the last occurrence.

8.1-4

Suppose that you are given a sequence of n elements to sort. The input sequence consists of n/k subsequences, each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length n is to sort the k elements in each of the n/k subsequences. Show an $ \Omega(n lg k)$ lower bound on the number of comparisons needed to solve this variant of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)
let $h_k$ be height of the subtree tree of k elements and l be the reachable leaves $$k! \leq l \leq 2^h $$ applying log on both sides $$ log k! \leq log 2^h_k $$ $$ log k! \leq h_k $$ The above height is one sub tree we have n/k subsequences. Add n / k subsequences of log k! height. $$ n/k log k! \leq h $$ since log k can be written as k log k as per stirlings approximation or bounding it using integrals $$ n/k . k log k \leq h $$ $$ n log k \leq h $$ since h is no of comparisons as well as height as per lower bound for worst case on pg 193 $$ h = \Omega(n log k) $$

8.1-3

Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length n. What about a fraction of $1/n$ of the inputs of length n? What about a fraction $1/2^n$?
using the formula from theorem 8.1
$$n! \leq l \leq 2^h$$ $$ n!/2 \leq n! \leq l \leq 2^h$$ taking logs on both sides $$ log (n!/2) \leq log (2^h)$$ $$ log (n!) - log 2 \leq log (2^h)$$ $$ log (n!) - 1 \leq log (2^h)$$ $$ log (n!) - 1 \leq h $$ $$ log (n!) - 1 \leq log(n!) \leq h $$ $$log(n!) \leq h $$ $$log(n!) = h $$ $$ \Omega(n log(n)) = h $$ b)fraction of $1/n$ of the inputs of length n?
$$ n!/n \leq n! \leq l \leq 2^h$$ $$ n!/n \leq 2^h$$ taking logs on both sides $$ log (n!/n) \leq log 2^h$$ $$ log n! - log n \leq h$$ $$ log n! - log n \leq h$$ c.What about a fraction $1/2^n$ $$ n!/2^n \leq n! \leq l \leq 2^h$$ taking log on both sides $$ log n!/2^n \leq log 2^h $$ $$ log n!/2^n \leq h $$ $$ log n! - log 2^n \leq h $$ $$ log n! - n \leq h $$

8.1-2

Obtain asymptotically tight bounds on lg(n!) without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k = 1}^n lg k$ using techniques from Section A.2.

$$lg n!$$ $$lg (n+n-1+..1)$$ $$log n + log (n-1)+...+1$$ above can be written as summation $$\sum_{k = 1}^n lg k$$ lg k is monotonically increasing function and can be bounded by integrals $$ \int_{0}^n log k \leq \sum_{k = 1}^n lg k$$ $$ [k (log k-1)+ck ]_{0}^n \leq \sum_{k = 1}^n lg k$$ $$ [n (log n-1)+cn +0 ] \leq \sum_{k = 1}^n lg k$$ $$ n log n- n + cn \leq \sum_{k = 1}^n lg k$$ $$ \leq n log n $$ $$ = n log n $$

8.1-1

What is the smallest possible depth of a leaf in a decision tree for a comparison sort?
n-1 if n is the no of elements. It happens when the input is already in sorted order. we compare element from 1 to n and tree follows the leftmost path in the decision tree.

7-6