Ask a question from expert

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

This assignment consists of three questions related to tree nodes, ordered search tables, and merge sort. The questions aim to evaluate and improve critical thinking, problem solving, and coding skills.

8 Pages2224 Words310 Views

This article discusses algorithms for internal node children, kth smallest key, sorting, recurrence, and adjacency matrix. It explains the time complexity and recurrence tree depth. The article also provides insights from references.

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

This assignment consists of three questions related to tree nodes, ordered search tables, and merge sort. The questions aim to evaluate and improve critical thinking, problem solving, and coding skills.

BookmarkShareRelated Documents
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 smlen(S)/2smlen(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 tmlen(T)/2tmlen(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+tmksm+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 (ktm)(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

## End of preview

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

Related Documents
|8
|1956
|422

|9
|1953
|138

|8
|1712
|254

|9
|2127
|207

|9
|2086
|492

### Support

#### +1 306 205-2269

Chat with our experts. we are online and ready to help.