CS5800-Homework 3 Solved

1           Problem 1
From the preceding discussion, it suffices to determine the height of a decision tree in which each permutation appears as a reachable leaf. Consider a decision tree of height h with l reachable leaves corresponding to a comparison sort on n elements, Because each of the n! permutations of the input appears as some leaf, we have n! ≤ l. Since a binary tree of height h has no more than 2h leaves, we have n! ≤ l ≤ 2h, which, by taking logarithms, implies

                                                 h ≥ lg(n!)           (since the lg function is monotonically increasing)

If half of the n!, then  lg2 = lg(n!) − 1

According to the Stirling’s approximation, lg(n!) = Θ(nlgn) (Book Equation 3.19)

h ≥ lg(n!) − 1 ≥ Θ(nlgn) = Θ(nlgn)

If fraction of , then 

If fraction of  , then 

Since the running time is Θ(nlgn), there is no comparison sort whose running time is linear for at least half of the n! inputs of length n, for a fraction of  of the inputs of length n, and for a fraction of   inputs of length n.

2           Problem 2
Since the input sequence consists of   sub-sequence, each containing k elements, there are k!nk possible output permutations. Since a binary tree of height h has no more than2h leaves, we have k!nk ≤ 2h, which, by taking logarithms, implies

    lg2)

3           Problem 3
In the code for counting sort, we assume that the input is an array A[1..n], and thus A.length = n. We require two other arrays: the array B[1..n] holds the sorted output, and the array C;0..k] provides temporary working storage.

Initial:

1
2
3
4
5
6
7
8
9
10
11
6
0
2
0
1
3
4
6
1
3
2
1
2
3
4
5
6
7
8
9
10
11
 
 
 

 
A:

B:

0                        1              2              3              4              5                6              0              1              2              3              4              5              6

2
2
2
2
1
0
2
 
2
4
6
8
9
9
11
C:                                                         =⇒

Start counting sort:

(a)

1                        2              3              4              5              6                7              8              9              10           11

B:

0
1
2
3
4
5
6
2
4
5
8
9
9
11
2                         C:

1     2     3     4     5     6     7
8     9     10     11
 
 
 
 
2
 
3
 
 
 
 
(b)                B:

0
1
2
3
4
5
6
2
4
5
7
9
9
11
C:

1     2     3     4     5
6     7
8     9     10     11
 
 
 
1
 
2
 
3
 
 
 
 
 
(c)                B:

0
1
2
3
4
5
6
2
3
5
7
9
9
11
C:

1     2     3     4     5
6     7
8     9     10
11
 
 
 
1
 
2
 
3
 
 
6
 
 
 

 
(d)               B:

0
1
2
3
4
5
6
2
3
5
7
9
9
10
C:

1     2     3     4     5
6     7
8
9     10
11
 
 
 
1
 
2
 
3
4
 
6
 
 
 
 
(e)                B:

0
1
2
3
4
5
6
2
3
5
7
8
9
10
C:

(f)

         1     2     3     4     5     6     7     8     9     10     11

 
 
1
 
2
3
3
4
 
6
B:

0
1
2
3
4
5
6
2
3
5
6
8
9
10
C:

1     2     3
4     5
6
7
8
9     10
11
 
 
1
1
 
2
3
3
4
 
6
 
 
 
 
(g)                B:

0     1
2
3
4
5
6
2
2
5
6
8
9
10
 
 
 
 
C:

1     2
3
4     5
6
7
8
9     10
11
 
0
1
1
 
2
3
3
4
 
6
 
 
 
 
(h)                B:

0     1     2
3
4
5
6
1
2
5
6
8
9
10
 
 
 
 
 
C:

(i)

         1     2     3     4     5     6     7     8     9     10     11

 
0
1
1
2
2
3
3
4
 
6
B:

0     1     2
3
4
5
6
1
2
4
6
8
9
10
 
 

C:

(j)

1
2
3
4
5
6
7
8
9   10
11
0
0
1
1
2
2
3
3
4
 
6
 
 
 
 
B:

0     1     2
3
4
5
6
0
2
4
6
8
9
10
 
 
 

C:

1
2
3
4
5
6
7
8
9
10
11
0
0
1
1
2
2
3
3
4
6
6
(k) B:

0     1     2
3
4
5
6
0
2
4
6
8
9
9
 
 

 
C:

4           Problem 4
Pseudocode 1 Algorithm
 
1: function Algorithm(A,B,k)

2:                    let C[0..k] be a new array
 
3:
for i=0 to k do
 
4:
C[i] ← 0
 
5:
end for
 
6:
for j=1 to A.length do
 
7:
C[A[j]] ← C[A[j] + 1]
. C[i] now contains the number of elements equal to i
8:
end for
 
9:
for i=1 to k do
 
10:
C[i] = C[i] + C[i − 1]
. C[i] now contains the number of elements less than or equal to i
11:
end for
 
12:
n = C[b] − C[a − 1]
 
13:               return n

14: end function
 
This algorithm will begin by preprocessing exactly as Counting Sort does before line 10, so that C[i] contains the number of elements less than or equal to i in the array. Thus, we compute C[b]−C[a−1] to know how many of the n integers fall into a range [a..b] in O(1) time.

5           Problem 5
input
sort for last word
sort for middle word
sort for first word
COW
SEA
TAB
BAR
DOG
TEA
BAR
BIG
SEA
MOB
EAR
BOX
RUG
TAB
TAR
COW
ROW
BIG
SEA
DIG
MOB
RUG
TEA
DOG
BOX
DOG
DIG
EAR
TAB
DIG
BIG
FOX
BAR
BAR
MOB
MOB
EAR
EAR
DOG
NOW
TAR
TAR
COW
ROW
DIG
COW
ROW
RIG
BIG
ROW
NOW
SEA
TEA
NOW
BOX
TAB
NOW
BOX
FOX
TAR
FOX
FOX
RUG
TEA
6           Problem 6
After sorting on digit i, we need to show that if we restrict to just the last i digits, the list is in sorted order. Since we just claim that digits we just sorted were in ordered order, now we suppose it’s true for i−1, we need to show it for i. Suppose there are two elements, when restricted to the i last digits, are not in sorted order after the ith step. Then, we must make sure they have the same ith digit. Since they have the same first digit, their relative order is determined by their restrictions to their last i − 1 digits. However, these were placed in the correct order by the i − 1th step. Since the sort on the ith digit was stable, their relative order is unchanged from the previous step. This means that they are in correct order still.

We use stability to show that being in the correct order prior to doing the sort is preserved.

7           Problem 7
According to the lemma 8.3, Given n-digit numbers in which each digit can take on up to k possible values, Radix-Sort correctly sorts these numbers in Θ(d(n + k)) time if the stable sort it uses takes Θ(n+k) time. First run through the list of integers and convert each one to base n, then Radix-Sort them. Since it takes on up to n3,k = n3 then each number will have at most logn(n3) = 3 digits so there will be only 3 passes. For each pass, there are n possible values which can be take on, so we can use counting sort to sort each digit in O(n) time.

8           Problem 8
If we build a Binary Search Tree(BST) from bottom to top and each node contains the smaller one of a pair, then we need n−1 comparisons to build BST. The top of BST is minimum, then the second smallest must be in the path of generating the top. Since the second smallest is only smaller than the smallest

9           Problem 9
Pseudocode 2 Randomized-Select
 
1: function Randomized-Select(S,b,e,k)

2:                     if b == e then
 
3:
return S[b]
 
4:
end if
 
5:
q = Randomized-Partition(S,b,e)
 
6:
i = q-b+1
 
7:
if k == i then
. the pivot value is the answer
8:
S[q]
 
9:
else
 
10:
if k < i then
 
11:
return Randomized-Select(A,b,q − 1,k)
 
12:
else
 
13:
return Randomized-Select(A,q + 1,e,k − i)
 
14:
end if
 
15:               end if

16: end function
 
First step: Find the median in a set S

Second step: For all integers in a set S, each integer minus the median and get the absolute value saving for a new set

Third step: Use Randomized-Sort(S, b, e, k) to find the kth smallest number x from a set S[b..e]

Final step: Iterate new set to choose all the absolute value that are less than y

10          Problem 10
 

Pseudocode 3 Median

1: function Median(X,Y,n)

2:                     if n == 1 then
3:
return min(X[1],Y [1])
4:
end if
5:
if   then
6:
return median 
7:
else
8:
if  then
9:
return median 
10:
end if
11:               end if

12: end function
11          Problem 11
If n = 2: when only have y1,y2 two points, y0 could be anywhere between y1 and y2. In this case, the distance of sub-pipes is |y1y2|

If n = 3: In this case, y0 should put on the position of y2, the distance of sub-pipes is |y1y2| + |y2y3|

 

Pseudocode 4 Median

 

1: function Median(A,size)

2:                  median = size     mod 2

3:                    if size != 0 then                                                                                                                                                           . size is odd

4:                                   pick the y coordinate of the main pipeline to be equal to the median of all the y coordinates of the wells.

5:                 else                                                                                                                                                                                . size is even

6: pick the y coordinate of the pipeline to be anything between the y coordinates of the wells with ycoordinates which have order statistics  and the  

7:                  end if

8: end function

Therefore, in general, when n is even the y0 need to be the place between the two pipes which are median of all pipes. When n is odd, the y0 need to be the median of all pipes. These can all be found in linear time using the Median algorithm from Book Chapter 9.

12          Problem 12
X is 0 or 2 which probability   each, and 1 with probability  

 

13          Problem 13
13.1         a. Sort the numbers, and list the i largest
Sorting by using MergeSort takes time Θ(nlgn), and listing them out takes time Θ(i), so the total runtime is O(nlgn + i)

13.2         b. Build a max-priority queue from the numbers, and call EXTRACT-MAX i times
Build the heap which takes Θ(n) time, then call EXTRACT-MAX i times which takes Θ(ilgn). So the total runtime is Θ(n + ilgn).

13.3         c. Use an order-statistic algorithm to find the ith largest number, partition around that number, and sort the i largest numbers
Use the SELECT algorithm in Book Chapter 9.3 to find the largest number in Θ(n) time. Partition around the ith largest takes Θ(n) time. Sorting the i largest numbers take Θ(ilgi)time. So the total runtime is O(n + ilgi)

14          Problem 14
14.1 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   and that the rest are labeled 0.

There are n! possible permutations of the input array because the input elements are all distinct, so each occurs with probability  .