# COMP3011 Assignment 3

MA Mingyu (Derek) | 14110562D | Nov 10, 2017
derek.ma | derek.ma@connect.polyu.hk

## Question 1

### a

For A, there are $$(n-1)+(n-2)+...+1 = \frac{n^2-n}{2}$$ good pairs.

### b

Let $$X$$ be a random variable indicate whether a pair of number is a good pair or not. For $$i \in \{1,2,...,\frac{n^2-n}{2}\}$$, define an indicator random variable $$X_i = I\{whether\ this\ pair\ is\ a\ good\ pair\}$$. $$X_i=1$$ indicate it's a good pair between this pair, otherwise $$X_i = 0$$.

Then $$X = \sum_{i=1}^{(n^2-n)/2} X_i$$.

$$Pr\{pair\ i\ is\ a\ good\ pair\} = 1/2$$ because the revert order of this pair exist in another permutation, and these two cases have same probability to happen in one permutation.

By Lemma 5.1, $$E[X_i] = Pr\{pair\ i\ is\ a\ good\ pair\}$$.

According to linearity of expectation: $$E[X] = E[\sum_{i=1}^{(n^2-n)/2} X_i] = \sum_{i=1}^{(n^2-n)/2}E[X_i] = \sum_{i=1}^{(n^2-n)/2}1/2 = \frac{n^2-n}{4}$$.

## Question 2

sort(array P){
sorted_by_digits = sort P according to elements' number of digits \
from smallest to largest using counting-sort \
save as a 2D array
# sorted_by_digits is in form: [[elements with 1 digit],[with 2 digits],...]
# loop the 2D array from smallest one
result = []
for each subarray in sorted_by_digits:
sorted = sort subarray using radix-sort from smallest to largest
result.append(sorted)
return result
}
# call sort(P)


The counting-sort for getting sorted_by_digits takes $$O(k)$$.

Then for total time complexity of all radix-sorts in the loop:
$Total\ Sorting\ Time = \sum{(\#\ of\ digits\ of\ subarray(10+\#\ of\ elements\ in\ subarray))} \\ = \sum{(10\times\#\ of\ digits\ of\ subarray)} + \\ \sum{(\#\ of\ digits\ of\ subarray\times\#\ of\ elements\ in\ subarray )} \\ = 10k + k \\ = O(k)$

So the total time complexity is $$O(k)$$.



## Question 3

Transfer this problem into a Exact String Matching Problem, try to match pattern S in string R+R.

findShift(String R, String S){
# call fast algorithm for Exact String Matching Problem
result = fastAlgorithm(T = R + R, P = S) # S is the pattern
if there are some output for matching position in result
return 'YES'
else
return 'NO'
}
# call findShift(R, S)


The time complexity is mainly the time for the fast algorithm which is $$\Theta(2|R|+|S|)$$. So the time complexity is $$O(|R|+|S|)$$.

## Question 4

### a

If $$P = <(2,0), (5,1), (4,1.1), (2,4)>$$, for point $$(4,1.1)$$, it's a maximal with respect to $$P$$, but it's not on the convex hull. The following figure can illustrate the situation clearly: ### b

findMaximal(array of points P){
sorted_by_x = sort P according to points' x value from largest to smallest \
using merge-sort, save as 2D array
# sorted_by_x is in form: [...,[point(s)],[point(s)],[point(s) at largest x]]
maximalList = []
yMaxGlobal = 0
for each array in sorted_by_x:
# get the point with largest y value at this x
yMax = 0
for each element in array:
if (element.y >= yMax):
yMax = element.y
maxYPoint = element
# compare with global max y value
if (maxYPoint.y > yMaxGlobal):
# if the point with largest y at this x is larger than previous max y value
# then this point is maximal
maximalList.append(maxYPoint)
yMaxGlobal = maxYPoint.y
return maximalList
}
# call findMaximal(P)


In this algorihtm, the time complexity of sorting by x value is $$O(nlgn)$$. The loop in the loop to get the point with largest y value in that x will scan every individual points in P, so the time complexity is $$O(n)$$. All in all, the dominant time complexity is the sorting, thus the total time complexity is $$O(nlgn)$$.