Ask a question from expert

Ask now

Advanced Algorithm Analysis: Recurrence Trees, Divide-and-Conquer Technique, and Universal Sink

This assignment involves solving three problems related to tree nodes, ordered search tables, and merge sort with insertion sort.

9 Pages2086 Words492 Views
   

Added on  2023-06-04

About This Document

This article covers advanced algorithm analysis topics such as recurrence trees, divide-and-conquer technique, and universal sink. It includes explanations, examples, and proofs. The time complexity of algorithms is also discussed. Course code and college/university are not mentioned.

Advanced Algorithm Analysis: Recurrence Trees, Divide-and-Conquer Technique, and Universal Sink

This assignment involves solving three problems related to tree nodes, ordered search tables, and merge sort with insertion sort.

   Added on 2023-06-04

BookmarkShareRelated Documents
[Author Name(s), First M. Last, Omit Titles and Degrees]
Advanced Algorithm Analysis: Recurrence Trees, Divide-and-Conquer Technique, and Universal Sink_1
Question 1
Suppose nI=1, then it means nE=2nI+1=2+1=3;
Suppose nI=0, then nE=2nI+1=1
Making a presumption that for k’<k, the equation nE holds, an equation provided in the form nI
=k’<k, the condition nE=2nI+1 is true.
Giving consideration to nI=k, then it follows that nE=2(k-1) + (3-1). This is interpreted as the
total external nodes is equivalent to the external nodes composed of k-1 nodes in addition to
3(the addition of 3 refers to the internal nodes that have 3 children) removing 1 (this is a
replacement of the external node that was changed into an internal node when creating a new
internal node). An inference can thus be reached at that nE=2k-2+3=2k+1
Question 2
The algorithm adopts the divide-and-conquer technique. While adopting this divide-and-conquer
technique, an alternation in the lengths of the two sorted arrays T and S is notice. Len (T) is used
in the denotation of the length of T while the length of S is denoted using len (S) at any provided
time.
Any certain iteration given, ms=lens (S)/2 is used in the denotation of the medium index of S
besides medium of S by S[ms]. On a similar note, mT=len (T)/ 2 is used in the denotation of the
medium index of T alongside as the medium of T is denoted by T[mt]. mt+ms and S[ms] can
then be compared against T[mt] that aids in finding the half part i.e. right or left of the arrays i.e.
S or T that may be eliminated or discarded to leave the smaller sub-problems for recursion.
The algorithm
Advanced Algorithm Analysis: Recurrence Trees, Divide-and-Conquer Technique, and Universal Sink_2
1st Condition (ms+mt k)
Condition 1.1 when S[ms] T [mt ]
Discarding of the right larger half of array S may be performed that would mean removal from
S[ms] from the end and thereafter recursive determination of the k-th smallest element that is in
T alongside the left smaller half of S
Condition 1.2 when T[mt]¿ S[ms]
Under this condition, a direct and exact symmetry with condition 1.1 with the arrays T and S
exchanged is noticed
Condition 2 (ms+mt<k):
Condition 2.1 S[ms] T [ mt ]
This condition encompasses the discarding of the left smaller half of T array and then finding the
(k-mt)-th of the smallest element in S alongside in the right large half of array S
Condition 2.2 T[mt]>S[ms]
Similar Condition 1.2, Condition 2.2 has exhibits the exact symmetry with condition 1.1, with
the arrays T and S exchanged
Time complexity: At a specific iteration, discarding of half of some array occurs and thereby the
time complexity becomes O (log (len(S)) +log (len (T))) which can be simplified to O (logn) at
size n as the input of the arrays T and S
Question 3
Advanced Algorithm Analysis: Recurrence Trees, Divide-and-Conquer Technique, and Universal Sink_3

End of preview

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

Related Documents
Advanced Algorithm Analysis - Desklib
|8
|1712
|254

Advanced Algorithm Analysis - Desklib
|9
|2127
|207

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