Algorithms: Internal Node Children, Kth Smallest Key, Sorting, Recurrence, Adjacency Matrix

ALGORITHMS
By:
The Name of the class:
Professor:
The Name of The School:
The City and State where it is located:
The Date:

1.show if every internal node has exactly 3 children
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(sm) 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
3.
a) sorting the sub lists
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