Question 1
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)
1.1 Condition 1.1 S[ms]
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]
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]
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)
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
T (n) = 3T (n/2) + n
For this recurrence, a=3, b=2, f (n) =n and hence we have, since f (n) = 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) for a constant c<1 and all sufficiently large n. if this can be proved, then a conclusion can be made than T (n)= using case 3 of the master theorem (Xu & Xu, 2016)
Question 2
Proof of the condition being regular
af (n/b) =3(n/4) for c=0.7 and
A conclusion can thus be arrived at that the solution is T (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
iii)
To verify the answer, for all integers n, s.t, the property P (n)
there seems to be a match between the closed form T (n) 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) (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
Order an Essay Now & Get These Features For Free:
Turnitin Report
Formatting
Title Page
Citation
Outline
