Advance Algorithm: Divide and Conquer, Recurrence, Universal Sink

This article covers the techniques of divide and conquer, recurrence, and universal sink in advance algorithms. It explains the time complexity and proofs of regularity conditions. It also provides insights into insertion-sort and merging sublists. The article cites various authors and their works on the subject.

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

Question 1
For nI=0, nE=2nI+1=1
For nI=1, then nE=2nI+1=2+1=3
Assuming that the equation nE is true for k’<k, which means for any equation nI =k’<k, the
value of nE=2nI+1
Taking into consideration nI=k, nE=2(k-1) + (3-1). This means that the number of external nodes
is the same as the number of external nodes for a tree that has k-1 internal node + 3 (the addition
of internal nodes which have to have 3 children) subtract 1 (in generating the new internal node,
an external node was made into an internal node). Hence nE=2k-2+3=2k+1 (Ahuja, 2017)
Question 2
The algorithm makes use of the technique of divide-and-conquer. In the course of adoption of the
technique of divide-and-conquer, there will be a change in the lengths of both the sorted arrays T
and S. the length of T (or S) is denoted using len(T) (or len(S))at any given moment (Corke,
2017).
At any provided iteration, the median index of S is denoted using ms=len (S)/2 as well as the
medium of S by S[ms]. On the same note, the median index of T is denoted by mT=len (T)/2 as
well as the medium of T by T[mt]. a comparison can then be made between mt+ms and S[ms]
with T[mt] in the determination of which (right or left) half part of which of the arrays (S or T)
may be removed and then the smaller sub-problem be left for recursion (Evans, 2017)
The algorithm

Condition 1(ms+mt≥ k)
1.1 Condition 1.1 S[ms]≥ T [mt ]
The right bigger half of array S can be removed i.e. from S[ms] to its end and thereafter
recursively find the k-th smallest element in T and as well as the left smaller half of S
1.2 Condition 1.2 T[mt] ¿ S[ms]
It is exactly symmetric with Condition 1.1, having T and S exchanged
Condition 2 (ms+mt<k):
2.1 Condition 2.1 S[ms]≥ T [ mt ]
The left smaller half of array T can be discarded and the recursively determine the (k-
mt)-th smallest element in S and in the right larger half of S (Rao & Yip, 2014)
2.2 Condition 2.2 T[mt]>S[ms]
This condition is exactly symmetric with Condition 1.1, having T and S exchanged
Time complexity:
At every iteration, half of some array is discarded and thus the time complexity is O (log (len(S))
+log (len (T))) which is O (logn) for the input arrays T and S of size n
Question 3
i) Each sub list that has a length of k takes Ɵ (k2) worst-case time with the aid of Insertion-Sort.
In order to sort n/k it takes n/k* Ɵ (k2) = Ɵ (nk) as worst-case time for such sub lists

ii)
 Ɵ(n) worst-case time is taken in merging n/k sub lists to form n/2k sub lists
 Ɵ(n) worst-case time is taken in merging n/2k sub lists to form n/4k sub lists
 Ɵ(n) worst-case time is taken in merging n/4k sub lists to form n/8k sub lists and so on
 Generally, merging 2 sub lists into a single list requires Ɵ(n) worst case time
 For the case of lg(n/k) merges, n/k can be merged into one list and would require Ɵ(n
lg(n/k)) as the worst case time (Leighton, 2014)
iii)
to have Ɵ (nk+n lg (n/k)) =Ɵ (n lg n), either of the conditions n lg (n/k) =Ɵ (n lg n) or nk=Ɵ (n
lg n) has to be met. Following the preceding two possibilities, it is known and deducible that the
largest asymptotic value of k is Ɵ (lg n)
Question 4
i)
T (n) = 3T (n/2) + n
For this recurrence, a=3, b=2, f (n) =n and hence we have nlogb a =nlog3 2, since f (n) =
Ω=(n¿ ¿ log3 2+ ϵ )¿ in which ϵ =0.2, case 3 can be applied of the master theorem should it be
possible to show that the regularity condition holds for f (n)
Showing that the regularity condition holds calls for a proof of af(n/b)≤ cf (n) for a constant c<1
and all sufficiently large n. if this can be proved, then a conclusion can be made than T (n)=
⊝( f ( n)) using case 3 of the master theorem (Xu & Xu, 2016)

Proof of the condition being regular
af (n/b) =3(n/4)≤ cf ( n ) for c=0.7 and ≥ 2
A conclusion can thus be arrived at that the solution is T (n) =⊝( f ( n))=⊝( n)
ii)
since the ceilings and the floors are often not very necessary in the solution of recurrences, a
recurrence tree can be created for T (n) = 3T (n/2) + n
in the table, it is assumed that n is an exact power of 2 for the purposes of convenience to ensure
that all the subproblem sizes will be integers
Since the sizes of the subproblem are decreasing by a factor of 2 every time there is a one level
reduction, a boundary condition of T(1). The size of the subproblem for a single node at a depth i
is found to be n/2i in the determination of the tree depth. This makes the subproblem to attain
n=1 at the point n/2i=1 or its equivalent at the point i=lgn. Hence the tree will be having lgn+1
levels (the depths running from 0, 1, 2, 3…, lgn)

The next step involves the determination of the cost at each of the tree levels. Since each of the
levels is having thrice more nodes that the preceding level, the number of nodes will be 3i at
depth i. since there is a reduction by a factor of 2 for every level of the subproblem sizes down
from the roots, the cost of each of the nodes at a depth i where i=0,1,2,3,…, lgn-1 is determined
using the equation 3i* n/2i=(3/2)in. at the bottom level when the depth is lgn, 3lgn=3lg3nodes with
each of the nodes contributing a cost T(1) for an overall cost of nlg3 T(1) i.e. ⊝(nlg3) as an
assumption that T(1) is a constant
To find the cost of the whole tree, the costs over all the levels are added up
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)
To verify the answer, for all integers n, s.t≥ 1, the property P (n)
there seems to be a match between the closed form T (n)≤ dnlg 3−cn for certain constants d and c
s.t d>0 and c>0 resemble the recurrence T (n) = 3T (n/2) + n

Question 5
Should a vertex i be a universal sink as per the definition, the i-th row if the adjacency will all be
‘0’ while the i-th column will all be ‘1’ with the exception of 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 means j=j+1 (taking one step to
the right), while should aij be equal to 1then it means i=i+1 (a single step has been taken
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 (Pinedo, 2016).

References
Ahuja, R. K. (2017). Network flows: theory, algorithms, and applications. Pearson Education
Corke, P. (2017). Robotics, Vision and Control: Fundamental Algorithms In MATLAB® Second,
Completely Revised (Vol. 118). Springer
Evans, J. (2017). Optimization algorithms for networks and graphs. Routledge
Leighton, F. T. (2014). Introduction to parallel algorithms and architectures: Arrays· trees·
hypercubes. Elsevier
Madala, H. R. (2018). Inductive Learning Algorithms for Complex Systems Modeling: 0. cRc
press
Pinedo, M. L. (2016). Scheduling: theory, algorithms, and systems. Springer
Rao, K. R., & Yip, P. (2014). Discrete cosine transform: algorithms, advantages, applications.
Academic press
Xu, G., & Xu, Y. (2016). GPS: theory, algorithms and applications. Springer