Advanced Algorithm Analysis - Desklib

This article discusses advanced algorithm analysis for Desklib, an online library for study material. It covers topics such as divide-and-rule conquer method, time complexity, recurrence tree and more. The article also explains how to determine the existence of a universal sink. References are provided for further reading.

ADVANCED ALGORITHM ANALYSIS
[Author Name(s), First M. Last, Omit Titles and Degrees]
[Institutional Affiliation(s)]

Question 1
If nI=1, then it follows that nE=2nI+1=2+1=3;
When nI=0, nE=2nI+1=1
Assuming for k’<k, the equation nE is true, it would mean that an equation given in the form nI
=k’<k, the condition nE=2nI+1 holds.
Looking at nI=k, then nE=2(k-1) + (3-1). This is translated as the total external nodes is equal to
the tree external nodes composed of k-1 nodes in addition to 3(the addition of 3 is in references
to the internal nodes that have 3 children) removing 1 (this is compensation of the eternal node
that was converted into an internal node at the time of generation of a new internal node). It can
thus be concluded that nE=2k-2+3=2k+1
Question 2
The divide-and-rule conquer method is adversely used by the algorithm. In the process of the use
of this method, deviations are noticed in the lengths of the two sorted arrays S and T in which len
(T) is used to represent T while the lens (S) is used in the representation of the array S at a
particular time.
At a given iteration, medium index of S is represented by ms=len (S)/2 and that of the medium of
S denoted by S[ms]. Conversely, the medium of T is represented using T[mt] even as the
medium index of T is denoted using mT=len (T)/2. T[mt] can be compared with mt+ms and
S[ms] that will aid in the calculation of the half part (left or right) of which of the two arrays, S
or T, may need to be discarded to allow for recursion of the smaller sub-problem (Poursina,
2016).

Condition 1(ms+mt≥ k)
Condition 1.1 S[ms]≥ T [mt ]
Elimination of the right larger half of array S may be performed where it is removed from S[ms]
to the last and hence determining the k-th smallest elements that is in T recursively alongside the
left smaller half of array S
1.2 Condition 1.2 T[mt] ¿ S[ms]
This condition has the same symmetry as that of condition one with the main and only difference
being witnessed in the exchange of T and S
Condition 2 (ms+mt<k):
2.1 Condition 2.1 S[ms]≥ T [ mt ]
Contrary to condition 1, this condition could involve the removal of the left smaller of T and
thereby proceeding to calculate the (k-mt)-th smallest element in array S recursively alongside in
the right greater half of array S
2.2 Condition 2.2 T[mt]>S[ms]
This condition has the same symmetry as that of condition one with the main and only difference
being witnessed in the exchange of T and S
Complexity in time: At each of the iterations, to the tune of 50% of a certain array is removed,
making the time complexity to be O (log (len(S)) +log (len (T))) which when simplified remains
O (logn) for size n inputs of the T and S arrays

Question 3
i) This can be achieved in quite simple manner. The sorting of every list takes the form
ak2+bk+c for certain constants a, b and c. in this case, we have n/k of those constants and hence
n
k ( ak2+bk +c ) =ank +bn+ cn
k =⊝ (nk )
ii) Sorting sub lists of a of length k would each take
T ( a )=¿
{ 0 if a=1
2T ( a
2 )+ ak if a=2p ,if p> 0
There seems to be some sense in coming up with the merger as the merging of a single sub list is
trivial while the merging of the a sublists would translate to dividing them into two distinct units
of lists of a/2, recursively merging each of the units and thereafter joining the results in steps of
ak being that there are two rays, the length each would be a
2 k
T (1) =1 k lg 1=k.0=0
It is assumed that T (a) =ak lg a and hence T (2a)
T(2a)= 2T(a)+2ak=2(T(a)+ak)=2(ak lg a+ak)=2ak(lg a+1)=2ak (lg a+lg 2)=2ak lg (2a). This
serves as a proof and can thus the number if the sublists n/k can be substituted for a
T ( n
k )= nk
k lg n
k =n lg (n/k )

This condition only holds and is exact hence the power of n/k is 2. From this determination it can
be concluded that the general time complexity of the merge is given by ⊝( nlg n)
(Ratheesh et al., 2016)
iii) The greatest values is given by k=lg n, and through substitution,
⊝ (n lg n+n lg n
lg n )=⊝(lgn),
Suppose k=f (n)> lg n, then the complexity would be given by ⊝( nf (n)) which would be the
running time than merge sort.
Question 4
i) For the given recurrence T (n) = 3T (n/2) + n, a=3, b=4 and f (n) =n. for this case, nlogb a =nlog3 2
due to the fact that f (n) = Ω=(n¿ ¿ log3 2+ ϵ)¿ where ϵ =0.2. this makes it possible to deploy the
case 3 of the master theorem if proving the regularity condition would be possible for f (n). the
solution is T (n) =⊝(f ( n))=⊝( n)
ii) The upper and lower boundaries do not matter when it comes to solving recurrences making it
possible to come up with the recurrence tree for the recurrence equation T (n) = 3T (n/2) + n. to
enhance the convenience of working with numbers that can easily be determined, it is assumed
that n is to an exact power of 2 and this would see all the sizes of the subproblem being integers.
The recurrence tree for T (n) = 3T (n/2) + n is thus as follows:

As can be observed from the recurrence tree, there is a reduction in the sizes of the subproblem
by a constant factor of 2 every step down a level and finally a boundary of T (1) is attained as the
last level of the recurrence tree (Ratheesh et al., 2016). The size of the subproblem for any node
at the second depth i is found to be n/2i when determining the depth of the tree and hence the size
of the subproblem gest to n=1 at the point n/2i or its equivalent at i=lgn. the three therefore
remains to have lgn+1 levels with the depth sequence being 0, 1, 2, 3…, lgn
After determination of the depth of the tree, the subsequent step revolves around the calculation
of the cost at every level of the tree of all the four levels. Being that every level has at least three
more nodes when compared to the preceding level, and thus 3i defines the total number of nodes
at the depth i. the size of each of the subproblem had been established to decrease by a constant
factor of 2 for each of the level as one descends done from the top of the tree; thereby every node
whose depth i for i=0, 1, 2, 3, …, lgn-1 costs n/2i. The total cost is achieved by multiplying the
cost of each node, n/2i, by the total number of nodes, 3i, 3i* n/2i= (3/2) in. at the lowest level of
the tree, when the depth is at lgn, there are 3lgn=nlog3 nodes and each of them contributes a cost T

(1) bringing the overall cost to be nlog3 T (1) (Ratheesh et al., 2016). This is simplified as ⊝( nlg3 )
as it is assumed that T (1) is a constant in the equation hence cancelling out.
Adding up all the costs at every level gives the cost of the entire recurrence tree and it
determined as follows:
T ( n ) =n+ 3
2 n+( 3
2 )
2
n+( 3
2 )
3
n+…+ ( 3
2 )
lgn−1
n+⊝(nlg 3)
¿ ∑
k=0
lgn−1
(3
2 )
k
n+¿ ⊝(nlg3 )¿
=
( 3
2 )
lgn−1
3
2 −1
n+⊝(nlg3 )
=2 nlg 3−2 n+⊝( nlg3 )=⊝( nlg3 )
iii) Proof of answer
for all the integers n, s.t ≥ 1 at the Property P (n)
the presence of a seemingly close match between the form T (n)≤ dnlg 3−cn for some of the
constants d as well as c where c>0 and d>0 gives an impression of a close resemblance of the
recurrence T (n) = 3T (n/2) + n
Question 5
If a vertex i be a universal sink as going by the definition, the i-th column of the adjacency will
all be ‘1’ while the i-th row will all be ‘0’ except for aii entry which there is vividly such a single

of such vertex. The algorithm is then described so as to determine the existence of a universal
sink.
Begin from aii, should a current entry aij be equal to ‘0’, then it translates to j=j+1 (making one
step to the right). Conversely should aij be equal to 1 then it translates to i=i+1 (a single step has
been made downwards). In so doing, a stop will be made of the last row at the entry akn or
otherwise at ank of the last column (n=|V|, 1≦ k ≦∨V ∨¿) (Madala, 2018). The vertex k is
checked if it meets the definition of a universal sink. Should it meet the definition, and then it
was found otherwise there is not a universal sink. Since a step is always made to the right or
down and the checking or determination if a vertex is a universal sink is may be achieved in O
(V), then the total running time would be O (V)
The algorithm returns no vertex in the absence of a universal sink. On the other hand, the path
begins at a11 will absolutely come across the u-th row or u-th column in case of the presence of a
universal sink u at certain entry. As soon as it is on track, it is not able to get off the track and
will eventually stop at the correct entry.

References
Poursina, M. (2016). Extended divide-and-conquer algorithm for uncertainty analysis of
multibody systems in polynomial chaos expansion framework. Journal of Computational
and Nonlinear Dynamics, 11(3), 031015
Ratheesh, A., Soman, P., Nair, M. R., Devika, R. G., & Aneesh, R. P. (2016, July). Advanced
algorithm for polyp detection using depth segmentation in colon endoscopy.
In Communication Systems and Networks (ComNet), International Conference on (pp.
179-183). IEEE