script

Monday, March 4, 2013

9.3-8


Professor Olay is consulting for an oil company, which is planning a large pipeline running east to west through an oil field of n wells. The company wants to connect a spur pipeline from each well directly to the main pipeline along a shortest route (either north or south), as shown in Figure 9.2. Given the x- and y-coordinates of the wells, how should the professor pick the optimal location of the main pipeline, which would be the one that minimizes the total length of the spurs? Show how to determine the optimal location in linear time.
In order to find optimal placement we only need to find medians of y-coordinates. Claim:
The optimal y-cordinate is as follows:
a) If n is even then the optimal placement of the pipeline is either on the oil well whose y-coordinate is lower median or on oil well whose y-coordinate is upper median or anywhere between them.
b) If n odd then the optimal placement of pipeline is on the oil well whose y-coordinate is the median.
Proof:
We examine various cases in each we start out with the pipeline at a particular y-coordinate and see what happens when we move it. We denote s as the sum of north and south spurs and s' denotes the sum after we move the pipeline.
If n is even and we start the pipeline on or somewhere between oil wells whose y-coordinate are the lower median and upper median. if we move the pipeline by a vertical distance d with out crossing either of the the median wells, then n/2 of the oil wells will be d distance farther from the pipeline and n/2 of the oil wells will nearer to the pipeline. If we caculate the distance s' = s+nd/2 - nd/2 then s' = s. thus all the locations on or between the two medians is good.
Now suppose if the pipeline goes through the upper median oil well and if we increase the y-coordinate of the pipeline d- distance away(upwards) from upper median. Then there are n/2+1 oil wells farther from pipeline and n/2-1 oil wells nearer to oil well. If we calculate the distance $$s' \geq s+(n/2+1)d-(n/2-1)d $$ $$s' \geq s+2d$$ clearly s' is greater than s.we conclude that if we move the pipeline away from the upper median then it increases the total spur length. similarly if we move the pipeline away below lower median the spur length increases.
when n is even the optimal placement of pipeline is on or somewhere between oil wells whose y-coordinates are upper and lower medians.
Now lets consider n is odd if we start the pipeline at oil well whose y-coordinate is the median and move the pipeline y-coordinate by d distance. Then there are n+1/2 oil well farther from the pipeline and n-1/2 oil wells nearer to the pipeline. if we calculate the distance $$s' \geq s+ (n+1/2)d -(n-1/2)d $$ $$s' \geq s+ d $$ which greater than s. A symmetrical argument shows that moving the y-cordinate of pipeline below the median also increases the spur length. If n is odd then the optimal placement for the pipeline is the median. We use the linear-time-median algorithm.

9.3-9


Let X{1..n] and Y[1..n] be two arrays, each containing n numbers already in sorted order. Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y .
If X is an array that has 1..n and let median m occurs at X[k]. Then there k elements less than equal m and n-k elements greater than equal m.If we combine both arrays X and Y the no of elements is 2n. If m is a median after combining two arrays it should have n to its left and n elements to the right including m. So for the left side to have n there n-k less than or equal to m(let x be no of elements in y which less than or equal to m n = k+x then x = n-k ). similarly for the right side k elements greater than or equal to m(let x be no of elements in y which greater than or equal to m n = n-k+x). If we can an in equality. $$Y[n-k] \leq X[k] \leq Y[n-k+1]$$ But we need to also consider when k = n. Then Y[0] will have any elements and $X[n] \leq Y[1]$. If the median k' > k then X[k] will not satisfy the above equation. Then $$X[k] \lt Y[n-k]$$. Similarly if we have K' < k then X[k] > Y[n-k+1]. Similarly the median can occur in X or Y. If it occurs Y array the comparisions will have the array names reversed(replace x with Y and Y with X).We can use above analysis to write the algorithm. We can use binary search to find the median.

FIND-TWO-ARRAY-MEDIAN(X,Y)
n = A.length
median = FIND-MEDIAN(X,Y,1,n,n)
If median not found
FIND-MEDIAN(Y,X,1,n,n)
return median
FIND-MEDIAN(X,Y,low,high,n)
If low < high
k = (low+high)/2
If k = n and X[n] = Y[1] then
return X[n]
else if $Y[n-k] \leq X[k] \leq Y[n-k+1]$
return X[k]
else if $X[k] > Y[n-k+1]$
FIND-MEDIAN(X,Y,low,k-1,n)
else
FIND-MEDIAN(X,Y,k+1,high,n)

Sunday, March 3, 2013

9.3-7


Describe an O(n)-time algorithm that, given a set S of n distinct numbers and a positive integer $k \leq n$, determines the k numbers in S that are closest to the median of S.
Assume for simplicity that n is odd and k is even. If the set S was in sorted order, the median is in position n=2 and the k numbers in S that closest to the median are in positions (n − k)/2 through (n + k)/2. We first use linear time selection to fi nd the (n − k)/2, n/2, and (n + k)/2 elements and then pass through the set S to fi nd the numbers less than (n+k)/2 element, greater than the (n−k)/2 element, and not equal to the n/2 element. The algorithm takes O(n) time as we use linear time selection exactly three times and traverse the n numbers in S once(Use for loop to do comparisons to find element > (n-k)/2 and less than (n+k)/2 but not equal to n/2 ).

9.3-6


The kth quantiles of an n-element set are the k 1 order statistics that divide the sorted set into k equal-sized sets (to within 1). Give an O(n lg k)-time algorithm to list the kth quantiles of a set. The k quantiles of an n-element sorted array A are: A[\floor 1 n/k \rfloor],A[\lfloor 2 · n/k \rfloor], . . . ,A[\lfloor(k − 1) · n/k\rfloor]. We have as inputs an unsorted array A of distinct keys, an integer k, and an empty array Q of length k − 1 and we want to find the kth quantiles of A. QUANTILES(A, k,Q)
1. if k = 1 then return
2. else
3. n = length[A]
4. i = $\lfloor k/2 \rfloor$
5. x = $ SELECT (A, \lfloor i n/k \rfloor)$
6. PARTITION (A, x)
7. Add to list Q: QUANTILES(A[1]..A[i· n/k], \lfoor k/2 \rfloor, Q)
8. Add to list Q: QUANTILES(A[i·n/k + 1]..A[n],\lceil k/2 \rceil, Q)
9. return x
The output Q of the recursive algorithm QUANTILES contains the kth quantiles of A. The algorithm first finds the key that turns out to be the lower median of Q, and then partitions the input array about this key. So we have two smaller arrays that each contain at most (k−1)/2 of the k−1 order statistics of the original array A. At each level of the recursion the number of order statistics in the array is at most half the number of the previous array. Consider a recurrsion tree for this algorithm. At the top level we need to find k − 1 order statistics, and it costs O(n) to find one. The root has two children, one contains at most $\lfoor(k−1)/2\rfloor$ order statistics, and the other $\lceil (k−1)/2 \rceil$ order statistics. The sum of the costs for these two nodes is O(n). At depth i we find $2^i$ order statistics. The sum of the costs of all nodes at depth i is O(n), for $0 \leq i \leq log_{2} (k − 1)$, because the total number of elelements at any depth is n. The depth of the tree is $d = log_{2}(k − 1)$. Hence, the worstcase running time of QAUNTILES is $ \theta(n lg k)$.

Saturday, March 2, 2013

9.3-5


Suppose that you have a “black-box” worst-case linear-time median subroutine. Give a simple, linear-time algorithm that solves the selection problem for an arbitrary order statistic.
we are given a median subroutine that takes A ,p and r as parameters and returns the median value of A[p..r] in O(n) time.Given the median below is the SELECT' algorithm for finding ith smallest element. The algorithm uses deterministic partitioning that is modified to take element to partition around as input parameter.
SELECT'(A,p,r)
if p == r then
return A[p]
x = MEDIAN(A,p,r)
q = PARTITION(A,x)
k = q-p+1
if i == k then
return a[q]
if i > k
SELECT'(A,q+1,r,i-k)
else
SELECT'(A,p,q-1,i)
Because x is the median of A[p..q] and it partition the array in to A[p..q-1] and A[q+1..r] of n/2 sizes. we have the recurrence $$T(n) \leq T(n/2)+O(n)$$ the above recurrence is master method case T(n) = O(n).

9.3-4


Suppose that an algorithm uses only comparisons to find the i th smallest element in a set of n elements. Show that it can also find the i - 1 smaller elements and the n - i larger elements without performing any additional comparisons.


Suppose that the algorithm uses m comparisons to find the ith smallest element x in a set of n elements. If we trace these m comparisons in the log, we can easily find the i - 1 smaller elements by transitivity. If x > a and a > b, then x > b can be deduced without actually performing a comparison between x and b. Similarly, the n - i larger elements can be found, too.

Say we can not decide that some element e is smaller or greater than x. Then we claim that the algorithm does not work properly, since an adversary could design an input in which e is the ith largest element instead of x. The i -1 and n -i smaller elements may be not in sorted order with respect to each but they are in sorted order with respect to the ith smallest element. What I mean we get i -1 and n-i smaller elements but it does'nt any thing about the relative order of the smaller or larger elements it means they are just smaller or larger than i.

9.3-3


Show how quicksort can be made to run in O(n lg n) time in the worst case, assuming that all elements are distinct.
The worst case for quick sort occurs when the split creates 0 and n-1 elements. $T(n) = T(n-1)+\theta(n)$. But if we select a median that gives us n/2 and n/2 split always then we can eliminate the worst case.
BEST-CASE QUICKSORT(A,p,r)
if p < r then $$i \leftarrow (r-p+1)/2 $$ $$ x \leftarrow SELECT(A,i)$$ $$ q \leftarrow PARTITION(A,x)$$ BEST-CASE QUICKSORT(A,p,q-1)
BEST-CASE QUICKSORT(A,q+1,r)
Because the BEST-CASE QUICKSORT recurses only on elements of size at most n/2(for even n n/2 and n/2 - 1 and for odd n n/2 and n/2). $$T(n) \leq 2 T(n/2) + \theta(n)$$ The running time for above recursion is similar to merge sort $O(n log n()$

9.3-2


Analyze SELECT to show that if n 140, then at least $\lceil n/4 \rcieil elements are greater than the median-of-medians x and at least $\lceil n/4 \rcieil elements are less than x. if we draw a 5 X 5 grid. we have 3n/10 greater than x and 3n/10 elements are less than x. 3 140/10 = 42 n/4 = 140/4 = 35

9.3-1

In the algorithm SELECT, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 7? Argue that SELECT does not run in linear time if groups of 3 are used.

for groups of we can. if we can draw the 7 x 7 grid figure to represent the elements. we know there are 4 elements below the median that are greater median. hence the no of elements greater than the median of medians is $4(n/14 - 2)$ = $2n/7 - 8$. So if we partition the array as in step 4 using x(median of medians) we will be left with $n - (2n/7 - 8) $ = $5n/7 + 8 $
we can use the same recursive equation as for the groups of 5 and plugin values
$$T(n) \leq T(n/7)+ T(5n/7+8)+\theta(n) $$ let T(n) = cn $$T(n) = cn/7 + 5cn/7+8c+\theta(n) $$ $$T(n) = 6cn/7+8c+\theta(n) $$ $$T(n) = cn/7 - (cn/7-8c-an) $$ $$cn/7-8c-an \geq 0$$ $$cn/7-8c \geq an$$ $$c( n-56/7) \geq an$$ $$c \geq 7an/ ( n-56)$$ if n> 56 then the above recurrence is satisfied for the value of c described as above. Similarly for groups 3. if we draw 3 x 3 grid. 2(n/6-2) = n/3-4. The no of elements left after partitioning are n - (n/3-4) = 2n/3+4. $$T(n) \leq T(n/3)+ T(2n/3+4)+\theta(n) $$ $T(n) = cn$ $$T(n) = cn/3+ 2cn/3+4c)+\theta(n) $$ $$T(n) = cn/3+ 2cn/3+4c+\theta(n) $$ $$T(n) = cn+4c+\theta(n) $$ $$T(n) = cn +4c+\theta(n) $$ the above recurrence is greater than cn since we have the residual elements($4c+\theta(n)$).
we can prove the lower bound on T(n) to see the minimum value for the recurrence.The lower bound occurs when we the even split where we get 3 x 3 grid elements and no column with elements less than 3. The no of elements greater than median of medians x is 2(n/6-1)+ 1. (The -1 is for median of medians group and also there is one element in the median of medians that is greater than median of medians).The no of elements left after step 4 is n - (2(n/6-1)+1)= n - n/3+1 = 2n/3+1. The recurrence is $$T(n) \geq T(n/3)+ T(2n/3+1)+\theta(n) $$ $T(n) = cn log n$ $$T(n) = cn logn/3+ c(2n log n/3+1)+\theta(n) $$ $$T(n) = cn logn/3+ 2cn log n/3+c+\theta(n) $$ $$T(n) = cn logn+c+\theta(n) $$ $$T(n) = cn logn+c+\theta(n) $$ The above recurrence is at least cn logn.

selection in worst case linear time


The selection in worst case uses insertion sort to sort in step 2. but you would think insertion sort worst case running time is $O(n^2)$.but we are only sorting groups of 5 elements we know insertion sort is linear time for smaller values of n/. remember it beats megesort for smaller values of n. hence the step is linear time. Also dont use selection in worst case linear time because in practice it has large constants and it gets reduced by 19/20 n. it takes a while to be really small. use random selection in practice.

Wednesday, February 27, 2013

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.

Sunday, February 24, 2013

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.

Saturday, February 23, 2013

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).$

Friday, February 22, 2013

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$

Sunday, February 17, 2013

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)$

Friday, February 15, 2013

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.

Thursday, February 14, 2013

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

Wednesday, February 13, 2013

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$$

Monday, February 11, 2013

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} $$

Sunday, February 10, 2013

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.

Saturday, February 9, 2013

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.

Friday, February 8, 2013

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.

Thursday, February 7, 2013

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 $$

Wednesday, February 6, 2013

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


Sunday, January 27, 2013

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 $$

Saturday, January 26, 2013

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     
      
 ii'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.

Friday, January 25, 2013

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)$$

Thursday, January 24, 2013

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)$$

Wednesday, January 23, 2013

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)$

Tuesday, January 22, 2013

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.

Monday, January 21, 2013

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.

Sunday, January 20, 2013

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.

Saturday, January 19, 2013

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.

Sunday, January 13, 2013

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)$