CS2800

Assignment 1,CS19B039,CS19B036,CS19B006

1. (a) Pseudo code for Heap building

BuildHeap(A) :
heapsize = size(A)
for i= heapsize/2 to 1
heapify(A,i)
end for
end BuildHeap
(b) As by seeing the above code,
we can think that the heapify does O(log n) calls and the for loop gets O(n) calls.
so, running time is O(n log n).
Ofcourse it is correct but the bound is not tight.
Heapify depends on the height of the tree ’h’ at that node.So, it takes the different
time for
 every
 height of that node which is O(h). At a height h, there will be at
most 2hn+1 nodes.
log
Pn n
 
T (n) = 2h+1
*O(h)
h=0
log
Pn h
= O(n ∗ 2h
)
h=0
By using properties of Big O notaion,ignoring ceiling function
By this sigma term is constant and the time complexity gets O(n)

2. Let poly be the array of n elements which was given input

eval and deriveval be the values at x0
F unction :
eval = 0, deriveval = 0
f or i = n − 1 to 0
eval = x0 ∗ eval + poly[i]
if (i! = 0)
deriveval = (1 + i) ∗ poly[i] + x0 ∗ deriveval
endif
endf or
endF unction

Page 1 of 14
 CS2800: Assignment 1,CS19B039,CS19B036,CS19B006

3. In the first algorithm,Think of as max-heap

loop invariant is heap[i] >= heap[i*2]
Initialisation:
Everything is a leaf, so it is already a heap.

In the loop:
children of node i are numbered higher than i. So, it preserves.

Termination:
i becomes 0, node is the root of the heap and it’s true.

In the second algorithm,

loop invariant is eval = sum of the polynomial with the given coefficents
derival = sum of the coefficients multiplied to their power of the polynomial

Initialisation: initially there is no summation.So both are zeroes

In the loop: By using Loop invariant, end of ith operation

n−i−1
ak+i+1 xk
P
eval = ai + x∗
k=0
n−i
= ai x0 + ak+i xk
P
k=1
n−i
ak+i xk
P
=
k=0
n−i−1
(k + 1 + i)ak+i+1 xk−1
P
deriveval = (i+1)ai + x∗
k=1
n−i
= (i+1)ai x0 + (k + i)ak+i xk−1
P
k=2
n−i
(k + i)ak+i xk−1
P
=
k=1

Termination:
i = -1 for the loop,
n
ak x k
P
eval =
k=0
derivative ends at i = 0,
n
(k)ak xk−1
P
So deriveval =
k=1

Page 2 of 14
 CS2800: Assignment 1,CS19B039,CS19B036,CS19B006

4. Getting permutation from its inversion vector

Let the inversion Vector be (a1,a2,....an) then position of 1,2,3,....n is (a1+1,a2+1,....an+1)
the empty space from the left

For the number 1 in permutation, let it be at position k then (k-1) values that
are greater than 1 are on its left. Hence a1=k-1 and position of is (k)th empty
space.i.e., visited [k] = false for 0 to k.

The visited array marks if the space is empty or not

for i 1 to n
position = invector[i]+1;
count, j = 0;
for j 1 to n
if(count==position)
break;
if(visited[j]==0)
count++;
end for
permutation[i]=j;
visited[j]=1;
end for

Intial Condition:
visited[i]=0 for all i in range(0,n+1)

Loop invariants:
{visited[i]∈{true,false} for all i} and {1<=j<=n}

Final Condition:
visited[i]=1 for all i in range pssbl

Proof:-
Initial case the permutation is same as inversion vector for single element

Assume for n= k; prove for n=k+1.

Page 3 of 14
 CS2800: Assignment 1,CS19B039,CS19B036,CS19B006

Assume {j1,j2,...jk} be the inversion vector add 1 to the set of elements. The per-
mutation given by inversion matrix {i1,...ik+1} we take ia+1=ja for all a∈[1,k]· To
finish the construction, we need to add 1 into the modified permutation of length
k. This can be done by shifting all elements whose index to greater than i1, to the
right by one position and filling ik+1 by 1. visited[i] for all [1,n] is true and thus,
a permutation can be constructed using inversion Matrix.

Page 4 of 14
 CS2800: Assignment 1,CS19B039,CS19B036,CS19B006

5. (a) M1 = max(W1 (i, j, k)) :

To find the two points which are farther apart,irrespective of third point
minvalue = min(a[1],b[1],c[1])
maxvalue = max(a[n],b[n],c[n])
if((minValue == c[1]) and (maxvalue == c[n]))
// check for other arrays too
temp1 = max(a[n],b[n]) - c[1];
temp2 = c[n] - min(a[1],b[1]);
M1 = max(temp1,temp2);
else M1 = maxvalue - minvalue;

Initial conditions : {(minvalue {a[1],b[1],c[1]}) ∪(maxvalue{a[n],b[n],c[n]})}

Final conditions : {M1 = maxvalue - minvalue}
Correctness : We can assume a[1] to be the least of {a[1],b[1],c[1]} and c[n] to be
the largest of {a[n],b[n],c[n]}. a[1] will be the least in three arrays and c[n] will be
the largest in three arrays. Simply we can write M1 = c[n] - a[1].
If the minimum element and maximum element present in the same row,we should
find the max(a[n],b[n]) and min(a[n],b[n]).In which we get two differences and
choosing the maximum one

(b) M2 = min(W1 (i, j, k)) :

Distance between two points be minimum such that three elements are closest

i=1,j=1,k=1
minW1 = 0
while(i,j,k <= n)
W1 = max(abs(a[i]-b[j]),abs(b[j]-c[k]),abs(c[k]-a[i]))
minW1 = min(minW1,W1)
min = min(a[i],b[j],c[k])
if(a[i] == min) i++
else if(b[j] == min) j++
else if(c[k] == min) k++
end while
M2 = minW1

Initial condition :{(i,j,k = 1)∪(minW 1 = 0)}

LoopInvariants : {(i, j, k <= n) ∪ (minW 1{W1(i,j,k)})}

Page 5 of 14
 CS2800: Assignment 1,CS19B039,CS19B036,CS19B006

Final condition :{(minW1 = min(W1(i,j,k)))∪(max(i, j, k) = n + 1)}

(c) M3 = max(W2 (i, j, k)) :

We check each combination of (a,b) (b,c) (c,a) as the upper and lower limits,since to find
the max of w2 is largest distance between two closest points. we cannot forward as taking
min and ma x of three arrays as in (a).
// similarily with other pairs
Type-1:
min = a[1]
max = c[n]
while(abs(a[1]-b[i]) < abs(c[n]-b[i]))
i++
end while
tempMin1 = min(abs(a[1]-b[i]),abs(c[n]-b[i]))

Type-2:
min = c[1]
max = a[n]
while(abs(c[1]-b[i]),abs(a[n]-b[i]))
i++
end while
tempMin2 = min(abs(c[1]-b[i]),abs(b[i]-a[n]))
tempM3(c,a) = max(tempMin1,tempMin2);

M3 = max(tempM3(a,b),tempM3(b,c),tempM3(c,a))

(d) M4 = min(W2 (i, j, k))

i=1,j=1,k=1
while(i,j,k <= n)
W2 = min(abs(a[i]-b[j]),abs(b[j]-c[k]),abs(c[k]-a[i]))
minW2 = min(minW2,W2)
min = min(a[i],b[i],c[i])
if(min == a[i]) i++
else if(min == b[i]) j++
else if(min == c[k]) k++
end while

Page 6 of 14
 CS2800: Assignment 1,CS19B039,CS19B036,CS19B006

M4 = minW2
Initial condition:{(i,j,k = 1)∪(minW 2 = 0)}
LoopInvariants : {(i, j, k <= n) ∪ (minW 2{W2(i,j,k)})}
Final condition :{(minW2 = min(W2(i,j,k)))∪(max(i, j, k) = n + 1)}

Page 7 of 14
 CS2800: Assignment 1,CS19B039,CS19B036,CS19B006

6. To find a common element x, there is a naive algorithm with time complexity

O(nm2 ) but same problem can be solved by using a O(nm) algo by just changing
a single function.
//The below part is common for both algo.
//By changing the common finder function we can realize both complexitie’s

O(nm2 ) algorithm in which common term is present:

CommonFinder1(arr1,arr2)
{
temp[m]
k=0;
for i 0 to arrsize-1 //O(m2 ) time complexity
for j 0 to m
if(arr1[i]==arr2[j])
temp[k]=arr1[i]
k++
break;
endfor
endfor
arrsize=k;
return temp;
}
arrsize=m;
int∗ common=CommonFinder1(A[0], A[1]);
for(i=0;i < n − 2;i++) //O(nm2 ) time complexity
common=CommonFinder1(common, A[i+2]);
endfor
x=common[0];
for(i=0,i < n;i++)
ind=BinarySearch(A[i],x);

O(nm) algorithm for EXTN-1:

CommonFinder2(arr1,arr2)
{
temp[m];
k=0;
while(i < arrsize and j < m) //O(m) time complexity

Page 8 of 14
 CS2800: Assignment 1,CS19B039,CS19B036,CS19B006

if(arr1[i]==arr2[j])
temp[k]=arr1[i]
i++;j++;k++
else if(arr1[i] < arr2[j])
i++;
else
j++;
endwhile
arrsize=k;
return temp;
}
arrsize=m;
int∗ common=CommonFinder2(A[0], A[1]);
for(i=0;i < n − 2;i++) //O(nm) time complexity
common=CommonFinder2(common, A[i+2]);
endfor
x=common[0];
for(i=0,i < n;i++)
ind=BinarySearch(A[i],x);

Loop Invariant:
{i <= n − 2} and {Array ”common” contains all common elements in the arrays
A[0]..A[i+1]} and {arrsize >=1}
is common for both O(nm) and O(nm2 ) algorithms.
Program correctness:
From loop invariant we can see that Array ”common” contains all common ele-
ments in the arrays A[0]..A[i+1].At the end of the loop i will be n-2 which means
all common elements btw A[0] to A[n-1] are present in ”common” array.
Since atleast one common element is there,size of ”common” array cant be zero.Hence
it will be one of the common element.This guarentees the solution.// In case of
EXTN2 it is not given that common element is present or not.
So, the for loop will be changed slightly to check whether common elements have
come to zero.
At this point we stop execution.

for(i=0,i¡n-2;i++) common=CommonFinder(common, A[i+2]);

if(arrsize==0)
cout<<”There is no common element”<<endl;

Page 9 of 14
 CS2800: Assignment 1,CS19B039,CS19B036,CS19B006

endfor

Everything other than this remains same as in the case of O(nm) algorithm before.
Loop Invariant:
{i <= n − 2} and {Array ”common” contains all common elements in the arrays
A[0]..A[i+1]}
The difference between two loop invariants is the condition {arrsize >=1}.

7. Using relations in 8.c and derivatives of these eqn :

0
Dj0 (x) = Dj−1 (x) ∗ (x − xj ) + Dj−1 (x)
D0 (x)
G0j (x) = (yj − Gj−1 (xj )) Dj−1
j−1
(xj )
+ G0j−1 (x)
with base cases G00 (x) = 0 and D00 (x) = 0. Order will be finding Dj (x) and then
Dj0 (x) and then Gj (x) and then G0j (x) in a single loop. Now computing all these
in linear j . So, c ∗ 1 + ...c ∗ n = c ∗ n(n + 1)/2 which is again O(n2 ).

Page 10 of 14
 CS2800: Assignment 1,CS19B039,CS19B036,CS19B006
Q x−xj
8. (a) Let Si (x) = xi −xj
i!=j,1<=j<=n
Si (xj ) is 0, when i!=j and 1 when i=j.
Because numerater is 0 when i!=j and when i=j factors of numerator
cancels with denominator results 1.
Now our polynomial A(x) is linear combination of Si (x) for 1 <= i <= n
P
A(x) = yi Si (x)
1<=i<=n
So for any xi (1 <= i <= n),A(xi ) = yi Si (xi ).But Si (xi ) = 1,so A(xi ) = yi
Hence it satisfies all n points.

(b) Naive algorithm calculates Si individually. To compute each Si ,numerator is a

polynomial and takes O(n2 ) steps to compute naively.Denominator can be
computed using Horners method in O(n) steps
Assuming numerator has roots a1 , a2 , a3 ...an − 1 where ai ’s are xi where one xi is
missing.
Using incremental algorithm where Pk (x) be the polynomial of roots a1 , a2 ... be
present in array p where p[i] is the coefficient of xi .
q[0] = −p[0] ∗ a[k] // a[k] is k + 1 th root
f or i = 1 to k
q[i] = p[i − 1] − p[i] ∗ a[k]
endf or
q[k + 1] = 1
starting with 1, we keep on adding ai ’s and get the final polynomial.
This takes 2k steps for kth root,now for computing Si 2k summed over to (n−1)∗n
steps for each Si .
Total number of steps = n ∗ (n − 1) ∗ n steps which is O(n3 ).

(c) We use two recurrence relations:

Dj (x) = Dj−1 (x) ∗ (x − xj )
D
j−1 (x)
Gj (x) = (yj − Gj−1 (xj )) Dj−1 (xj )
+ Gj−1 (x)
with base cases D0 (x) = 1 and G0 (x) = 0.Now all Dj ’s can be calculated in O(n2 ).
Each Gj−1 (xj ) takes 2j steps using Horner’s method. Similarily Dj−1 takes 2j steps
and addition of coefficients after multiplying also take linear steps in j.
So each Gj (x) takes c ∗ j steps. So to calculate Gn (x) we do c ∗ 1 + ..c ∗ n =
c ∗ n ∗ (n + 1)/2 steps.
So order becomes O(n2 ).

Page 11 of 14
 CS2800: Assignment 1,CS19B039,CS19B036,CS19B006

9. Let f (n) be the minimum number of calls be done for n people. we can say simply
for f (1) = 0, f (2) = 1, f (3) = 3, f (4) = 4
we can work on 5 and 6 just for induction.
min calls will be 6 and 8 for both 5 and 6 of the value n.
we can assume by this mincalls will be 2n − 4,if n >= 4.
lets prove by induction,
for f (k) = 2k − 4 .
lets introduce a person A into the group.
Lets assume he calls B who is already in the group and let the calling be 2k − 4
for passing A information.
Another calling between them makes A gets all information
f (k + 1) = 2k − 4 + 2
Extra two calls for AtoB and BtoA
f (k + 1) = 2(k + 1) − 4
Hence min calling will be 2n − 4 for n >= 4.

10. This is the 3.23 question

Initially all visited are false
count[n]
FindPath(u,v) :
visited[u] ← true
sum ← 0
for i adjacent to u
if(visited[i])
sum += count[i]
else if(i==v)
sum++
else
count[i] = FindPath(i,v)
sum += count[i]
end for
return sum

Here sum denotes the no.of paths from u to v and the algorithm is linear which is
O(n)

Page 12 of 14
 CS2800: Assignment 1,CS19B039,CS19B036,CS19B006

11. This is the 3.24 question solution

Given a DAG as an input, to determine whether it contains a path which touches
all the vertices exactly once.
If a DAG contains such a path,then there exists an edge for every two consecutive
vertices in topological sort of this DAG
Topological sort:
{
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge
while S is not empty do
remove a node n from S
add n to L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
}
Now take every two consecutive vertices in this topological order and find whether
there exist an edge between them or not.
This is the linear algorithm same as above problem

Page 13 of 14
 CS2800: Assignment 1,CS19B039,CS19B036,CS19B006

12. (a) Function :

Topologically sort the DAG
for u in reverse topological order
w be adjacent to u
cost[u] = min(pu ,min(cost[w]))
end for
end Function
This is the linear algorithm which finds the cost of every vertex

(b) In a directed graph,if two nodes u,v are in the same strongly connected compo-
nents, then the nodes reachable from u are identical to those reachable from v, so
cost[u] = cost[v]. We donot need to distiguish between nodes in the same SCC,
and we can work with a DAG
Find the strongly connected component of G
For each SCC C: let the price p∗c for component C be the smallest price of
it’s nodes, p∗c = minuc pu
Run the DAG of algorithm(a) on the metagraph, using these metaprices
p∗c .This returns component metacosts cost∗ [C] .
For each SCC C; and each node uC: cost[u] = cost∗ [C]

This takes linear time because the algorithm for SCC and for part(a) are both
linear time

Page 14 of 14