Analysis Of Divide-and-Rule Conquer Method And Recurrence Tree

Describe the Advanced Algorithm Topics For Total External Nodes.

Divide-and-Rule Conquer Method

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 

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)

Condition 1.1 S[ms]

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]

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):

Condition 2.1 S[ms]

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

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 

1. 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
2. ii) Sorting sub lists of a of length k would each take 

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

Recurrence Tree

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 

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  (Ratheesh et al., 2016)

iii) The greatest values is given by k=lg n, and through substitution, 

Suppose k=f (n)> lg n, then the complexity would be given by  which would be the running time than merge sort. 

1. i) For the given recurrence T (n) = 3T (n/2) + n, a=3, b=4 and f (n) =n. for this case, due to the fact that f (n) =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) ==
2. 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/2ⁱ when determining the depth of the tree and hence the size of the subproblem gest to n=1 at the point n/2ⁱ 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 3ⁱ 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/2ⁱ. The total cost is achieved by multiplying the cost of each node, n/2ⁱ, by the total number of nodes, 3ⁱ, 3i* n/2ⁱ= (3/2) ⁱⁿ. at the lowest level of the tree, when the depth is at lgn, there are 3^lgn=n^log3 nodes and each of them contributes a cost T (1) bringing the overall cost to be n^log3 T (1) (Ratheesh et al., 2016). This is simplified as  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: 

iii) Proof of answer

for all the integers n, s.t at the Property P (n)

the presence of a seemingly close match between the form T (n) 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 

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 a_ii 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 a_ii, should a current entry a_ij be equal to ‘0’, then it translates to j=j+1 (making one step to the right). Conversely should a_ij 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 a_kn or otherwise at a_nk of the last column (n=|V|, 1) (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 a₁₁ 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