Description
Question – 1
The Hadamard matrices H0, H1, H2, … are defined as follows:
• H0 is the 1 × 1 identity matrix [1].
• For k > 0, Hk is the 2
k × 2
k matrix
”
Hk−1 Hk−1
Hk−1 – Hk−1
#
(1)
Show that if v is a column vector of length n = 2k
, then the matrix-vector product Hkv can be
calculated using O(n log n) operations. Assume that all the numbers involved are small enough
that basic arithmetic operations like addition and multiplication take unit time.
Solution – 1
If the column vector v is split into two halves (v1, v2), then the matrix-vector product Hkv becomes
h
Hk−1v1+Hk−1v2
Hk−1v1−Hk−1v2
i
. We can now compute the matrix-vector product recursively as described in the
following pseudocode:
Listing 1: Code
vector Matproduct ( v ){
if (| v |==1)
return v ;
vector v1 = v [0..(| v |/2 -1) ];
vector v2 = v [(| v |/2) …(| v | -1) ];
r1 = Matproduct ( v1 ) ;
r2 = Matproduct ( v2 ) ;
vector ans [| v |];
for ( int i =0; i <| v |/2; i ++) {
ans [ i ]= r1 [ i ]+ r2 [ i ];
}
for ( int i =| v |/2; i <| v |; i ++) {
ans [ i ]= r1 [i -| v |/2] – r2 [i -| v |/2];
}
return ans ;
}
Assignment № 2 Page 1
Correctness and Explanation:-
The function above splits the vector into two halves and returns the same vector if it’s size is
one. Else it recursively calls itself to get r1 and r2 and returns the product vector in its simplified h
Hk−1v1+Hk−1v2
Hk−1v1−Hk−1v2
i
form.
Running Time Analysis:-
The time complexity is given by
T(n) = 2T(n/2) + O(n)
which is the same as mergesort, and thus it’s time complexity is O(n log n).
Assignment № 2 Page 2
Question – 2
Let T be a table of n relative integers. Give an algorithm to find the maximum sum of contiguous
elements, namely, two indices i and j ,(1 ≤ i ≤ j ≤ n) that maximizes Pj
k=i
T[k].
Solution – 2
Listing 2: Code
# include
int max_sum ( int arr [] , int N ) {
int maxsum = 0; // To store the maximal subsequence sum .
int thissum = 0; // Stores the present subsequence sum .
for ( int i = 0; i maxsum ) {
maxsum = thissum ; // If max < current , then update max .
} else if ( thissum < 0) {
thissum = 0; // If sum becomes > n ;
int arr [ n ];
for ( int i =0; i > arr [ i ];
}
cout < < max_sum ( arr , n ) ;
return 0;
}
Correctness and Explanation:-
We keep track of the subsequence sum starting from index 0. Also keep updating Max-Sum accordingly. Let us assume the maximal subsequence sum if from index i to j. So that must mean that for
any index i02 then f(n) has to be broken into some f(1) and f(2). This will be done using a recursion tree.
Let there be X no.of 1’s and Y no.of 2’s for the minimum value of f(n).
Let Z be the number of internal nodes of the tree.
Then following the recurrence relation the equations are:
X + Y – 1 = Z (Leaves = Internal Nodes + 1 : Complete Tree)
X + 2Y = n (Decomposition of n into 1’s & 2’s)
Xc1 + Yc2 + Zc3 = f(n)
(where c3 is the cost of each internal node)
On substituting Z = X + Y – 1 we get
f(n) = X(c1 + c3) + Y(c2 + c3) – c3
On substituting Z = n – 2Y
f(n) = n(c1 + c3) – Y(2c1 + c3 – c2) – c3
Therefore the only variable cost in f(n) is value of Y and this decides our way of splitting
2 Cases:
Case 1: c2 < 2c1 + c3
if n = 2k (even) then f(n) = k*(c2 +c3) – c3
if n = 2k+1 (odd) then f(n) = k*(c2 +c3) + c1
Here as c2 s
Therefore s is the minimum. Hence proved that above is optimum.
Case 2: c2>= 2c1 + c3
In this case minimum is (n-2)c1 + (n-2)c3 + c2
Here we take as many 1’s as possible till we reach 2 and then terminate there.
This will result in the optimal splitting.
Proof:
If this is not optimum then only way to optimise it is to put a 2 instead of two 1s. If the initial sum
Assignment № 2 Page 4
is s then now new sum will be s + c2 -2c1 – c3 because each of the 2 c1 will be replaced by a c2 and
a division will be decreased so that is a reduction of c3.But from our case condition
s + c2 − 2c1 − c3 > s
Therefore s is the minimum. Hence proved that above is optimum.
Assignment № 2 Page 5
Question – 4
Given a binary number i with binary representation bk−1…b1b0, defined revk(i) to be the number that
has binary representation b0b1…bk−1. (Example: rev3(3) = 6 since 3 and 6 have binary representations
“011” and “110” respectively.)
Given n = 2k
, consider the problem of computing the sequence revk(0), revk(1),…, revk(n − 1).
(Example for n = 8, the output is (0,4,2,6,1,5,3,7) as the binary representations of these numbers
are 000, 100, 010, 110, 001, 101, 011, 111.)
Give an O(n)-time algorithm by using divide and conquer. (This is faster than the trivial algorithm
which reverses each number one by one in total time O(nk) = O(n log n).) Remember, arithmetic
operations involving two integers are performed in O(1) time.
Solution – 4
Claim: The required sequence S(n) is
S(n) = S1(n/2).S2(n/2), where n is a multiple of two
Where S1(n) is the sequence obtained when every element of S(n) is multiplied by 2, and S2(n) is the
sequence where every element in S1(n) is incremented by 1, and “.” is the concatenation operator.
Proof: The first n/2 numbers would remain the same if the bits were not reversed, as they don’t
depend on the value of the left-most bit. But for the sequence with reversed bits, it would be an
addition of a ’0’ bit to the right, that is a left shift. Therefore, the first n/2 numbers of the required
sequence would be the sequence S(n/2) with each element multiplied by 2.
The next n/2 numbers are 1 in the most significant bit followed by the the bits of all the previous
numbers in order. Therefore, in the in the reverse sequence of bits, the numbers would be the numbers
in the first half plus 1 in the same order.
Consider the recursive function that does this to give the array Sn.
Listing 3: Code
void RevSeq (S , n ) {
if( n ==1) {
S [0]=0; return ;
}
else {
RevSeq (S , n /2) ;
for (int i =0; i < n /2; i ++) {
S [ i ] = 2* S [ i ];
}
for (int i = n /2; i 0) {
S [ i ]= marker /2;
int lim = i ;
i ++;
for (int j =1; j < lim ; j ++) {
S [ i ]= S [ j ] + S [ lim ];
i ++;
}
marker /=2;
}
return ;
}
Correctness and Explanation:-
The former algorithm does what we described in the claim. It is correct, as shown in the proof earlier.
The latter algorithm iteratively does the recursion, but usews the observations from the recursion to
do it efficiently.
Running Time Analysis:-
The former function is a recursive one, and the complexity is given by the recurrence relation:
T(n) = T(n/2)+n where T(n/2) represents the recursive call, and n represents the nO(1) arithmetic
operations.
The solution of this recurrence relation gives the time complexity: T(n) = O(n log n)
For the latter, each iteration of the while loop and the nested for loop increments the index in the sequence, and each iteration has only O(1) operations. Therefore the time complexity for this algorithm
is O(n).
Assignment № 2 Page 7
Question – 5
We are given an index k and two sorted arrays A and B of sizes na and nb, respectively. Describe
an O(log(na) + log(nb) time algorithm that can find the k-th smallest element among all na + nb
elements in the two arrays. Example: If A = (3, 9, 15) and B = (2, 4, 8, 10, 11), and k = 5, the
output would be 9. You may assume that all elements are distinct. Hint: Aim for a recurrence of the
form T(N) = T(N/2) + O(1), where N = nanb. Think in terms of the product of the two arrays.
More hint: Let ma and mb be the middle elements of A and B, respectively. If k < (na + nb)/2, and
ma < mb, can we prune half of one of the arrays? What about the other cases?
Solution – 5
Listing 5: Code.
# include
using namespace std ;
// Recursive function to find the kth minimum in 2 sorted arrays .
int kth_smallest (int * arr1 , int * arr2 , int * end1 , int * end2 , int n1 , int n2←-
, int k ) {
// If the first array is completed , then simply return kth element←-
of the second array .
if( arr1 == end1 ) {
return arr2 [ k ];
}
// If the second array is completed , then simply return kth ←-
element of the first array .
if( arr2 == end2 ) {
return arr1 [ k ];
}
// Get the mid indices .
int mid1 = ( end1 – arr1 ) / 2;
int mid2 = ( end2 – arr2 ) / 2;
// If mid1 + mid2 < k, then start of the array having the smaller ←-
element at mid becomes mid + 1.
if ( mid1 + mid2 arr2 [ mid2 ]) {
return kth_smallest ( arr1 , arr2 + mid2 + 1 , end1 , end2 , n1 ,←-
n2 , k – mid2 – 1) ;
}
else {
return kth_smallest ( arr1 + mid1 + 1, arr2 , end1 , end2 , n1 , n2←-
, k – mid1 – 1) ;
}
Assignment № 2 Page 8
}
// If mid1 + mid2 > k then end of the array with the larger value ←-
at mid becomes mid – 1.
else
{
if ( arr1 [ mid1 ] > arr2 [ mid2 ]) {
return kth_smallest ( arr1 , arr2 , arr1 + mid1 , end2 , n1 , n2 , k )←-
;
}
else {
return kth_smallest ( arr1 , arr2 , end1 , arr2 + mid2 , n1 , n2 , k )←-
;
}
}
}
int main () {
int n1 , n2 ;
int x;
int k;
cin > > n1 > > n2 > > k ;
int arr1 [ n1 +1];
int arr2 [ n2 +1];
for ( int i =0; i > x ;
arr1 [ i ]= x ; // Get the 1st array .
}
for ( int i =0; i > x ;
arr2 [ i ]= x ; // Get the second array .
}
cout < < kth_smallest ( arr1 , arr2 , arr1 + n1 , arr2 + n2 ,n1 , n2 ,k -1) < k then
we can simply look at the first half of the array which has higher of the values at indices mid1 and
mid2,basically just pruning to half of one of the array’s. After decreasing the size of the array, we
can call this function recursively to get the kth smallest element when either one of the start indices
equal the end indices.
Running Time Analysis:-
This sort of implementation is a divide and conquer approach very similar to that of binary search.
Assignment № 2 Page 9
Here we will have O(log na) + O(log nb) time complexity since in the worst case, we need to go
through both the arrays completely in a binary search kind of fashion.
Assignment № 2 Page 10
Question – 6
(Computer screen display problem.) You are to design and implement a program, using divide-andconquer and runnning in time O(n log n), to display objects on the screen. To make your life simple,
all objects are rectangles and standing on the same horizontal line (say y = 0). The i-th object is
specified as (Li;Hi;Ri) where Li and Ri are its leftmost and rightmost coordinates, respectively, and
Hi is its height. The input is a sequence of triples of integers. The output should show the outline of
the objects such that hidden parts of the objects are not shown.
For example, if the input is (you can assume 3 numbers in a line, separated by spaces):
(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28)
the output should be:
(1,11), (3,13), (9,0), (12,7), (16,3), (19,18), (22,3), (23,13), (29,0)
Solution – 6
Correctness and Explanation:-
Listing 6: Class Declaration
class node {
public :
int x ;
int h ;
}
class input_node {
public :
int x ;
int h ;
int y ;
}
Listing 7: Merging Function
vector merge ( vector v1 , vector v2 ) {
int i =0; j =0 , h1 = -1; h2 = -1;
int n1 = v1 . size () , n2 = v2 . size () ;
vector v ;
while ( i < n1 && j < n2 )
{
if ( v1 [ i ] <= v2 [ j ])
{
h1 = v1 [ i ]. h ;
v1 [ i ]. h = max ( v1 [ i ]. h , h2 );
v . push_back ( v1 [ i ]) ;
Assignment № 2 Page 11
i ++;
}
else
{
h2 = v2 [ j ]. h ;
v2 [ j ]. h = max ( v2 [ j ]. h , h1 );
v . push_back ( v2 [ j ]) ;
j ++;
}
}
while ( i < n1 )
{
v . push_back ( v1 [ i ]) ;
i ++;
}
while ( j < n2 )
{
v . push_back ( v2 [ j ]) ;
j ++;
}
return v ;
}
Listing 8: Recursive Function Call Function
vector merger ( input_node a [] , int start , int end ) {
if( start == end ) {
node n1 , n2 ;
n1 . x = a [ end ]. x ;
n2 . x = a [ end ]. y ;
n1 . h = a [ end ]. h ;
n2 . h =0;
vector v ;
v . push_back ( n1 ) ;
v . push_back ( n2 ) ;
return v ;
}
else {
vector a = merger (a , start ,( start + end ) /2) ;
vector b = merger (a ,( start + end ) /2+1 , end ) ;
return merge (a , b ) ;
}
}
Assignment № 2 Page 12
Listing 9: Main
int main ()
{
for ( int ii =0; ii < t ; ii ++) {
input_node a [ n ]; // input array
vector ans = merger (a ,0 ,n -1) ;
}
}
Running Time Analysis:-
Assignment № 2 Page 13
Question – 7
You are given a pile of n coins and you may flip the first m ≤ n coins as a group.
• What is the least number of flips needed to ensure that the coins are all heads up in the worst
case?
• What is the least average number of flips needed to ensure that the coins are all heads up if
each arrangement of heads and tails occurs with uniform probability?
• What are the worst and average costs if the cost of each flip is proportional to the number of
coins flipped?
Solution – 7
For each first m elements that we chose to flip, we make sure that all have the same parity to optimize
the least number of flips required.
(a) The worst case would be when the coins are alternate heads and tails and the last coin is a tail.
In that case, we flip the the first 1 coin so then the first 2 coins have the same parity, and then flip
the first two coins such that the first three show the same face and so on. This requires n flips (first
1 coin, first 2 coins, … first n coins).
(b) Let F denote the number of flips. We can write:
F(n) = ( 1
2 × 1 + 1
2 × 0) + F(n − 1) with F(0) = 1
2
We do a flip if the first element in F(n−1) is different from the first element in F(n) and don’t do a
flip if it’s not. The probability of that happening is 1
2
. Solving this recurrence relation gives the least
average number of flips required = n
2
.
(c) If the cost is proportional to the number of coins flipped, then
For the worst case, we flip 1 coin, then 2 coins, and so on till n coins. Thus the cost would be
Pn
i=1 i =
(n)(n−1)
2
.
For the average case, the we take the first m coins and in each case the probability of flipping the
coins is 1
2
. So the cost would be
Pn
i=1
i
2 =
(n)(n−1)
4
.
Assignment № 2 Page 14
Question – 8
An m × n array A of real numbers is a Monge array if for all i, j, k, and l such that 1 ≤ i < k ≤ m
and 1 ≤ j < l ≤ n we have A[i, j] + A[k, l] ≤ A[i, l] + A[k, j]. In other words, whenever we pick
two rows and two columns of a Monge array and consider the four elements at the intersections of
the rows and columns, the sum of the upper-left and lower-right elements is less than or equal to the
sum of the lower-left and upper-right elements. For example, the following array is Monge:
10 17 13 28 23
17 22 16 29 23
24 28 22 34 24
11 13 6 17 7
45 44 32 37 23
36 33 19 21 6
75 66 51 53 34
(a). Prove that an array is Monge if and only if for all i = 1, 2, . . . , m – 1, and j = 1, 2, . . . , n – 1
we have A[i, j] + A[i + 1, j + 1] ≤ A[i, j + 1] + A[i + 1, j]. (Hint: For the "if" part, use induction
seperately on rows and columns.)
(b). The following array is not Monge. Change one element in order to make it Monge. (Hint: Use
part (a).)
37 23 22 32
21 6 7 10
53 34 30 31
32 13 9 6
43 21 15 8
(c). Let f(i) be the index of the column containing the leftmost minimum element of row i. Prove
that f(1) ≤ f(2) ≤ · · · ≤ f(m) for any m × n Monge array.
(d). Here is a description of a divide-and-conquer algorithm that computes the leftmost minimum
element in each row of an m × n Monge array A:
Construct a submatrix A’ of A consisting of the even-numbered rows of A. Recursively determine the
leftmost minimum for each row in A’. Then compute the leftmost minimum in the odd-numbered
rows of A. Explain how to compute the leftmost minimum in the odd-numbered rows of A (given that
the leftmost minimum of the even-numbered rows is known) in O(m + n) time.
(e). Write the recurrence describing the running time of the algorithm described in part (d). Show
that its solution is O(m + n log m).
Solution – 8(a)
The "only if" part is trivial, it follows form the definition of Monge array.
As for the "if" part, let’s first prove that
Assignment № 2 Page 15
A[i, j] + A[i + 1, j + 1] ≤ A[i, j + 1] + A[i + 1, j]
⇒ A[i, j] + A[k, j + 1] ≤ A[i, j + 1] + A[k, j],
where i R.H.S, the inequality does not hold. So we should either decrease A[i, j]/A[i+ 1, j + 1] or increase
A[i, j + 1]/A[i + 1, j] with a factor of 2 or more.
If we decrease 23 by 2 or more , the inequality will be broken for i, j = 0, 0. However if we increase
22 to 24, then we see that all the inequations are satisfied ⇒
37 23 24 32
21 6 7 10
53 34 30 31
32 13 9 6
43 21 15 8
is a valid Monge array with only one change at the element 22 becoming 24.
Solution – 8(c)
Let ai and bj be the leftmost minimal elements on rows a and b and let’s assume that i > j. Then
we have A[j, a] + A[i, b] ≤ A[i, a] + A[j, b].But
A[j, a] ≥ A[i, a](ai
is minimal)
A[i, b] ≥ A[j, b](bj is minimal)
Which implies that
A[j, a] + A[i, b] ≥ A[i, a] + A[j, b]
A[j, a] + A[i, b] = A[i, a] + A[j, b]
Assignment № 2 Page 16
Which in turn implies that either:
A[j, b] A[j, a] ⇒ ai
is not minimal
A[j, b] = A[i, b] ⇒ bj is not the leftmost minimal
Solution – 8(d)
If µi
is the index of the i-th row’s leftmost minimum, then we have µi−1 ≤ µi ≤ µi+1. For i = 2k +
1, k ≥ 0, finding µi takes µi+1 − µi−1 + 1 steps at most, since we only need to compare with those
numbers. Thus
T(m, n) =
m/
X
2−1
i=0
(µ2i+2 − µ2i + 1)
=
m/
X
2−1
i=0
µ2i+2 −
m/
X
2−1
i=0
µ2i + m/2
=
m/
X
2
i=1
µ2i −
m/
X
2−1
i=0
µ2i + m/2
= µm − µ0 + m/2
= n + m/2
= O(m + n).
Solution – 8(e)
The divide time is O(1), the conquer part is T(m/2) and the merge part is O(m + n). Thus,
T(m) = T(m/2) + cn + dm
= cn + dm + cn + dm/2 + cn + dm/4 + · · ·
=
lg
Xm−1
i=0
cn +
lg
Xm−1
i=0
dm
2
i
= cn lg m + dm
lg
Xm−1
i=0
Qkk(x) = A(x)mod(x − xk), which from the previous result is equal
to A(xk) ( Let z = xk). Hence Qkk(x) = A(xk).
For the second part, we have P0,n−1(x) = (x − x0) ∗ (x − x1) ∗ … ∗ (x − xn−1), which is of order n.
Also, A(x) =
Pn−1
k=0 akx
k
is of order n − 1(< n) and so we have Q0,n−1(x) = A(x)modP0,n−1(x) =
A(x).
Hence Proved.
Assignment № 2 Page 21
Solution – 11(c)
Consider A(x), let A(x) be equal to f(x) ∗ Pij + cj−i(x), where cj−i(x) represents a polynomial of
order = k, PijmodPik = 0, and so the L.H.S
becomes cj−i(x)modPik(x).Clearly L.H.S = R.H.S.
Hence Proved the first part.
Now similarly for the second part, we have R.H.S = Qij (x)modPkj (x) = cj−i(x)modPkj (x). The
L.H.S is given by A(x)modPkj , and since we know that A(x) = f(x) ∗ Pij + cj−i(x), and that k >=
i, PijmodPkj = 0, and so the L.H.S becomes cj−i(x)modPkj (x).Clearly L.H.S = R.H.S.
Hence Proved.
Solution – 11(d)
To get A(x0), A(x1), …, A(xn−1), it is sufficient to find Q00, Q11, Q22, …Qn−1,n−1, since Qk,k =
A(xk) from part b. Now, to get Qk,k, we can use a recursive code as follows:-
Listing 11: Pseudo Code
// Let the values of A(x) at the points be stored int the array arr [].
void get_val (int i , int j , Poly Q ( ij ) ) {
if( i == j ) {
arr [ i ]= Q (i , i ) ; // A(x(i)) = arr [i] = Q(ii).
}
else {
int k = ( i + j ) /2;
Q (i , k ) = Q (i , j ) modP (i , j ) ; // O( nlogn ).
Q ( k +1 , j ) = Q (i , j ) modP ( k +1 , j ) ; // O( nlogn ).
get_val (i ,k , Q ( ik ) ) ;
get_val ( k +1 ,j , Q ( k +1 , j ) ) ;
}
}
int main () {
get_val (0 ,n -1 , Q (0 ,n -1) ) ;
return 0;
}
Correctness and Explanation:-
We use a binary type of recursive function to get the values of Q(kk) at every k ∈ [0,n-1]. If i==j,
then just store the value, if not then split it into 2 halves and call the functions for each half.
Running Time Analysis:-
Assignment № 2 Page 22
We have T(n) = 2T(n/2)+O(n log(n)), which by master’s theorem leads to T(n) = O(n log2
(n)).Therefore
we have a O(n log2
(n)) solution to find the value of the polynomial at n points.
Assignment № 2 Page 23
Question – 12
An inversion in an array A[1..n] is a pair of indices (i,j) such that i A[j]. The number
of inversions in an n-element array is between 0 (if the array is sorted) and
n
2
(if the array is sorted
backward). Describe and analyze an algorithm to count the number of inversions in an n-element
array in O(nlogn) time. [Hint: Modify mergesort.]
Solution – 12
Correctness and Explanation:-
We use the basic Mergesort Function and make a very subtle modification in it’s Merging Function.
If we know the number of inversions in both the sub-arrays, the inversions not accounted for in them
are the inversions occurring during the merging part. Thus we just need to count those inversions
and then call it recurively on the sub-arrays as well.
While merging we check which of the elements is smaller and greater. During this process when we
encounter such a case that an element in the right array to be merged is smaller than the current
element in the left array to be merged i.e L[i] > R[j], it is a case of inversion with R[j]. Now as the 2
arrays are sorted we know that for i<=k<=(size_of_L) all elements L[k] are also greater than R[j].
Therefore we add all these vertices pairs in the no_of_inversions global variable. We repeat this over
all merging operations and update the count respectively.
Listing 12: Global Variable
int no_of_inversions =0;
Listing 13: Modified Merging Function
void merge (int arr [] , int l , int m , int r )
{
int i , j , k ;
int n1 = m – l + 1;
int n2 = r – m ;
int L [ n1 ] , R [ n2 ];
for ( i = 0; i < n1 ; i ++)
L [ i ] = arr [ l + i ];
for ( j = 0; j < n2 ; j ++)
R [ j ] = arr [ m + 1+ j ];
i = 0;
j = 0;
k = l ;
while ( i < n1 && j < n2 )
{
if ( L [ i ] <= R [ j ])
{
Assignment № 2 Page 2
arr [ k ] = L [ i ];
i ++;
}
else
{
arr [ k ] = R [ j ];
j ++;
// No.of elmts greater than R[j] in L are (n1 -i)
no_of_inversions +=( n1 – i ) ;
// ** Modification **
// Each time we find a smaller elmt in the right array ,
// update the inversions count by the no of elmts
// greater than it.
}
k ++;
}
while ( i < n1 )
{
arr [ k ] = L [ i ];
i ++;
k ++;
}
while ( j < n2 )
{
arr [ k ] = R [ j ];
j ++;
k ++;
}
}
Listing 14: Mergesort Function
void mergeSort ( int arr [] , int start , int end )
{
if ( start < end )
{
int mid = ( start + end ) /2;
mergeSort ( arr , l , mid ) ;
mergeSort ( arr , mid +1 , r ) ;
merge ( arr , l , mid , r ) ;
}
}
Listing 15: Main
Assignment № 2 Page 25
int main ()
{
int arr [ no_of_vertices ]; // input array
mergeSort ( arr , 0 , no_of_vertices – 1) ;
cout < < no_of_inversions <<"\n";
}
Running Time Analysis:-
Since the code is exactly same as that of Mergesort, and only incudes a constant time operation O(1)
in its merging function, its time complexity still remains the same i.e O( NlogN ) .
Assignment № 2 Page 26
Question – 13
(a) Suppose you are given two sets of n points, one set {p1, p2, …, pn} on the line y = 0 and the
other set {q1, q2, …, qn} on the line y = 1 . Create a set of n line segments by connecting each point
pi to the corresponding point qi
. Describe and analyze a divide-and-conquer algorithm to determine
how many pairs of these line segments intersect, in O(n log n) time.
(b) Now suppose you are given two sets {p1, p2, …, pn} and {q1, q2, …, qn} of n points on the unit
circle. Connect each point pi to the corresponding point qi
. Describe and analyze a divide-and-conquer
algorithm to determine how many pairs of these line segments intersect in O(n log2 n) time.[Hint:
Use your solution to part (a)].
(c) Describe an algorithm for part (b) that runs in O(n log n) time. [Hint:Use your solution from
part (b)].
Solution – 13
(a)
We sort the array P[1..n] and permute the array Q[1..n] to maintain correspondence. (This can be
done by storing the arrays as a vector of pairs and sorting by first.) This is done in O(n log n) time.
Now, for any indices i Q[j]. Thus we just have
to find the number of inversion pairs in Q. See Q-12 for the algorithm to find number of inversion
pairs. That algorithm runs in O(n log n) and so the overall complexity of determining the number of
line segments which intersect is O(n log n).
(b)
Note that the number of intersections do not depend on the actual positions of the points along the
circle, but only on their position relative to other points, for example, for each i, which other pairs
(pj , qj ) have exactly one end-point in the arc clockwise from pi to qi
. Therefore, for simplicity we will
assume that the points are numbered and specified according to their appearance in clockwise order
starting from some arbitrary location, call it “origin”, on the circle. So, for example, if p1 = 5, then
p1 is the fifth point clockwise from the origin in the set P ∪ Q.
Now we sort the array P[1..n] and permute the array Q[1..n] to maintain correspondence. (This can
be done by storing the arrays as a vector of pairs and sorting by first in O(n log n) time.) We walk
through the segments in clockwise direction and for any segment (pi
, qi), the segment (pj , qj ) will
intersect it if and only if:
pi < pj < qi < qj or pj < pi < qj < qi
Since we are moving in a sorted array, pi < pj for i < j. So for every segment i we need to find the
number of segments j such that pj < qi and qi aT(n/b) = a
2T(n/b2
) + af(n/b), and similarly we have
T(n) = aT(n/b) + f(n)
aT(n/b) = a
2T(n/b2
) + af(n/b)
a
2T(n/b2
) = a
3T(n/b3
) + a
2
f(n/b2
) …
a
i0−1T(n/bi0−1
) = a
i0 T(n/bi0
) + f(n/bi0−1
)
a
i0 T(n/bi0
) = a
i0 d = a
i0 f(n0) = a
i0 f(n/bi0
)
Adding all these equations and cancelling terms from the left hand side and the right hand side, we
have
T(n) = f(n) + af(n/b) + a
2
f(n/b2
) + … + a
i0−1
f(n/bi0−1
) + a
i0 f(n/bi0
)
=
X
i0
i=0
a
i
f(n/bi
)
=
logbX
(n/n0)
i=0
a
i
f(n/bi
).
Hence proved.
Solution – 14(b)
Let i0 = logb(n/n0),
T(n) =
Θ(n
p
) if f(n) ∈ O(n
p/(log(n))1+q
)
Θ(f(n)log(n)log(log(n))) if f(n) ∈ Θ(n
p/log(n))
Θ(f(n)log(n)) if f(n) ∈ Θ(n
p
(log(n))q−1
)
Θ(f(n)) if f(n) ∈ Θ(n
p+q
)
CASE-1:-
f(n) ∈ O(n
p/(log(n))1+q
) => f(n/bi
) ∈ O(n
p/bip(log(n/bi
))1+q
)
Assignment № 2 Page 29
T(n) =
logbX
(n/n0)
i=0
a
i
f(n/bi
)
≤
logbX
(n/n0)
i=0
a
i n
p
b
ip(log(n/bi))1+q
≤
logbX
(n/n0)
i=0
n
p
log(n/bi)
1+q
(Since a = b
p
).
≤
X
i0
i=0
n
p
(log(n) − log(b
i))1+q
.
≤
X
i0
i=0
n
p
(log(n) − ilog(b))1+q
.
≤
X
i0
i=0
n
p
(log(n) − (i0 − i)log(b))1+q
.
≤
X
i0
i=0
n
p
(log(n) − i0log(b) + ilog(b))1+q
.
≤
X
i0
i=0
n
p
(log(n0) + ilog(b))1+q
.
≤ n
pX
i0
i=0
1
(log(n0) + ilog(b))1+q
.
≤ n
pX∞
i=0
1
i
1+q
.
≤ c.np
. (Since 1
i
x
converges for x > 1and given that q>0).
T(n) = O(n
p
).
Also we know that
logbX
(n/n0)
i=0
a
i
f(n/bi
) ≥ a
i0 f(n0) ≥ a
logb(n/n0) ≥ (n/n0)
logba ≥ n
p => T(n) =
Ω(n
p
).
Therefore T(n) = Θ(n
p
).
Hence proved.
Assignment № 2 Page 30
CASE-2:-
f(n) ∈ Θ(n
p/logn)
T(n) =
logbX
(n/n0)
i=0
a
i
f(n/bi
).
= Θ(
logbX
(n/n0)
i=0
a
i n
p
b
iplog(n/bi)
).
= Θ(
logbX
(n/n0)
i=0
n
p
log(n/bi)
) (Since a = b
p
).
= Θ(X
i0
i=0
n
p
(log(n) − log(b
i))).
= Θ(X
i0
i=0
n
p
(log(n) − (i0 − i)log(b))).
= Θ(X
i0
i=0
n
p
(log(n) − i0log(b) + ilog(b))).
= Θ(X
i0
i=0
n
p
(log(n0) + ilog(b))).
= Θ( n
p
log(b)
cX
+i0
c
1
i
) , c = logb(n0).
= Θ( n
p
log(b)
Z c+i0
c
1
x
dx). (Since we can write the summation as the riemann sum,
= Θ(n
p
log( c + i0
c
)). which is both upper and lower bound).
= Θ(n
p
log(logb
(n)
c
)).
= Θ(n
p
log(log(n))).
Hence Proved.
Assignment № 2 Page 31
CASE-3:-
f(n) ∈ Θ(n
p
(log(n))q−1
)
T(n) =
logbX
(n/n0)
i=0
a
i
f(n/bi
).
= Θ(
logbX
(n/n0)
i=0
a
i n
p
(log(n) − ilog(b))q−1
)
b
ip ).
= Θ(
logbX
(n/n0)
i=0
n
p
(log(n) − ilog(b))q−1
).
= Θ(n
p
logbX
(n/n0)
i=0
(log(n) − (i0 − i) log(b))q−1
).
= Θ(k × n
p
logbX
(n/n0)
i=0
(log(n0) + ilog(b))q−1
).
= Θ(k × n
pX
i0
i=0
(i)
q−1
).
= Θ(n
p
i
q
0
).
= Θ(n
p
log(n)
q
).
= Θ(f(n) log(n)). (Since f(n) = Θ(n
p
(log(n))q−1
)
Hence Proved.
CASE-4:-
f(n) ∈ Θ(n
p+q
)
f(n) ≤ c × n
p+q
.
T(n) ≤ c
logbX
(n/n0)
i=0
a
i
f(n/bi
).
≤ c
logbX
(n/n0)
i=0
a
i n
p+q
b
ip+iq .
≤ c
logbX
(n/n0)
i=0
n
p+q
b
iq .
≤ cnp+q
logbX
(n/n0)
i=0
1
b
iq .
≤ cnp+qX∞
i=0
1
b
iq .
≤ cnp+q
1
1 − b
q
.
≤ cnp+q
.
Assignment № 2 Page 32
Therefore T(n) = O(n
p+q
).
f(n) ≥ c × n
p+q
.
T(n) ≥ c
logbX
(n/n0)
i=0
a
i
f(n/bi
).
≥ c
logbX
(n/n0)
i=0
a
i n
p+q
b
ip+iq .
≥ c
logbX
(n/n0)
i=0
n
p+q
b
iq .
≥ cnp+q
logbX
(n/n0)
i=0
1
b
iq .
≥ cnp+q × k (Since
logbX
(n/n0)
i=0
1
b
iq converges to some definite value k, as all terms are finite).
≥ cnp+q
.
Therefore T(n) = Ω(n
p+q
) => T(n) = Θ(f(n)).
Hence Proved.
Solution – 14(c)
T(n) ∈ (n
p
)wheneverf(n) ∈ (n
r
) for some real constant r
log(n)
1+q
for some q and sufficiently large n, and so n
r Θ(n
r
) = O(n
p/ log(n)
1+q
).
Hence Proved.
Assignment № 2 Page 33
Solution – 14(d)
For f(n) ∈ Θ(n
p+q/ log n), we have
T(n) =
logbX
(n/n0)
i=0
a
i
f(n/bi
).
= Θ(
logbX
(n/n0)
i=0
a
i n
p+q
b
ip+iq log(n/bi)
).
= Θ(
logbX
(n/n0)
i=0
n
p+q
b
iq log(n/bi)
).
= Θ(n
p+q
logbX
(n/n0)
i=0
1
b
iq log(n/bi)
).
= Θ(n
p+q
log n
logbX
(n/n0)
i=0
1
b
iq(1 − ilogn
b)
).
Also we know that
logbX
(n/n0)
i=0
1
b
iq(1 − ilogn
b)
must be bound by some constant k, so
T(n) = Θ(n
p+q
log n
logbX
(n/n0)
i=0
1
b
iq(1 − ilogn
b)
).
= Θ(k ×
n
p+q
log n
).
= Θ(n
p+q
log n
).
= Θ(f(n)).
Assignment № 2 Page 34
Hence proved that T(n) = Θ(f(n)).
Now for f(n) ∈ Θ(n
p+q
log n), we have
T(n) =
logbX
(n/n0)
i=0
a
i
f(n/bi
).
= Θ(
logbX
(n/n0)
i=0
a
i n
p+q
log(n/bi
)
b
ip+iq ).
= Θ(
logbX
(n/n0)
i=0
n
p+q
log(n/bi
)
b
iq ).
= Θ(n
p+q
logbX
(n/n0)
i=0
log(n/bi
)
b
iq ).
= Θ(n
p+q
log n
logbX
(n/n0)
i=0
1 − logn
b
b
iq ).
= Θ(n
p+q
log n × k). (Since
logbX
(n/n0)
i=0
1 − logn
b
b
iq must be bound by some constant k).
= Θ(n
p+q
log n).
= Θ(f(n)).
Hence proved that T(n) = Θ(f(n)).
For the 3rd part, we have g(bn) ≥ αg(n) for all n ∈ X => g(n) ≥ αg(n/b).
T(n) can be written as
logbX
(n/n0)
i=0
a
i
g(n/bi
), since f(n) ∈ Θ(g(n)). Also g(n) ≥ αg(n/b) => g(n) ≥
α
i
g(n/bi
) => g(n/bi
) ≤ g(n)/αi
, so we have X
i0
i=0
g(n/bi
) ≤ g(n) ×
X
i0
i=0
1
αi
, and so X
i0
i=0
a
i
g(n/bi
) ≤
g(n) ×
X
i0
i=0
(
a
α
)
i
.
T(n) =
logbX
(n/n0)
i=0
a
i
g(n/bi
).
= Θ(g(n) ×
X
i0
i=0
(
a
α
)
i
).
= Θ(g(n) × k). (Since X
i0
i=0
(
a
α
)
i will be bounded by a constant k).
Therefore T(n) = Θ(g(n)) = Θ(f(n))..
Hence Proved.
Assignment № 2 Page 35
Question – 15
Solution – 15
Correctness and Explanation:-
We know that if we have the ConvexHulls of the left part and the right part and we want to find the
ConvexHull of the complete set, we need to merge the individual convex hulls. We achieve this by
using the upper-tangent and the lower-tangent method.
Now the problem comes down to finding the convex hulls of the left and the right part. This is where
we utilize the paradigm of divide and conquer, we recursively divide the given vertex set into smaller
and smaller sets and we bottom out at set size ≤ 5, and then solve it for them using the brute force
algorithm. Then finally recursively calling the merge operation on these smaller vertex sets will lead
to the Convex Hull of the original Vertex set.
Listing 16: Algorithm for upper tangent:
L <- line joining the rightmost point of a
and leftmost point of b .
while ( L crosses any of the polygons )
{
while ( L crosses b )
L <- L * : the point on b moves up .
while ( L crosses a )
L <- L * : the point on a moves up .
}
Listing 17: Algorithm for lower tangent:
L <- line joining the rightmost point of a
and leftmost point of b .
while ( L crosses any of the polygons )
{
while ( L crosses b )
L <- L * : the point on b moves down .
while ( L crosses a )
L <- L * : the point on a moves down .
}
Listing 18: Merging of 2 Convex Hulls
vector < pair > merger ( vector < pair > a ,
vector < pair > b )
Assignment № 2 Page 36
{
// n1 -> size of polygon a
// n2 -> size of polygon b
int n1 = a . size () , n2 = b . size () ;
int ia = 0 , ib = 0;
// ia -> rightmost point of a
for ( int i =1; i a [ ia ]. first )
ia = i ;
// ib -> leftmost point of b
for ( int i =1; i < n2 ; i ++)
if ( b [ i ]. first < b [ ib ]. first )
ib = i ;
// finding the upper tangent
// using the upper tangent algorithm
pair < > p = UpperTagent (a , b ) ;
int uppera = p . first , upperb = p . second ;
// finding the lower tangent
// using the lower tangent algorithm
pair < > p = LowerTagent (a , b ) ;
int lowera = p . first , lowerb = p . second ;
vector < pair > ret ;
// ret contains the convex hull after merging the two convex hulls
// with the points sorted in anti – clockwise order
int ind = uppera ;
ret . push_back ( a [ uppera ]) ;
while ( ind != lowera )
{
ind = ( ind +1) % n1 ;
ret . push_back ( a [ ind ]) ;
}
ind = lowerb ;
ret . push_back ( b [ lowerb ]) ;
while ( ind != upperb )
{
ind = ( ind +1) % n2 ;
ret . push_back ( b [ ind ]) ;
}
Assignment № 2 Page 37
return ret ;
}
Listing 19: Solving ConvexHull-BruteForce
vector < pair > solve_Hull_Bruteforce ( vector < pair > a )
{
// Brute – Force Method
// Take any pair of points from the set and check
// whether it is the edge of the convex hull or not .
// if all the remaining points are on the same side
// of the line then the line is the edge of convex
// hull otherwise not
set < pair >s ;
// Contains the set of vertices in the ConvexHull
// after solving them by brute – force
for ( int i =0; i < a . size () ; i ++)
{
for (int j = i +1; j < a . size () ; j ++)
{
int x1 = a [ i ]. first , x2 = a [ j ]. first ;
int y1 = a [ i ]. second , y2 = a [ j ]. second ;
int a1 = y1 – y2 ;
int b1 = x2 – x1 ;
int c1 = x1 * y2 – y1 * x2 ;
int positive = 0 , negative = 0;
for (int k =0; k < a . size () ; k ++)
{
if ( a1 * a [ k ]. first + b1 *a [ k ]. second + c1 = 0)
positive ++;
}
if ( positive == a. size () || negative == a . size () )
{
s . insert ( a [i ]) ;
s . insert ( a [j ]) ;
}
}
}
Assignment № 2 Page 38
vector < pair > ret ;
for ( auto e : s )
ret . push_back ( e ) ;
// Sorting the points in the anti – clockwise order
mid = {0 , 0};
int n = ret . size () ;
for ( int i =0; i < n ; i ++)
{
mid . first += ret [ i ]. first ;
mid . second += ret [ i ]. second ;
ret [ i ]. first *= n ;
ret [ i ]. second *= n ;
}
sort ( ret . begin () , ret . end () , compare ) ;
for ( int i =0; i < n ; i ++)
ret [ i ] = make_pair ( ret [ i ]. first /n , ret [ i ]. second / n ) ;
return ret ;
}
Listing 20: Divide Function
// Returns the convex hull for the given set of points
vector < pair > divide ( vector < pair > a )
{
// If the number of points is less than 6 then the
// function uses the brute – force algorithm to find the
// convex hull
if ( a . size () 5 we divide it into 2 parts
// and call divide on both of them recursively
// left contains the left half points
// right contains the right half points
vector < pair > left , right ;
for ( int i =0; i < a . size () /2; i ++)
left . push_back ( a [ i ]) ;
for ( int i = a . size () /2; i < a . size () ; i ++)
right . push_back ( a [ i ]) ;
Assignment № 2 Page 39
// convex hull for the left and right sets
vector < pair > left_hull = divide ( left ) ;
vector < pair > right_hull = divide ( right ) ;
// merging the convex hulls
return merger ( left_hull , right_hull ) ;
}
Listing 21: Int Main
int main ()
{
vector < pair > input ;
// sorting the set of points according
// to the x- coordinate
sort ( input . begin () , input . end () ) ;
vector < pair > ansvector = divide ( input ) ;
}
Running Time Analysis:-
We divide the Convex-Hull into exactly 2 parts at every step of the Divide and Conquer approach,
(bottoming out at 5) calling it recursively on both parts.
Merging of 2 Convex-Hulls takes O(n) time, therefore giving us the reccurence relation
T(n) = 2T(n/2) + O(n) which on solving gives T(n) = O(nlogn) .
Assignment № 2 Page 40
