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.