7-5

7-5 Median-of-3 partition
One way to improve the RANDOMIZED-QUICKSORT procedure is to partition around a pivot that is chosen more carefully than by picking a random element from the subarray. One common approach is the median-of-3 method: choose the pivot as the median (middle element) of a set of 3 elements randomly selected from the subarray. (See Exercise 7.4-6.) For this problem, let us assume that the elements in the input array A[1..n] are distinct and that $n \geq 3$. We denote the
sorted output array by A[1..n] . Using the median-of-3 method to choose the pivot element x, define pi = Pr{x=A'[i]}
a. Give an exact formula for $p_i$ as a function of n and i for i = 2,3,...,n-1. (Note that $p_1 = p_n = 0$.)
b. By what amount have we increased the likelihood of choosing the pivot as x = $A'\big[\lfloor(n+1/2\rfloor\big]$ , the median of A[1..n] , compared with the ordinary implementation? Assume that $n \rightarrow \infty$, and give the limiting ratio of these probabilities.
c. If we define a “good” split to mean choosing the pivot as x = A[i] , where $n/3 \leq i \leq 2n/3$, by what amount have we increased the likelihood of getting a good split compared with the ordinary implementation? (Hint: Approximate the sum by an integral.)
d. Argue that in the $\Omega(n lg n)$ running time of quicksort, the median-of-3 method affects only the constant factor.
a. The probability of choosing a pivot element x, pi = Pr{x=A'[i]} depends picking three elements and one of two elements should be less than pivot element and one element should be greater than pivot. pi = Pr{ probability of choosing three elements from set n and one of two elements should be less than pivot and one of the element should be greater than pivot} since these are independent events pi = Pr{ probability of choosing three elements from set n} Pr{one of two elements should be less than pivot} Pr{one of the element should be greater than pivot} $$p_i = \frac{3}{n} \frac{2 . (i-1)}{n-1} \frac{n-i}{n-2} $$ $$p_i = \frac{6 . (i-1)(n-i)}{n . (n-1) . (n-2)} $$ b. The probability will remain same for in both cases while chossing $A'\big[\lfloor(n+1/2\rfloor\big]$ because all elements have equal chance. subsitute $\frac{(n+1)}{2}$ for i ignoring floor conditions $$p_i= \frac{6 . (i-1)(n-i)}{n . (n-1) . (n-2)}$$ $$p_{\frac{(n+1)}{2}}= \frac{6 . (\frac{(n+1)}{2}-1)(n-\frac{(n+1)}{2}}{n . (n-1) . (n-2)}$$ $$p_{\frac{(n+1)}{2}}= \frac{6 . (\frac{(n-1)}{2})(\frac{(n-1)}{2}}{n . (n-1) . (n-2)}$$ $$p_{\frac{(n+1)}{2}}= \frac{3 . (n-1)}{2 n . (n-2)}$$ Lets take ratio of improved method with original method. The original has a probability of 1/n taking ratio of probability and $n \rightarrow \infty$ $$p_{\frac{(n+1)}{2}}= \lim_{n \rightarrow \infty} \frac{ \frac{3 . (n-1)}{2 n . (n-2)}}{\frac{1}{n}}$$ $$p_{\frac{(n+1)}{2}}= \lim_{n \rightarrow \infty} \frac{3 . (n-1)}{2 . (n-2)}$$ $$p_{\frac{(n+1)}{2}}= \lim_{n \rightarrow \infty} \frac{3 . (1-\frac{1}{n})}{2 . (1-\frac{2}{n})}$$ $$p_{\frac{(n+1)}{2}}= \frac{3}{2}$$ we have increased the chance of selecting by 50 %(3/2-1).
c. The probability of selecting a value between $n/3$ and $2n/3$ for original method is $(2n/3-n/3)/n $ = $1/3$ The probability of selecting an element between $n/3$ and $2n/3$ for median of 3 method is $$p_i = \sum_{i = \frac{n}{3}}^{\frac{2n}{3}} \frac{6 . (i-1)(n-i)}{n . (n-1) . (n-2)} $$ using approximation by integrals $$p_i = \int_{\frac{n}{3}}^{\frac{2n}{3}} \frac{6 . (i-1)(n-i)}{n . (n-1) . (n-2)} $$ $$p_i = \frac{6 }{n . (n-1) . (n-2)} \int_{\frac{n}{3}}^{\frac{2n}{3}} (i-1)(n-i) $$ $$p_i = \frac{6 }{n . (n-1) . (n-2)} \int_{\frac{n}{3}}^{\frac{2n}{3}} -i^2+(n+1)i-n $$ $$p_i = \frac{6 }{n . (n-1) . (n-2)} \Big[-\frac{i^3}{3}+(n+1)\frac{i^2}{2}-n i \Big]_{\frac{n}{3}}^{\frac{2n}{3}} $$ substituting the limits in the above equation and solving gives $$\frac{13 n ^2 -27n}{27n^2-81n+54}$$ when $n \rightarrow \infty$ $$\lim_{n \rightarrow \infty}\frac{13 -27/n}{27-81/n+54/n^2}$$ $$\frac{13}{27}$$ If we take teh ratio of improved method with the orginal method we get $$\frac{13}{27} \frac{1}{3}$$ $$\frac{13}{9}$$ = 1.44 Thus we increased the chance of choosing median by 44 %.
d.The best case occurs for the original method when we partition in to two subarrays of sizes n/2 and n/2. $$T(n) = 2T(n/2)+\theta(n)$$ Even if we use the median of 3 method(will add little extra time in finding the median) running time will be $\Omega(n log n)$ because we are only improving the probability of finding the median but not the running time.

7-4

The QUICKSORT algorithm of Section 7.1 contains two recursive calls to itself. After QUICKSORT calls PARTITION, it recursively sorts the left subarray and then it recursively sorts the right subarray. The second recursive call in QUICKSORT is not really necessary; we can avoid it by using an iterative control structure. This technique, called tail recursion, is provided automatically by good compilers. Consider the following version of quicksort, which simulates tail recursion: TAIL-RECURSIVE-QUICKSORT(A, p, r)
1 while p < r
2 // Partition and sort left subarray.
3 q = PARTITION(A, p, r)
4 TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
5 p = q + 1
a. Argue that TAIL-RECURSIVE-QUICKSORT(A, 1,A:length) correctly sorts the array A.
Compilers usually execute recursive procedures by using a stack that contains pertinent information, including the parameter values, for each recursive call. The information for the most recent call is at the top of the stack, and the information for the initial call is at the bottom. Upon calling a procedure, its information is pushed onto the stack; when it terminates, its information is popped. Since we assume that array parameters are represented by pointers, the information for each procedure call on the stack requires O(1) stack space. The stack depth is the maximum amount of stack space used at any time during a computation.
b. Describe a scenario in which TAIL-RECURSIVE-QUICKSORT’s stack depth is $\theta(n)$ on an n-element input array. c. Modify the code for TAIL-RECURSIVE-QUICKSORT so that the worst-case stack depth is $\theta(lg n)$. Maintain the O(n lg n) expected running time of the algorithm.
a. TAIL-RECURSIVE-QUICKSORT performs same operations as QUICK-SORT. Quicksort calls itself recursively with A,p,q-1 and A,q+1,r arguments. TAIL-RECURSIVE-QUICKSORT does the same calls as well. It intially recursively calls it self with A,p,q-1 later it sets p value to q+1 and using the while it calls it does same operations as calling it self with A,q+1,r arguments.
b.TAIL-RECURSIVE-QUICKSORT will have a stack of depth $\theta(n)$ when calls to PARTITION return a q value of r(q=r).This happens when we an already sorted array. Below are sequence of calls:
TAIL-RECURSIVE-QUICKSORT(A,p,n)
TAIL-RECURSIVE-QUICKSORT(A,p,n-1)
TAIL-RECURSIVE-QUICKSORT(A,p,n-2)
.
.
.
TAIL-RECURSIVE-QUICKSORT(A,p,1)
c. The TAIL-RECURSIVE-QUICKSORT can be modified as below.
TAIL-RECURSIVE-QUICKSORT(A,p,r)
q = PARTITION(A,p,r)
if q-p < r-q
TAIL-RECURSIVE-QUICKSORT'(A,p,q-1)
r = q+1
else
TAIL-RECURSIVE-QUICKSORT'(A,q+1,r)
r = q-1
TAIL-RECURSIVE-QUICKSORT'(A,p,r)
if you see in b TAIL-RECURSIVE-QUICKSORT will push more recursive call to stack if the size of the first partition is large. At a time you will $\theta(n)$ calls on the stack. we can eliminate this by using the modified procedure which calls the TAIL-RECURSIVE-QUICKSORT' for small partition. The best case scenario we will have array with equal sizes of n/2. This will occupy stake depth of $\theta(log n)$ using recursion
$$S(n) = 2 S(n/2)$$ this master theorem case 1 which $\theta(log n)$.
This will change the running time since we only changed the order of processing the algorithm hence the expected running time is $O(n log n)$.

7-3

7-3 Alternative quicksort analysis
An alternative analysis of the running time of randomized quicksort focuses on the expected running time of each individual recursive call to RANDOMIZEDQUICKSORT, rather than on the number of comparisons performed.
a. Argue that, given an array of size n, the probability that any particular element is chosen as the pivot is 1/n. Use this to define indicator random variables Xi = I {i th smallest element is chosen as the pivot}. What is E[Xi] ? b. Let T .n/ be a random variable denoting the running time of quicksort on an array of size n. Argue that
$$E[T(n)] =E\Big[\sum_{q=1}^n X_q (T(q-1)+T(n-q)+\theta(n))\Big]$$ c. Show that we can rewrite equation (7.5) as
$$E[T(n)] = 2/n \sum_{q=2}^{n-1} E[T(q)]+\theta(n)$$ d. Show that
$$\sum_{k=2}^{n-1} k lg k \leq 1/2 n^2 lgn - 1/8 n^2$$ (Hint: Split the summation into two parts, one for k = 2,3,...,$\lceil n/2\rceil$-1 and one for $k = \lceil n/2\rceil,...,n-1.$)
e. Using the bound from equation (7.7), show that the recurrence in equation (7.6) has the solution E[T(n)] =\theta(n lg n). (Hint: Show, by substitution, that $E[T(n)] \leq an lg n$ for sufficiently large n and for some positive constant a.)
a. To choose an element from n elements we know the probability is 1/n. Since each element has a equal probability of getting picked.
if we define a random variable Xi = I {i th smallest element is chosen as the pivot}
But for the element to be ith smallest we need pick the element from n elements. we need consider this as well. so $E[X_i] = \sum_{j=1}^{n} Pr\{select an element j and j is ith smallest element\}$ the event mentioned above are independent. Hence for independent events $$A \cap B = A . B$$ $$E[X_i] = \sum_{j=1}^{n} Pr\{select an element j\} Pr\{j is ith smallest element\}$$ $$E[X_i] = \sum_{j=1}^{n} 1/n 1/n $$ $$E[X_i] = 1/n $$ b. The running time of quick sort on a array of size n is dependent on the size of sub-arrays. The subarray size is dependent of probability of picking a pivot element. We can sum size of subarrays resulting from all possible pivots multiplied by the probability of pivot. $$E[T(n)] = E \big[ \sum_{q=1}^n X_q (T(q-1)+T(n-q)+\theta(n)) \big]$$ we need add size subarray and $\theta (n)$ because it is the time taken for partitioning the array.
c. $$E(T(n)) = E \big[ \sum_{q=1}^n X_q (T(q-1)+T(n-q)+\theta(n)) \big]$$ using linearity of expectation $$E(T(n)) = \sum_{q=1}^n E[X_q] (T(q-1)+T(n-q)+\theta(n)) $$ since E[X_q] is 1/n from a. $$E(T(n)) = \sum_{q=1}^n 1/n (T(q-1)+T(n-q)+\theta(n)) $$ $$E(T(n)) = 1/n (\sum_{q=1}^n T(q-1)+ \sum_{q=1}^n T(n-q)+\sum_{q=1}^n \theta(n)) $$ $$E(T(n)) = 1/n (E[T(0)]+E[T(1)]+..E[T(n-1)]+E[T(n-1)]+..+E[T(1)]+E[T(0)]+ n .\theta(n)) $$ $$E(T(n)) = 1/n (E[T(2)]+..E[T(n-1)]+E[T(n-1)]+..+E[T(2)]+ n .\theta(n)) $$ since T(0) and T(1) is $\theta(1)$ $$E(T(n)) = 1/n ( 2(E[T(2)]+..E[T(n-1)])+ n .\theta(n)) $$ $$E(T(n)) = 1/n ( 2 \sum_{q=2}^{n-1} E[T(q)] )+ n. 1/n .\theta(n)) $$ $$E(T(n)) = 2/n \sum_{q=2}^{n-1} E[T(q)] + \theta(n)) $$ d. $$\sum_{k=2}^{n-1} k log k \leq 1/2 n ^2 lg n -1/8 n ^2$$ $$=\sum_{k=2}^{\lceil n/2 - 1 \rceil} k log k + \sum_{k= \lceil n/2 \rceil }^{n-1} k log k $$ $$\leq \sum_{k=2}^{\lceil n/2 - 1 \rceil} k log n/2 + \sum_{k= \lceil n/2 \rceil }^{n-1} k log n $$ $$\leq log n/2 \sum_{k=2}^{\lceil n/2 - 1 \rceil} k + log n \sum_{k= \lceil n/2 \rceil }^{n-1} k $$ $$= log \frac {n}{2}( \frac {(n/2-1).n/2 } {2} -1 )+ log n (\frac{n .(n-1)} {2} - \frac {(n/2-1).n/2 } {2}) $$ $$\leq log \frac {n}{2} \frac {(n/2).(n/2) } {2} + log n (\frac{n.n}{2} - \frac {(n/2).n/2 } {2}) $$ $$= log n \frac {(n^2)} {8} - log 2 \frac {(n^2)} {8} + log n \frac{\frac{n}{2} \frac{n}{2}}{2} - \frac {(n/2).n/2 } {2} $$ $$= log n \frac {(n^2)} {8} - \frac {(n^2)} {8} + log n \frac{ n^2}{2} - log n \frac {n^2} {8} $$ $$= - \frac {(n^2)} {8} + log n \frac{ n^2}{2} $$ e. $$E(T(n)) = 2/n \sum_{q=2}^{n-1} E[T(q)] + \theta(n)) $$ lets use substituion method and assume E[T(q)] = c q log q over q = 2 to n-1 $$E(T(n)) = 2/n \sum_{q=2}^{n-1} c q log q + \theta(n)) $$ from equation 7.7 $$E(T(n)) = 2/n c (log n \frac{ n^2}{2}- \frac {(n^2)} {8} ) + \theta(n)) $$ $$E(T(n)) = 2c (log n \frac{n}{2} - \frac {(n)} {8} ) + \theta(n)) $$ $$E(T(n)) = c n log n - c \frac {(n)} {4} ) + k n $$ $n \geq 4k$ $$E(T(n)) \leq c n log n $$

7-2

Quicksort with equal element values
The analysis of the expected running time of randomized quicksort in Section 7.4.2 assumes that all element values are distinct. In this problem, we examine what happens when they are not.
a. Suppose that all element values are equal. What would be randomized quicksort’s running time in this case?
b. The PARTITION procedure returns an index q such that each element of A[p..q-1] is less than or equal to A[q] and each element of A[q+1..r] is greater than A[q] . Modify the PARTITION procedure to produce a procedure PARTITION(A, p, r), which permutes the elements of A[p..r] and returns two indices q and t, where p q t r, such that
all elements of A[q..t] are equal,
each element of A[p..q -1] is less than A[q] , and
each element of A[t+1..r] is greater than A[q] .
Like PARTITION, your PARTITION' procedure should take $\theta(r-p)$ time.
c. Modify the RANDOMIZED-QUICKSORT procedure to call PARTITION', and name the new procedure RANDOMIZED-QUICKSORT'. Then modify the QUICKSORT procedure to produce a procedure QUICKSORT'(p, r) that calls RANDOMIZED-PARTITION' and recurses only on partitions of elements not known to be equal to each other.
d. Using QUICKSORT', how would you adjust the analysis in Section 7.4.2 to avoid the assumption that all elements are distinct?
a. The running will be $\theta(n^2)$.Similar to quick sort because RANDOM will get a same pivot element as A[r] since all the elements are similar and this would provide unbalanced split of n-1 and 0 elements. The running time for n-1 and 0 elements is $\theta(n^2)$
b. PARTITION'(A,p,r,q,t)
i = p-1
j = p
x = A[r]
k = p-1
for j = p to r-1
  if A[j] $\leq$ x
  i = i+1
   if A[i] = x
   k = k-1
  swap A[i] and A[j]
   if A[j] == x
   k = k+1
   swap A[k+i] and A[j]
Exchange A[k+1+i] and A[q]
q = i+1
t = k+1+i
c. QUICKSORT(A,p,r)
if p < r
RADOMIZED-QUICKSORT(A,p,r,q,t)
QUICKSORT(A,p,q-1)
QUICKSORT(A,t+1,r)
RADOMIZED-QUICKSORT(A,p,r)
i = Random(p,r)
swap A[i] and A[r]
PARTITION'(A,p,r)
d.Needs more research.

7-1

Hoare partition correctness
The version of PARTITION given in this chapter is not the original partitioning algorithm. Here is the original partition algorithm, which is due to C. A. R. Hoare:
HOARE-PARTITION(A, p, r)
1 x = A[p]
2 i = p-1
3 j = r + 1
4 while TRUE
5 repeat
6 j = j-1
7 until A[j] $ \leq$ x
8 repeat
9 i = i - 1
10 until A[E] $\geq$ x
11 if i < j
12 exchange A[i] with A[j]
13 else return j
a. Demonstrate the operation of HOARE-PARTITION on the array A {13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21}, showing the values of the array and auxiliary values after each iteration of the while loop in lines 4–13
The next three questions ask you to give a careful argument that the procedure HOARE-PARTITION is correct. Assuming that the subarray A[p .. r] contains at least two elements, prove the following:
b. The indices i and j are such that we never access an element of A outside the subarray A[p . . r] .
c. When HOARE-PARTITION terminates, it returns a value j such that $p \leq j < r$.
d. Every element of A[p .. j] is less than or equal to every element of A[j+1.. r] when HOARE-PARTITION terminates.
The PARTITION procedure in Section 7.1 separates the pivot value (originally in AOEr ) from the two partitions it forms. The HOARE-PARTITION procedure, on the other hand, always places the pivot value (originally in AOEp ) into one of the two partitions A[p..j] and A[j+1..r] . Since $p \leq j < r$, this split is always nontrivial.
e. Rewrite the QUICKSORT procedure to use HOARE-PARTITION.

a. Its important to understand until in the algorithm to solve this. Until means you have to do the opposite comparison if you write an actual program. so for $\leq$ we have to use $\gt$ and for $\leq$ we have to use $\gt$. We need use this while solving a.
for the first iteration x = 13 j =12
a[12] = 21 > 13
j = 11
since a[11] = 6 > 13 (false)
i = 1
a[1] = 13 < 13 (false)
swap a[1] and a[12]
the array will be A {6, 19, 9,5, 12, 8, 7, 4, 11, 2,13 , 21} for second iteration (i = 1 and j = 11):
j = 10
a[10] = 2 > 13 (false)
i = 2
a[2] = 19 < 13 (false)
swap a[2] and a[10]
the array will be A {6, 2, 9,5, 12, 8, 7, 4, 11, 19,13 , 21}
for third iteration(i = 2 and j = 10):
j = 9 a[9] = 11 > 13(false)
i = 3
a[3] = 9 < 13
i = 4
a[4] = 5 < 13
i = 5
a[5] = 12 < 13
i = 6
a[6] = 8 < 13
i = 7
a[7] = 7 < 13
i =8
a[8] = 4 < 13
i = 9
a[9] = 11 < 13
i = 10
a[10] = 2 < 13
i = 11
a[11] = 19 < 13 (false)
since i > j the loop will be terminated and we return j = 9.
b. we never access any element outside the Subaaray A[p..r] because we begin with j = j -1 and decremented before accessing any element outside r. similarly we begin with i = p -1 and increment it before any element outside p and the loop terminates when i > j so i will not go past r.
At the begging k =1 i = p and $p \leq j \leq r$. At k > 1 iteration $p \leq i \leq j \lt r$ . At k+1 iteration $p \leq i \lt i' \lt j' \leq j \lt r$. If the loop terminates at k th iteration we have $p \leq i \leq i' \leq j' \leq j \lt r$. So no element outside A[p..r] will be accessed.

k = 1
i					j
p	.	.	.	.	q
k > 1(k iteration)
	i			j
p	.	.	.	.	q
k+1 iteration
	i	i'	j'
p	.	.	.	.	q

c. from above we can prove $p \leq j \lt r$.
d. After kth iteration the elements A[p..i] $\leq$ x and the elements A[j..r] $\geq$ x. After the while loop termination all the elements A[p..j] will be less than or equal to A[j+1..r].
e. We cannot use the same logic as in PARTITION AND QUICK-SORT and HOARE-PARTITION and QUICK-SORT because in PARTITION and QUICK-SORT the pivot is in fixed position and we don't use pivot in the next iteration as we know all the elements to left of pivot are less than pivot and all elements to right are greater than pivot. IN HOARE-PARTITION the algorithm uses pivot for comparison but we don't get the similar sub array as in PARTITION and QUICK-SORT.
QUICKSORT(A,p,r)
if(p q = HOARE-PARITION(A,p,r)
QUICKSORT(A,p,q)
QUICKSORT(A,q+1,r)

7.4-6

Consider modifying the PARTITION procedure by randomly picking three elements from array A and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst an $\alpha-to(1 -\alpha)$ split, as a function of ˛ in the range $0 < \alpha < 1.$

Let A (resp, B, C) denote the subset of elements in the positions range $[0, \alpha n)$ (resp. $[ \alpha n, n- \alpha n]$,$(n - \alpha n, n])$,
We analyze the possible cases in which the median gives a valid (i.e. $ \alpha -to-(1 - \alpha )$) partition and calculate their respective probabilities.
Pr[One element from each of A,B and C] = $3! . \alpha^ 2(1 - 2 \alpha )$
Pr[One element from A, and two elements from B] = $(3/2) \alpha (1 - 2 \alpha)^2$
Pr[One element from C and two elements from B] = $(3/2) \alpha (1 - 2 \alpha)^2$
Pr[All three elements from B] = $(1 - 2 \alpha )^3$
The probability of a valid partition is just the sum of the above terms.

7.4-5

We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is “nearly” sorted. Upon calling quicksort on a subarray with fewer than k elements, let it simply return without sorting the subarray. After the top-level call to quicksort returns, run insertion sort on the entire array to finish the sorting process. Argue that this sorting algorithm runs in $O(nk + n lg n/ k)$ expected time. How should we pick k, both in theory and in practice? Quick-sort should run until we have k elements. $$n/2^i = k $$ Applying log $$i = log n/k $$ the height of the tree is $log n/k$ The time partition procedure runs is $O(n)$ and for a height of log n/k the running time for quick sort is $O(n log n/k)$ Now we have n/k sub arrays with each k unsorted elements the time for insertion sort is $$O(n/k . k^2)$$ $$O(n.k)$$ The expected running time is $O(nk + n lg n/ k)$. We should pick k as log n so the running time is n log n which is the best expected running time. In practice we pick k such that its values is around log n and provides better performance than quick-sort.

7.4-4

Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n lg n)$. The expected running time of Randomized-QUICKSORT is $$E[X] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} 2/j-i+1 $$ $$E[X] = \sum_{i=1}^{n-1} \sum_{k=2}^{n-i+1} 2/k $$ $$E[X] = \sum_{i=1}^{n-1} \sum_{k=2}^{n-i+1} 2/k $$ using approximation by integration (Appendix A)(sum can be bounded by integrals)(monotonically decreasing series) $$E[X] \geq \sum_{i=1}^{n-1} 2 \int_{k=2}^{n-i+2} 1/k $$ $$E[X] = \sum_{i=1}^{n-1} 2 ( ln(n-i+2)-ln2) $$ $$E[X] = \sum_{i=1}^{n-1} 2 (ln(n-i+2)-ln2) $$ $$E[X] = 2(ln(n+1)+ln n + ln(n-1) +..+ ln 3 )- ln2(n(n-1)) $$ $$E[X] \geq 2 (ln(n)+ ln n + ln(n-2)+...+ln 2 + ln 1) - ln2 (n(n-1))$$ $$E[X] \geq 2 (ln n!) - ln2 (n(n-1))$$ $$E[X] = \Omega(n log n)$$

7.4-3

Show that the expression q^2 + (n -q -1)^2 achieves a maximum over q = 0. 1... n - 1 when q = 0 or q = n 1. $$F(n) = q^2 + (n -q -1)^2$$ if we take derivative $$F'(n) = 2q -2 (n -q -1)$$ $$ 2q -2 (n -q -1) = 0$$ $$ 2q = 2 (n -q -1) $$ $$ 2q = (n -1) $$ $$ q = (n -1)/2 $$ the above value can be max or min depending on second derivate.Take second derivative F'(n) $$F''(n) = 2 +2 $$ $$F''(n) = 4 $$ second derivative is positive it means this is a minimum value. If we graph above equation it will be a downward-convex. The maximum for a downward convex occurs at its endpoints and minimum at its middle.

7.4-2

Show that quicksort’s best-case running time is $\Omega(n lg n)$.
for best case we need to have at least element to left side of the tree.(see CLRS about the ratio q and 1-q)
$$T(n) = min_{1 \leq q \leq n-1} (T(q)+T(n-q-1))+\theta(n)$$ lets use substitution method. lets assume $T(n) \geq c n lg n $ $$T(n) = min_{1 \leq q \leq n-1} (c q log q+ c (n-q-1) log(n-q-1))+\theta(n)$$ to find maximum and minimum we need to use calculus. Refer
http://www.youtube.com/watch?v=tBBJ2TSTa1Q
http://www.1728.org/minmax.htm
If the second derivative is positive q ln q+ (n-q-1) ln(n-q-1)/ln we get a minimum value:
$$f(n) = q ln q+ (n-q-1) ln(n-q-1)/ln 2$$ $$f'(n) = ln q+ 1- ln(n-q-1)-1/ln 2$$ $$f'(n) = ln q - ln(n-q-1)/ln 2$$ slope is zero at minimum
ln q - ln(n-q-1) = 0
q = n-1/2
Now we need to see if the second derivative is positive $$f''(n) = 1/q + 1/(n-q-1)/ln 2$$ lets substitute q = (n-1)/2 $$f''(n) = 2/(n-1) + 1/(n-((n-1)/2)-1)/ln 2$$ $$f''(n) = (4/n-1)/ln 2$$ if $n \geq 2$ then above equation is always postive hence the minimum value occurs when q = (n-1)/2 substituting q value in eq at the top. $$T(n) = (c (n-1)/2 log (n-1/2)+ c (n-(n-1/2)-1) log(n-(n-1/2)-1))+\theta(n)$$ $$T(n) = (c (n-1)/2 log (n-1/2)+ c (n-1)/2 log((n-1)/2)+\theta(n)$$ $$T(n) = (c (n-1) log (n-1/2)+ \theta(n)$$ $$T(n) = (c (n-1) log (n-1)- c(n-1)+ \theta(n)$$ $$T(n) = (c n log (n-1) - c log (n-1)- c(n-1)+ \theta(n)$$ $$T(n) = (c n log (n-1) - c log (n-1)- c(n-1)+ \theta(n)$$ $$T(n) \geq (c n log (n/2) - c log (n-1)- c(n-1)+ \theta(n)$$ since $n \geq 2$ $$T(n) \geq (c n log (n) -cn - c log (n-1)- c(n-1)+ \theta(n)$$ $$T(n) \geq (c n log (n) - c (n - log (n-1)- (n-1))+ \theta(n)$$ if we pick a small value for c so $\theta(n)$ is larger than n - log (n-1)- (n-1) then $$T(n) = \Omega(n log n)$$

7.4-1

Show that in the recurrence $T(n) = max_{0 \leq q \leq n- 1} (T(q) +T(n-q-1))+ \theta(n),$ $T(n) = \Omega (n^2)$ Let us use assumption method $$T(n) \geq c n^2 $$ $$T(n) \geq c q^2 + c (n-q-1)^2+ \theta(n) $$ $$T(n) \geq c q^2 + c (n-q-1)^2+ \theta(n) $$ for T(n) to be greater than or equal to right side of the equation we need to see if this hold at maximum value of the term $q^2 + (n-q-1)^2$. The maximum for term occurs when q = 0,n-1. By substituting either one we get $(n-1)^2$. $$T(n) \geq c (n-1)^2 + c + \theta(n)$$ $$T(n) \geq c (n^2-2n+1) + c + \theta(n)$$ $$T(n) \geq c (n^2)+ c (-2n+2) + \theta(n)$$ if we pick a large value for c so it can dominate $\theta(n)$. $$T(n) \geq c (n^2)$$ $$T(n) = \Omega(n^2)$$

7.3-2

When RANDOMIZED-QUICKSORT runs, how many calls are made to the randomnumber generator RANDOM in the worst case? How about in the best case? Give your answer in terms of $\theta$-notation.

The no of times RANDOM is called depends on no of times RANDOMIZED-PARTITION is c alled.The Best case and worst case depends on partitioning(like earlier in normal quick sort case). The worst case occurs when partition of n gives n-1 and n-1 gives n-3. The recurrence for RANDOMIZED-PARTITION is: $$ T(n) = T(n-1)+ \theta(1) $$ $\theta(1)$ for the comparison if p < q.
By using substitution method the above recurrence is $\theta(n)$.
The best case occurs when when partition of n gives n/2 and n/2-1 elements:
$$ T(n) \leq 2 T(n/2)+\theta(1) $$ $$ T(n) \leq 2 T(n/2)+\theta(1) $$ Above recurrence is master theorem case 2. The recurrence is $\theta(n)$. for both best and wrost case the no of times RANDOMIZED-PARTITION is called is $\theta(n)$

7.3-1

Why do we analyze the expected running time of a randomized algorithm and not its worst-case running time?

An algorithm is randomized if the behavior is dependent not only on the input but also by values produced by random number generator. In analysis of randomized algorithm we use a random - number generator to produce the distribution of various input values. When we calculate the running time it will be for the distribution of various input values. In a sense we are calculating average time for the distribution of input values. We are in effect averaging running time for all possible input values. Randomization will reduce the chance of getting a worst case. It will be in correct measure if we use randomization to analyze worst-case running time.

7.2-6

Argue that for any constant $0 \gt \alpha \geq 1/2$, the probability is approximately $1-2\alpha$ that on a random input array, PARTITION produces a split more balanced than $1 - \alpha$ to $\alpha$.

you approach solution in two ways:
1) if the partition has to be more balance than $1 - \alpha$ to $\alpha$ the pivot has to be between $\alpha n$ and $(1 - \alpha )n$. The probability of pivot between $\alpha n$ and $(1 - \alpha )n$ is no of elements between $\alpha n$ and $(1 - \alpha )n$ over total no of elements. $$((1 - \alpha )n - \alpha n )/n$$ $$(1 - 2 \alpha) n /n$$ $$(1 - 2 \alpha)$$ 2) partition can split the array in two ways
[ \alpha n , (1 - \alpha )n ]
[(1 - \alpha )n , \alpha n]
The probability of having less balanced PARTITION than $1 - \alpha$ to $\alpha$ occurs if the pivot is in the first \alpha n or the second \alpha n. The probability of having less balanced PARTITION than $1 - \alpha$ to $\alpha$ is $$2 \alpha n /n $$ $$2 \alpha $$ The probability of PARTITION produces a split more balanced than $1 - \alpha$ to $\alpha$ is = 1 - probability having less balanced PARTITION than $1 - \alpha$ to $\alpha$ $$ 1 - 2 \alpha $$

7.2-5

Suppose that the splits at every level of quicksort are in the proportion $1- \alpha$ where $0 \leq \alpha \leq 1/2$ is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately $- lg n/lg \alpha$ and the maximum depth is approximately $- lg n/ lg (1 - \alpha)$ (Don’t worry about integer round-off.) The key is understand where do we get maximum and minimum depths in a tree. Since $\alpha$ is less than or equal to 0.5. If $\alpha \lt 0.5 $ the tree with $\alpha$ elements as the parent will end soon compared to $1-\alpha$ elements because it will less no of elements compared to $1-\alpha$. n is The tree with $\alpha n $ is reduced to $\alpha^2 n$ elements for second level. Similarly at k'th level it will be $\alpha ^ k n$. If the k level is a leaf then $$\alpha ^ k n = 1 $$ applying logarithm on both sides $$ log (\alpha ^ k n) = log 1 $$ $$ log (\alpha ^ k) = log 1 - log n $$ $$ k log (\alpha) = - log n $$ $$ k = - log n/log (\alpha) $$ Similarly the tree with (1-\alpha)n elements will have maximum depth. $$ (1-\alpha)^k = 1$$ applying logarithm on both sides $$ log (1-\alpha)^ k = log 1 - log n $$ $$ k = - log n/log (1-\alpha) $$

7.2-4

7.2-4 Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order by check number, and merchants usually cash them with reasonable dispatch. The problem of converting time-of-transaction ordering to check-number ordering is therefore the problem of sorting almost-sorted input. Argue that the procedure INSERTION-SORT would tend to beat the procedure QUICKSORT on this problem.

INSERTION-SORT takes $\theta(n)$ to sort a sorted input because the inner while loop will take $\theta(1)$ instead of $\sum_1^n j$. It would take similar amount of time for almost sorted input may be little higher than $\theta(n)$ but not $\theta(n^2)$. QUICKSORT will take $\theta(n^2)$ on sorted input and similar amount of time on almost sorted input.

7.2-3

7.2-3 Show that the running time of QUICKSORT is $\theta(n^2)$ when the array A contains distinct elements and is sorted in decreasing order.

If the elements are sorted in decreasing order i will not increment from p-1 and for the lines 3-6 of the PARTITION procedure. The largest value in the array will be swapped with smallest elements and a partition of 0 and n -1 will be created. After the second iteration again a partition of 0 and n-2 will be created. This will continue until smaller partition of two elements is created. All the n-1,n-2.. elements will be iterated n-2,n-3.. times. This is an arithmetic progression hence the running time is $\theta(n^2)$.

7.2-2

What is the running time of QUICKSORT when all elements of array A have the same value?

The running time if all elements in a array same is similar to wrost case running running because i will be incremented to n-1 for first iteration so the recuurence will be $$T(n) = T(n-1)+\theta(n)$$ refer 7.2-1 $$T(n) = \theta(n^2)$$

7.2-1

Use the substitution method to prove that the recurrence $T(n) = T(n -1)+\theta(n)$ has the solution $T(n)=\theta(n^2)$, as claimed at the beginning of Section 7.2.

refer to 4.3-1.

7.1-4

7.1-4 How would you modify QUICKSORT to sort into nonincreasing order?
If the line 4 of partition is changed to $A[i] \geq x$ the array will be sorted into non increasing order

7.1-3

7.1-3 Give a brief argument that the running time of PARTITION on a subarray of size n is $\theta(n)$

In the worst i and j will be incremented n -1 times.Hence the upper bound is $O(n)$. In the best and average case i may not be incremented n-1 times but there still will be n-1 comparisons hence the best case running time is $\Omega(n)$. Hence the running time of the algorithm is $\theta(n)$

7.1-2

What value of q does PARTITION return when all elements in the array A[p..r] have the same value? Modify PARTITION so that $q = \lfloor(p + r)/2\rfloor$ when all elements in the array A[p..r] have the same value.
At the end of the for loop of the PARTITION subroutine the value of i in a array that has same values is q -1 and it will return q. We can modify the PARTITION line 4 as
A[j] < x or A[j] == x and j%2 == 0 this will return $q = \lfloor(p + r)/2\rfloor$ if you have an array with same values.

problem 6-3

6-3 Young tableaus An m x n Young tableau is an m x n matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of a Young tableau may be 1, which we treat as nonexistent elements. Thus, a Young tableau can be used to hold r  mn finite numbers.

c)Give an algorithm to implement EXTRACT-MIN on a nonempty mxn Young tableau that runs in O(m + n) time. Your algorithm should use a recursive subroutine that solves an m x n problem by recursively solving either an m-1 x n or an m x n-1 subproblem. (Hint: Think about MAXHEAPIFY.) Define T(p), where p = O(m + n), to be the maximum running time of EXTRACT-MIN on any mxn Young tableau. Give and solve a recurrence for T(p) that yields the O(m + n) time bound.
1,1 will have smallest element in the matrix. Lets replace this with $\infty$ (since empty should have infinity in tableau). Now the array is not a tableau. But i+1..m,j..n and i..m,j+1..m are two tableau(sub tableaus). we need to recursive
EXTRACT-MIN(A,m,n)
int min = A[1,1]
A[1,1] = $ \infty $
YOUNGIFY(A,m,n,1,1)
return min.
YOUNGIFY(A,m,n,i,j)
$minimum_i$ = i
$minimum_j$ = j
if i+1 <= m and A[i][j] < A[i+1][j]
$minimum_i$ = i+1
if j+1 <=n and A[$minimum_i$][j] $minimum_j$ = j+1
if $minimum_i$ != i and $minimum_j != j$
swap A[i][j] and A[$minimum_i$][$minimum_j$]
YOUNGIFY(A,m,n,$minimum_i$,$minimum_j$)
The YOUNGIFY is recursively called for i+j times(take a small 2 x 2 or 3 x 3 matrix infinity will reach from 1,1 to 3,3 finally). i and j cannot exceed m and n hence the running time $O(m+n)$ and we are solving the mxn problem recursively m-1 x n or m x n-1.

d. INSERT(A,m,n,key)
IF A[m] [n] < key
error ("Error")
A[m][n] = key;
BUILD-YOUNGIFY(A,m,n)


Below is BUILD-YOUNGIFY BUILD-YOUNGIFY(A,m,n)
$maximum_i$ = m
$maximum_j$ = n
if m-1 > 0 and A[$maximum_i$][$maximum_j$] < A[m-1][n] Then
$maximum_i$ = m-1
if n-1 > 0 and A[$maximum_i$][$maximum_j$] < A[m][n-1] Then
$maximum_j$ = n-1
If $maximum_i$ != m or $maximum_j != n$ Then
swap A[$maximum_i$][$maximum_j$] and A[m][n]
BUILD-YOUNGIFY(A,$maximum_i$,$maximum_j$)
even if we have an empty array and we are inserting new element the elements will traverse only (i+j) the maximum values for i and j are m and n so the running time is $O(m+n)$
e. SORT(A)
for i = 1 to m
INSERT(Y,n,n,A[i])
for i = 1 to m
A[i] = EXTRACT-MIN(Y)
The above procedure from line 1 to 2 is inserting $n^2$ in to tableau which takes $O(n+n)$ and lines 3 to 4 also extract $n^2$ and EXTRACT-MIN runs $O(n+n)$ this gives the running time of $O(n^3)$
In general, given n numbers to sort, let $a = \sqrt n$. We can create an empty a x a Young tableau and perform the above algorithm (with m = n). Each operation on the Young tableau will take O(a + a) = $O(\sqrt n)$ time. Therefore, the running time of the algorithm will be $O(n \sqrt n)$ = $O(n^{1.5})$.
f.
If we start from 1,1 or m,m we have to scan m x n elements. It will in efficient compared to m+n. The only possible way is to 1,n and move left until we the value if we dont we have to search the below row. if A[$i_0$][$j_0$] $\geq$ key we dont have to search i < $i_0$ and j < $j_0$.Because of the above logic we will always skip n elements and search only m+n in worst case hence the running time is $O(m+n)$
SEARCH-KEY (A,key,m,n)
i = 1
j = n
while j <= 1 and A[i][j] >= key
if A[i][j] == key
return "found"
j = j -1
m = m - 1
if i <= m
SEARCH-KEY(A,key,m,n)

problem 6-2

6-2 Analysis of d-ary heaps
A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children.
a. How would you represent a d-ary heap in an array?
b. What is the height of a d-ary heap of n elements in terms of n and d?
c. Give an efficient implementation of EXTRACT-MAX in a d-ary max-heap. Analyze its running time in terms of d and n.
d. Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its running time in terms of d and n.
e. Give an efficient implementation of INCREASE-KEY(A,i,k) which flags an error if k < A[i] , but otherwise sets A[i] = k and then updates the d-ary maxheap structure appropriately. Analyze its running time in terms of d and n.

a. A d-ary can be represented in a single dimensional array with elements A[1]..A[d+1] (for java A[0] to A[d]) and for the root and it children. The children of children can be represented from $A[d+2]..A[d^2+d+1]$(this is for the whole grandchildren level of the root.For java it will be $A[d+1]..A[d^2+d]$). It will easier if you can draw 3 and 4 ary trees to understand.This will continue for its children as well.
The procedure for GET-PARENT and GET-CHILD are as follows:
GET-PARENT
return $\lfloor (i+2)/d+1 \rfloor$ (java: (i-1)/d)
for get child we need to define a new variable j $1 \leq j \leq d$
GET-CHILD
return d(i-1)+j+1 (java: d(i)+j)

b. The height of the tree can be calculated same as exercise 6.1-2. The no of elements can be bounded by max and min no of elements. $$ d^(h) \leq n \leq d^(h+1) -1 $$ $$ d^(h) \leq n \leq d^(h+1) -1 \lt d^(h+1) $$ $$ d^(h) \leq n \lt d^(h+1) $$ Applying logarithm for above equation: $$ log d^(h) \leq log n \lt log d^(h+1) $$ $$ h log d \leq log n \lt (h+1) log d $$ $$ h \leq log n /log d \lt (h+1) $$ since h is an integer it is $\lfloor log_d n \rfloor$
c. EXTRACT-MAX(A,d)
int max = A[1]
A[1] = A[A.heapsize]
MAX-HEAPIFY(A,1,d)
return max; MAX-HEAPIFY(A,i,d)
//first child: d(i-1)+j+1 = d(i-1)+1+1 to last child d(i-1)+d+1 = di+1
largest = i
for j = d(i-1)+2 to d*j (iterate from first child to last)
if(j <= A.heapsize && A[j] > A[i] )
largest = j
if largest != i then
swap A[largest] and A[i]
MAX-HEAPIFY(A,largest,d)
d.
The only change from binary to n-ary is we need to send d(the no of children) to the insert prcoedure. INSERT(A,key,d)
A.heapsize = A.heapsize+1;
A[A.heapsize] = $- \infty $
MAX-HEAP-INCREASE(A,A.heapsize,key,d)
We see the implementation of MAX-HEAP-INCREASE in section e of the solution(which is below). The running time depends on MAX-HEAP-INCREASE above procedure takes constant time except for MAX-HEAP-INCREASE.
e.
MAX-HEAP-INCREASE(A,i,key,d) IF A[i] > key error("Invalid Key") A[i] =key While i > 1 and A[parent(i)] < A[i] Swap A[i] and A[parent(i)] i = parent(i) parent(i) return (i - 1)/d+1 In the worst case an element has to move from leaf node to root which is height of the tree. So the runnning time $\theta(h)$ = $\theta(log_d n)$

Problem 6.1

We can build a heap by repeatedly calling MAX-HEAP-INSERT to insert the elements into the heap. Consider the following variation on the BUILD-MAX-HEAP procedure:

BUILD-MAX-HEAP(A)
1 A.heap-size = 1
2 for i = 2 to A.length
3 MAX-HEAP-INSERT(A,A[i ])
a. Do the procedures BUILD-MAX-HEAP and BUILD-MAX-HEAP' always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.
b. Show that in the worst case, BUILD-MAX-HEAP' requires $\theta(n lg n)$ time to build an n-element heap.
BUILD-MAX-HEAP and BUILD-MAX-HEAP' will not always create the same heap. example A= {1,2,3} calling BUILD-MAX-HEAP will create {3,2,1} and calling BUILD-MAX-HEAP' will create {3,1,2}.

There n-1 calls to MAX-HEAP-INSERT which takes log n time hence the upper bound is $\theta n logn$
lets assume all the elements are increasing order since we are calculating the worst time. each of the element will take log i (which is the height of tree)
$$ \sum_{i=1}^n \theta(log i)$$ $$ \theta(log 1+ log 2+....log n) $$ Apply logarithm property log m+ log n = log mn $$ \theta(log (1.2...n)) $$ $$ \theta(log (n!)) $$ by stirling approximation $$ \theta(n log n)) $$ $$ \geq \Omega(n log n) $$

6.5-9

6.5-9 Give an O(n lg k)-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. (Hint: Use a minheap for k-way merging.)
Solution:
1) pick first k elements from k sorted lists and form a MIN-HEAP (which takes $\theta(k log k)$ )
2) call MIN-HEAP-EXTRACT on the heap and extract the smallest of k sorted lists and insert in to final list. (which takes log k (since k is the no of elements) we do this for n elements.)
3) extract the next element from the same list whose element is placed in the final list and place it on the heap.

step 3 is to make sure we get all smaller values , compare and place on the final list. example:
List 1 : 1 2 5
List 2 : 4 5 6

step 1: pick k elements : (1, 4) is the min tree
step 2:call MIN-HEAP-EXTRACT returns 1 and place it on final list final list : (1)
step 3: we will extract 2 from list 1 and place it on the heap(4,2). This will make sure we return the smallest values of K lists.
we have to repeat step 1 for n/k elements hence the runnning time is $\theta(n/ k .k.log k)$ the time complexity is $\theta(n log k)$

6.5-8

6.5-8 The operation HEAP-DELETE(A, i) deletes the item in node i from heap A. Give an implementation of HEAP-DELETE that runs in O(lg n) time for an n-element max-heap.

HEAP-DELETE(A,i)
temp = A[i]
A[i] = A[A.heapsize]
A.heapsize = A.heapsize -1
if A[i] < temp
MAX-HEAPIFY(A,i);
else
MAX-HEAP-INCREASE-KEY(A,i,A[i]);

We need to see if the new is greater than or less than the old element. Because we have it accordingly if we smaller or larger than older number.We may it up the tree if the number larger than old or down the tree if it smaller.

6.5-7

6.5-7 Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue. (Queues and stacks are defined in Section 10.1.).

We can implement a first-in,first-out queue with a priority queue We need two array one to hold values which are inserted as in normal array and second array that hold the keys in the order of insertion and apply MIN-HEAPIFY on the array and when EXTRACT-MINIMUM can return the index and using index we can return the value from source array.
Similarly we can implement a stack with a priority queue by creating a new array that hold the order of insertion and apply MAX-HEAPIFY on the array. This will in efficient and not recommended. This will cause waste memory and computing time.

6.5-6

6.5-6 Each exchange operation on line 5 of HEAP-INCREASE-KEY typically requires three assignments. Show how to use the idea of the inner loop of INSERTIONSORT to reduce the three assignments down to just one assignment.
MAX-HEAP-INSERT-KEY(A,i,key)

If i > key
error "invalid key value"
a[i] = key

while( i > 1 and a[parent(i)] < a[i])
a[i] = a[parent(i)]
i = parent(i);


a[i] = key;

6.5-5

6.5-5 Argue the correctness of HEAP-INCREASE-KEY using the following loop invariant: At the start of each iteration of the while loop of lines 4–6, the subarray A[1..A.heap-size] satisfies the max-heap property, except that there may be one violation: A[i] may be larger than A[PARENT(i)]. You may assume that the subarray A[1 ..A:heap-size] satisfies the max-heap property at the time HEAP-INCREASE-KEY is called.

Initialization:
Before the start of the loop we replace A[i] with key and key is greater than A[i]. There may be one violation where A[i] may be larger than A[Parent(i)].
Maintenance:
After the iteration of i the sub array A[1...A.heap-size] satisfies the max-heap property but still there may be one violation where A[i] may be larger than A[parent(i)]. Because even after exchanging A[i] with A[j=parent(i)]. A[j] may be larger than A[parent(j)].
Termination: when the loop terminates the sub array A[1..A.heap-size] satisfies the max-heap property.

6.5-4

Why do we bother setting the key of the inserted node to $-\infinity$ in line 2 of MAXHEAP- INSERT when the next thing we do is increase its key to the desired value?

We need to insert $-\infinity$ MAX-HEAP-INCREASE compares the value to be inserted with existing value so it needs a value. We cant insert any value to satisfy the condition but we have insert the smallest value.

6.4-5

6.4-5 ? Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n lg n)$. This is abit complicated. i need to revisit. This is proved in a paper as the author mentions in the below article. http://stackoverflow.com/questions/4589988/lower-bound-on-heapsort

6.4-4

Show that the worst-case running time of HEAPSORT is $\Omega( n lg n)$.

The worst case occurs when we have move the root element to the leaf the running time is for MAX-HEAPIFY is $\theta (h)$ = $\theta(log n)$
Heap sort calls MAX-HEAPIFY n-1 times.
$$ \sum_2^n \theta (log n) $$ $$ \theta( \sum_2^n log n) $$ $$ \theta( log 2+log 3 + ...log n) $$ $$ \theta(log n!) $$ $$ \theta(n log n) $$ hence the worst case running time is $\Omega( n lg n)$

6.4-3

6.4-3 What is the running time of HEAPSORT on an array A of length n that is already sorted in increasing order? What about decreasing order? No effect. Either way Build-MAX-HEap will take $O(n)$ to build a max heap. The running time of a heap sort take n-1 calls to max-HEAPIFY (takes log n time) $$\sum_2^n log n $$ $$ log 2+ log 3+.....log n $$ $$ log n! $$ by Stirling approximation above eq is $$ O(n log n)$$

6.4-2

Argue the correctness of HEAPSORT using the following loop invariant: At the start of each iteration of the for loop of lines 2–5, the subarray A[1 ..i] is a max-heap containing the i smallest elements of A[1 .. n] , and the subarray A[i+1..n] contains the n - i largest elements of A[1..n] , sorted.
Initialization: when i = A.length A[1 ..A.length] is a max- heap as we use build-max-heap containing A.length smallest elements of A[1 ..A.length] and A[i+1..n] will contain zero elements. Maintenance: For each iteration by the loop invariant A[1..i] will contain i smallest elements of A[1..n]. After iteration i the largest element of max-heap will be exchanged with A[i] and A[1..i] will contain i smallest elements of A[1..n]. Line 3 of the procedure exchanges A[1] with A[i] making A[i..n] n-i+1 largest elements of A[1..n]. The heapsize is reduced (heapsize = i -1). No the subarray A[1..i-1] is a not max heap.The root violates the max heap property but child obey the property. We call Max-heapify to make A[1..i-1] a max heap. Termination: when i = 1 we have subarray containing A[2..n] n-i+1 largest elements of A[1..n] and A[1..i] containing the smallest element of A[1..n].

B.5-3

B.5-3 Show by induction that the number of degree-2 nodes in any nonempty binary tree is 1 fewer than the number of leaves. Conclude that the number of internal nodes in a full binary tree is 1 fewer than the number of leaves.

Let l(T) be the no of leaves and d(T) be the nodes of degree 2(nodes that have 2 children.) of a tree T.
Base:If T is a binary tree with 1 node, then T consists of a single leaf, and no other nodes. In particular, it has no degree 2 nodes. So in this case l(T) = d(T) + 1. d(T) is zero.
Induction hypothesis: Suppose then that n0 is a positive integer with the property that if T is any binary tree with $n > n0 \geq 1 $ nodes, then l(T) = d(T) + 1.
Induction step: Suppose now that T is a binary tree with $n = n0 + 1 \geq 2$ nodes. Then T has a leaf L. By deleting L from T, we get a new tree T' with$ n = n0 \geq 1 nodes$. So by the induction hypothesis, l(T') = d(T') + 1. We consider two cases:
(a) L has no sibling in T, and
(b) L has a sibling in T.
Note that since T has at least two nodes, L is not the root of T, and hence L has a parent P in T. In case (a), P has degree 1 in T, and hence it’s a leaf of T'. Thus, l(T) = l(T') and d(T) = d(T'). So in this case, we have l(T) = d(T) + 1. In case (b), P has degree 2 in T, and hence degree 1 in T'. Thus l(T) = l(T') + 1 and d(T) = d(T') + 1. So by the induction hypothesis, we have that l(T) = l(T') + 1 = d(T') + 1 + 1 = d(T) + 1. the case b proves for full binary. A full binary tree every node has o or two children.

6.3-2

6.3-2 Why do we want the loop index i in line 2 of BUILD-MAX-HEAP to decrease from A{length/2} to 1 rather than increase from 1 to A[length/2]? This is because it will the precondition MAX-HEAPIFY condition is met before calling it.i.e if we increase from 1 to A[length/2] the precondition will fail and the loop invariant will not hold. If we decrease from A{length/2} to 1 we will max- heaps in both left and right subtrees.

6.2-6

6.2-6 Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is $\Omega (lg n)$. (Hint: For a heap with n nodes, give node values that cause MAXHEAPIFY to be called recursively at every node on a simple path from the root down to a leaf.)

The worst case occurs when an element from root is less than all it children for MAX-HEAPIFY. The running time is $\theta (h)$ where h is height of the tree. h is also log n. hence the running time $\theta(log n)$. The worst case running time is $\Omega (log n)$. since $\Omega$ is not tied to best case running time and $\theta$ is not average case running time and $O$ is not worst case running time. These are just math functionns that specify the bound. The wrost case running time means in a worst case the guarantee that the algorithm will always finish on time.
Also according to theorem 3.1 if $f(n) = \theta(g(n))$ then $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. please refer for more info on asymptotic notations: http://www.cs.berkeley.edu/~jrs/61b/lec/21

6.2-5

The code for MAX-HEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MAX-HEAPIFY that uses an iterative control construct (a loop) instead of recursion. while(i<=A.length) l = left(i) r = right(i) if l <= A.length and A[l] > A[i] then largest = l else largest = i if r <= A.length and A[r] > A[largest] then largest = r; if largest != i then swap A[i] and A[largest] i = largest; else break

6-2-4

What is the effect of calling MAX-HEAPIFY.A; i / for i > A.heap-size/2?
No effect. Since for i > A.heap-size/2 are leaves of the tree. Remember $\lfloor n/2 \rfloor+1 ,\lfloor n/2 \rfloor+2...n$ are all leaves.

6.2-2

Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFYA(i), which performs the corresponding manipulation on a minheap. How does the running time of MIN-HEAPIFY compare to that of MAXHEAPIFY? MIN-HEAPIFY A(i)
l = left(i)
r = right(i)
if l<=A.length and A[l] < A[i] then smallest = l else smallest = i; if r<=A.length and A[r] < A[smallest] then smallest = r if smallest != i then swap a[i] and a[smallest] MIN-HEAPIFY(A,smallest) The running time is same as MAX-HEAPIFY because the max size of substree 2n/3 and $\theta(1)$ to swap A[i] and A[left(i)] and A[right(i)].

Heap sort 2n/3 sub tree size

In a tree where each node has exactly either 0 or 2 children, the number of nodes with 0 children is one more than the number of nodes with 2 children.{Explanation: number of nodes at height h is 2^h, which by the summation formula of a geometric series equals (sum of nodes from height 0 to h-1) + 1; and all the nodes from height 0 to h-1 are the nodes with exactly 2 children}

    ROOT
  L      R
 / \    / \
/   \  /   \
-----  -----
*****

Let k be the number of nodes in R. The number of nodes in L is k + (k + 1) = 2k + 1. The total number of nodes is n = 1 + (2k + 1) + k = 3k + 2 (root plus L plus R). The ratio is (2k + 1)/(3k + 2), which is bounded above by 2/3. No constant less than 2/3 works, because the limit as k goes to infinity is 2/3.
Refrence : http://stackoverflow.com/questions/9099110/worst-case-in-max-heapify-how-do-you-get-2n-3

6.1-7

Show that, with the array representation for storing an n-element heap, the leaves are the nodes indexed by $$\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2. . . . .n.$$ since 2i and 2i+1 are the children for i th node. for the leaf this will not exist. The no of non leaf nodes are at most $$\lfloor n/2 \rfloor $$ since if i = n/2 if we calculate right child $$2i+1 = 2*(n/2)+1 = n +1 $$ It would outside of the boundary of heap (since we assumed we have n elements). hence the no of non leaf nodes should be at most $$\lfloor n/2 \rfloor $$ Since we index array from 1 to n and we have at most $\lfloor n/2 \rfloor $ non leaf nodes. The leaf nodes are $n/2+1,n/2+2.....n$

6.1-6

Is the array with values {23, 17, 14, 6, 13, 10, 1, 5, 7, 12} a max-heap? False. Because if you form a tree for 6 which is the 4 the element the children are 8{2i} and 9{2i+1}. But a[9] > a[4]. For max heap you need $a{[}parent(i){]} > a{[}i{]} $ but the array doesn't satisfy the above condition.

6.1-5

Is an array that is in sorted order a min-heap? True

6.1-4

Where in a max-heap might the smallest element reside, assuming that all elements are distinct? The smallest element resides at the leaf(last leaf from left to right).

6.1-3

6.1-3 Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree. Since for max-heap the parent is always greater than or equal to the child. The child is also greater than equal its childs. This relation continues till we reach end of the tree.

6.1-2

6.1-2 Show that an n-element heap has height $\lfloor lg n \rfloor$. As we know the minimum and maximum no of elements for tree of height h is $2^h$ and $2^{h+1}-1$ $$ 2^h \leq n \leq 2^{h+1}-1 $$ $$ 2^h \leq n \leq 2^{h+1}-1 \lt 2^{h+1} $$ $$ 2^h \leq n \lt 2^{h+1} $$ applying logarithm for in equality $$ h \leq log n \lt h+1 $$ But h is an integer hence the height of the tree is $\lfloor lg n \rfloor$.

6.1-1

What are the minimum and maximum numbers of elements in a heap of height h?
Since a heap is binary tree the idea is to write in the power of 2. The minimum no of nodes for height h tree is (the tree has to have 1 node to left)$$\{1+2+2^2+....+2^{h-1}\}+1$$ The above series in the flower braces can be written as a geometric series Below is the formula for geometric series(see wikipedia): $$1-r^{n+1}/1-r$$ $$ \{1-2^{h-1+1}/1-2\} + 1 $$ $$ \{1-2^{h}/-1\} + 1 $$ $$ \{2{h}-1 \}+ 1 $$ $$ 2{h}$$ The maximum no of nodes for a height h tree is $$1+2+2^2+....+2^{h}$$ Below is the formula for geometric series(see wikipedia): $$1-r^{n+1}/1-r$$ $$ 1-2^{h+1}/1-2 $$ $$ 1-2^{h+1}/-1 $$ $$ 2^{h+1} -1 $$

Harmonic Series Approximation

$$H(n) = 1+1/2+1/3+...1/n$$ This is Area under the curve $\int_1^n 1/x dx $ is $log n - log 1$ (this is an approximation) $$log n - 0$$ $$log n$$ Refer to youtube http://www.youtube.com/watch?v=H5PcgX6i0wY CLRS also has a proof: see apendix A For a monotonically decreasing function $$\int_m^{n+1} f(x) dx \leq \sum\limits_{k=1}^n f(k) \leq \int_{m-1}^n f(x) dx $$ for the lower bound $$\int_m^{n+1} 1/x dx \leq \sum\limits_{k=1}^n 1/k $$ $$ log(n+1) - log 1 \leq \sum\limits_{k=1}^n 1/k $$ $$ log(n+1) \leq \sum\limits_{k=1}^n 1/k $$ for upper bound $$\sum\limits_{k=2}^n 1/k \leq \int_{1}^n 1/n dx $$ $$\sum\limits_{k=2}^n 1/k \leq log n - log 1 $$ $$\sum\limits_{k=2}^n 1/k \leq log n $$

5.4-5

5.4-5 What is the probability that a k-string over a set of size n forms a k-permutation? How does this question relate to the birthday paradox? k-permuation over set n is $_n\mathrm{P}_k$ we can construct k-length over set n of size by $$n.n.n...n = n^k$$ the probability is $_n\mathrm{P}_k/n^k$ $$n(n-1)(n-2)...1/n^k (n-k)!$$ $$(n-1)(n-2)...(n-k+1)/n^{k-1} $$ The above equation looks similar to the probability of distinct birthdays k people in a room can have. Where k is the no of people and n -s no of days in a year.

5.4-3

5.4-3 For the analysis of the birthday paradox, is it important that the birthdays be mutually independent, or is pairwise independence sufficient? Justify your answer.

From appendix: A collection A1,A,.....An of events is said to be pairwise independent if $$Pr{Ai \cap Aj} = Pr{Ai} .Pr{Aj}$$ for all 1 i < j n.
We say that the events of the collection are (mutually) independent if every k-subset Ai1,Ai2, ... ,Aik of the collection, where 2\leq k \leq n and $1 \leq i1 < i2 < < ik \leq n$, satisfies $$Pr{Ai1 \cap Ai2 \cap.... \cap Aikg } = Pr{Ai1}. Pr{Ai2}...Pr{Aik}.$$ we need pairwise independence if we see the analysis of birthday pardox we compare two people birthdays. $$Pr\{b_i = r and b_j =r\} = Pr\{b_i=r\} Pr\{b_j=r\}$$

5.4-2

5.4-2 Suppose that we toss balls into b bins until some bin contains two balls. Each toss is independent, and each ball is equally likely to end up in any bin. What is the expected number of ball tosses?
To solve this lets take an example where we have 4 bins:
[] [] [] []
A bin can contain two balls only after two throws. Let $X_i$ be the variable when a bin contains two throws. Let X be a variable that counts no of bins that have two balls. So lets start at 2 throws It doesn't matter if the first throw hits any of the three boxes but the second throw has to hit the same box if a bin has to contain two balls.
Probability for bin to have two balls after two throws is 1 (first throw). 1/4(second throw the probability of hitting the first bin that has ball)
First throw can land in any of the 4 bins:
[B] [] [] []
[] [B] [] []
[] [] [B] []
[] [] [] [B]
the second throw has to land on any of the above 4 bins.
the final probability: 1 .1/4 (since the above events are independent)
for 3 throws:
First throw can land in any of the 4 bins:
[B] [] [] []
[] [B] [] []
[] [] [B] []
[] [] [] [B]
the second throw has to land on any of the above 3 bins other than the one containing the ball.
[B] [B] [] [] Or
[] [B] [B] [] Or
[] [B] [B] [] Or
[] [] [B] [B]
The probability is for second throw is 3/4.
The third throw has to land in any of two bins containing balls hence 1/2 (2 out of 4 bins)
The final probability: 1.3/4.1/2
for four throws:
for second throw the probability is: 3/4
for third throw we have two empty bins the probability is: 1/2
for fourth throw it has to fall in either of three bins containing a ball : 3/4
The final probability: 1.3/4.1/2.3/4
for five throws:(This is the final case since even 4 throws make it to distinct bins the fifth has to make one of the four to make the count to 2)
for second throw the probability is: 3/4
for third throw we have two empty bins the probability is: 1/2
for fourth throw it has to fall final empty bin : 1/4
for fifth throw it can fall in any bin to make the no of balls in a bin to 2 : 1
The final probability: 1.3/4.1/2.1/4 $$E[X] = 2 * 1 .1/4 + 3 * 1.3/4.1/2 + 4 * 1.3/4.1/2.3/4+ 5 * 1.3/4.1/2.1/4.1 $$ The above equation is of the form $$E[X] = \sum_{k=2}^b+1 k (k-1) b.(b-1)...(b-k+1)/b^k $$ The above sum is the no of throws in which we can get two balls in a bin.

5.4-1

5.4-1 How many people must there be in a room before the probability that someone
has the same birthday as you do is at least 1/2? How many people must there be
before the probability that at least two people have a birthday on July 4 is greater than 1/2?

The probability that someone has same birthday as me = 1 -(probability every person in the room has a different birthday as me) (every person can have birthday on other 364 days and it doesn't matter if they have birthday on same hence the 364 ) $$= 1 - (364/365)(364/365)...(364/365)$$ $$ = 1 - (364/365)^n = 1/2$$ $$ 1 - (364/365)^n \geq 1/2 $$ $$ (364/365)^n \leq 1/2 $$ applying logarithm on both sides $$ n lg(364/365) \leq lg(1/2) $$ $$ n lg(364/365) \leq - lg(2) $$ $$ n lg(365/364) \geq lg(2) $$ $$ n \geq lg(364/365) lg(2) $$ $$ n \geq 253 $$ (using a calculator ) For the second part the probability of at least two people have a birthday on July 4 is greater than 1/2 = 1 - probability of exactly one person born on july4 - probability that no one in the room is born on july 4 let probability of exactly one person born on july4 we can use binomial theorem here $$ {n \choose k} p^k (1-p)^{ n-k} $$ Let k be the no of people in the room(n=k) since we want exactly one person born on july 4(k =1). The probability of person born on a day in a year is 1/365(p =1/365) $$ {k \choose 1} (1/365)^k (1-1/365)^{ k-1} $$ $$ {k \choose 1} (1/365)^k (364/365)^{ k-1} $$ $$ {k \choose 1} (1/365)^k (364/365)^{ k-1} $$ probability that no one in the room is born on july 4: $$ (364/365)^k $$(from first part of analysis) probability of at least two people have a birthday on July 4 = $$1 - {k \choose 1} (1/365)^k (364/365)^{ k-1} - (364/365)^k $$ $$1 - {k \choose 1} (1/365)^k (364/365)^{ k-1} - (364/365)^k /geq 1/2 $$ If $k geq 613 $ the above equation is satisfied.