Finding The Kth Smallest Key And Relationship Between Internal And External Nodes In A Tree

For a tree T, let nI denote the number of its internal nodes, and let nE denote the number of its external nodes. Show that if every internal node in T has exactly 3 children, then nE = 2nI + 1.
2. Suppose we are given two ordered search tables S and T, each with n elements (with S and T being implemented with arrays). Describe an O(lg2n)-time algorithm for finding the kth smallest key in the union of the keys from S and T (assuming no duplicates). 

3. Although merge sort runs in(n lg n) worst-case time and insertion sort runs in (n2 ) worst case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort within merge sort when sub problems become sufficiently small.Consider a modification to merge sort in which n/k sub lists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to
be determined.

i) Show that the n/k sub lists, each of length k, can be sorted by insertion sort in(nk) worst-case time. 
ii) Show that the sub lists can be merged in worst-case time. 
iii) Given that the modified algorithm runs in (nk + n lg(n/k)) worst-case time, what is the largest asymptotiction) value of k as a function of n for which the modified algorithm has the same asymptotic running time as standard merge sort.

Relationship between internal and external nodes in a Tree

When nI = 1, then nE = 2nI + 1 = 2+1=3.

 When  nI = 2, then nE = 2nI +1 = 4+1 = 5.

Let’s propose that the equation nE is correct for k’< k, that is, for any nI = k’< k, nE = 2nI +1.

Now let’s consider k= nI. Then, 2(k − 1) + 1 + (3 − 1) is equals to nE.  The number of nodes which are external   is equal to the nodes which are external fora tree with k − 1 internal nodes plus 3 (we added an internal node which must have 3 children) minus 1 (in creating the new internal node, we made an external node into an internal node). Thus, nE = 2k − 2+ 3 = 2k + 1.

In a case where by three externals and 1 root => 3=2*1+1

Let’s Assume true n nodes in a given tree whereby: ne = 2ni + 1.

• A tree can have extended by addition of new nodes:

1. We are unable to add only 1 node without the violation of three--ary tree  property

2.only two nodes cannot be added cannot be added without the violation of the three-ary for Addition of 3 nodes all must be external.

• In such a case, one old external becomes internal, therefore we have: ni-new = ni +1

ne-new = ne-1+3 = 2ni +3

 = (2ni +2) +1 = 2(ni +1) + 1

= 2ni-new+1

• Therefore ne-new = 2ni-new +1

-new in both sides cancels

Then Ne=2ni+1

2. an O(lg2n) time algorithm for defining kth smallest key.

The algorithm applies the divide-and-conquer technique to find the kth smallest key. In process of divide-and-conquer, the sizes of arrays SS and TT which are both sorted will change. We indicate the length of TT (or, SS) by len(T)len(T) (or len(S)len(S)).

Notations and Basic Idea:

median index of SS should be denoted by sm?len(S)/2sm?len(S)/2 and the median of SS by S[sm]S[sm] At any iteration. Likewise, the median index of TT should be denoted by tm?len(T)/2tm?len(T)/2 and the median of TT by T[tm]T[tm].

The basic idea says that we do the comparison of sm+tmsm+tm with kk and S[sm]S[sm] with T[tm

for the determination of which half part either right or right of which (T or S) array can be discarded and the small sub-problem can be left to recursion.

The algorithm

1.case one (sm+tm≥ksm+tm≥k

Here we have to scenarios   where by :

Case 1.1 S[sm]≥T[tm]S[sm]≥T[tm].

The right bigger half of array S can be discarded that is from S(s_m) to its end. Recursively the k-th

 Can be found by the left smaller half of S and the Smallest element of T.T and S are exchanged case 1.1 symmetric.

The second scenario  

Case 1.2  
S[sm] is greater than S[sm]T[tm]  and S[sm]T[tm] is greater than  T[tm].

2. case 2 (sm+tm<ksm+tm<k):

The first scenario case 2.1 T[tm]≤. T[tm]S[sm]≤ S[sm]

Array’s left smaller half can be discarded. Recursively (k−tm)(k−tm)-th 

The right larger half of S and the smallest element of S can be found.

The second scenario 2.2 T

[tm]>S[sm]T[tm]>S[sm].

Time complexity

Half of some array are discarded at each iteration. Therefore   time complexity is O(lg(len(S)) +lg(len(T))), which is O(lgn)  for the input arrays T and S of n in size                                                                                                                    

1. a) sorting the sub lists

Finding the kth smallest key in Search Tables S and T

When inputting values of K in size, insertion sort in the worst –case time runs on Θ(k2). The equation of the form (ak2+bk+c) usually gives the running time.   the running time of the form Therefore, time which is worst-case is essential in sorting of the sub lists which are in form of n/k. each of k in length in the insertion sort:

T(k)=nk(ak2+bk+c)=ank+bn+cny

Where by y is an integer which is usually less than n. Therefore, to get bigger values of n, the last two term of T(k) can be ignored. Hence T(k)=Θ(nk).                                                                         

1. b) a merging the sublists.

we are having n elements; we divide into sub lists of k each of them into n/k sorted sublists in length. We take two sub lists simultaneously carry on with combining   them to enable us merge the n/k sorted sublist into a single list of n in length which is sorted. This results into
log(n/k)log .And  for   each  step n elements are been compared  ,hence  the entire procedure whole runs at Θ(nlg(n/k)).

c)The biggest value in k

when a set of rules are modified for them to be having similar asymptotic time of running as the one for ordinary com

Solution.

bination so,Θ(nlgn) must be similar to Θ(nk+nlg(n/k)) =Θ(nk+nlgn−nlgk)

in order to content this state, k should not grow asymptotically faster than lg n this is because when k grow faster than lg n, the set of rules will speed at worst asymptotic time than Θ(nlgn) because of the nk term. We need to consider for the state   k=Θ(lgn), requirements cling to or do not.

Let’s propose, k to be equal to Θ (lg n)

Θ(nk+nlg(n/k)) =Θ(nk+ n lgn−n lgk)

=Θ (n lg n +n lg n−n lg (lg n))

=Θ (2n lg n−n lg(lgn)) †

=Θ (n lg n)

†lg(lgn) is smaller compared to lg n for bigger quantities of n.

4.a) Recurrence

The recurrences of such form are applicable in master theorem

T(n)=At(n/b) +f(n)

In a case where a is greater or equals to one and b is greater than one they are continual and the function f(n) is an asymptotically useful role. we have three scenarios:

case 1: A function f(n)= O (n log b^a-e) for a particular continual E> 0, then T (n) = Θ (n log b ^a)

Scenario 2. A function f(n) = Θ (^{nlogb a} log^k n) having 1 k ≥ 0, then T (n) = Θ (n^{logb a}   log^k+1 n).

Scenario 3.A function f(n)= = ? (n logb a+e) having the e>0, and function f(n) satisfying the uniformity state, Therefore T (n) = Θ(f(n)).

The uniformity state, states that:af(n/b) <= cf(n) for a certain continual c<1 and every that are sufficiently bigger than n.

T (n) = 3T (n/2) + n =⇒ T (n) = Θ (n lg 3 )

ii)recursion tree

The recursion tree depth:

n (1/2) =1

n=2ⁱ

ⁱ⁼log 2 n=lgn

hence

T (n)  +3^{lg n}   = note: 3^{lg n} =n ^{lg 3}  and

 T(n)=n[(3/2)^{lg n} -1/(3/2)-1] +n^{lg 3}

T(n)=n/2[(3/2)^{lg n} -1]+ n^{lg 3}

T(n)=n/2[n^lg(3/2)-1]+n^{lg 3}

T(n)=1/2n^1+lg(3/2) –n/2+ n^{lg 3}

T(n)=1/2n^{lg 3} –n/2+ n^{lg 3}

               T(n)≤1/2 n^{lg 3}   if  -n/2+ n^{lg 3} ≥ 0

n^{lg 3-1≥}≥1/2

T(n)=O(n^{lg 3})

We will choose C large so that:

T(1)=3T(?1/2?+1=m 3T (0)+1=1≤(1) ^{lg 3}

T (2) =3T (?2/2?) +2=3T (1) +2=5≤ c (2) ^{lg 3}

This holds for c ≥2

Substitution

T(n)=3T(?n/2?) +n

T(n)≤3c (n/2) ^{lg 3} +n

T(n)=3cn^{lg 3}-2^{lg 3}+n

T(n)=3cn^{lg 3}+n

T(n)≤cn ^{lg 3}

5.Adjacency-matrix

According to the definition if a vertex I is a universal sink, the adjacency-matrix will be zero for the ith row and one for the i-th column except in entry a_{ii and} a such vertex is only one. To be able to find out if a universal sink really exist we then relate an algorithm for the same.

Starts from a₁₁. we take one steep right if the current entry a_ij is equals to zero then j=j+1; if   a_{ij is} equal to 1 the for i=i+1 we take one step downwards. By doing these we will terminate at akn ingress of the utmost cordon or a_{kn of} the last pier (n is equal to /V/,1 is equal to or less than k and k is equal to or less than /v/). Starting by checking if the definition of universal sink is satisfied by vertex k, if it is the we have found it, and if we cannot find it then there is no universal sink. The total running time is given by O(V). Because we do consistently make a pace down or right, then examining if an apex is a universal sink can be done in O(V).

No any vertex will be returned by this algorithm if there is no universal sink. The path that starts from a₁₁ will meet the u-th row or the u-th column at some entry if there is a universal sink u. Once it’s on the track it cannot really get out of the track and will stop finally at the right entry.

References

Motwani, R., & Raghavan, P. (2010). Randomized algorithms(pp. 12-12). Chapman & Hall/CRC.

Ali, K. H., Styczynski, Z. A., Shah, M. A., & Ramzan, M. (2014, December). Comparison between two types of approaches matrix based and tree based to check connectivity between nodes of a power system network. In Multi-Topic Conference (INMIC), 2014 IEEE 17th International (pp. 494-499). IEEE.