COMP3011 Assignment 3

MA Mingyu (Derek) | 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)\).