Ask a question from expert

Ask now

Advanced Algorithm Analysis - Desklib

Answer to Practical 8 – Advanced Algorithm Analysis (CP5602)

9 Pages2127 Words207 Views
   

Added on  2023-06-04

About This Document

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 - Desklib

Answer to Practical 8 – Advanced Algorithm Analysis (CP5602)

   Added on 2023-06-04

BookmarkShareRelated Documents
[Author Name(s), First M. Last, Omit Titles and Degrees]
Advanced Algorithm Analysis - Desklib_1
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).
Advanced Algorithm Analysis - Desklib_2
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
Advanced Algorithm Analysis - Desklib_3

End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents
Advanced Algorithm Analysis: Recurrence Trees, Divide-and-Conquer Technique, and Universal Sink
|9
|2086
|492

Advanced Algorithm Analysis - Desklib
|8
|1712
|254

Advance Algorithm: Divide and Conquer, Recurrence, Universal Sink
|8
|1956
|422

Advanced Algorithm Analysis: Techniques, Complexity, Recurrence, and Universal Sink
|9
|1953
|138

Algorithms: Internal Node Children, Kth Smallest Key, Sorting, Recurrence, Adjacency Matrix
|8
|2224
|310