A binary search tree is generated by inserting in order the following integers: 50, 15, 62, 5, 20, 58, 91,3, 8, 37,60, 24. The number of nodes in the left subtree and right subtree of the root respectively is
The binary search tree is as follows:
The number of nodes in the left subtree and right subtree of the root respectively is (7, 4).
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?
Bellman-Ford algorithm is used to find all pairs shortest distances in a graph and it is dynamic programming technique.
A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?
A B-tree is similar to 2-3 tree. Consider a B-tree of order 4.
A B-tree of order m contains n records and if each contains b records on the average then the tree has about [ n / b ] leaves, if we split k nodes along the path from leaves then
in given problem n = 10, b = 3, m = 4
A problem in NP is NP-complete if
3-SAT being an NPC problem, reducing NP problem to 3-SAT would mean that NP problem is NPC
For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?
X is reducible to NPC.
Hence X is also NPC
Let πA be a problem that belongs to the class NP. Then which one of the following is TRUE?
it is given that πA ∈ NP
∴ If πA is NP-hard, and since it is given that πA ∈ NP , this means that πA is NP-complete
∴ choice (c) is correct.
Notice that choice (a) is incorrect since as P ∈ NP, some NP problems are actually P and hence polynomial time algorithm can exist for these.
Choice (b) is incorrect since, If πA can be solved deterministicaily in polynomial time, it does not generate that P=NP, unless of-course it is additionally known that πA is NP-complete.
Choice (d) is incorrect since,
All problems belonging to P or NP have to be decidable.
The maximum number of edges in a n-nodes undirected graph without self loops is
The maximum number of edges in a n-node undirected graph without self loop i.e., complete graph.
n-node each having degree such each edge so total number of edges =
The average number of key comparisons required for a successful search for sequential search on n items is
Number of comparison in worst case = n
Number of comparison in best case = 1 So, average number of comparison
A complete binary tree with n non-leaf nodes contains
In complete binary tree.
Number of internal nodes = No. of leaf node - 1
So total number of nodes = Internal nodes + Leaf node
Algorithm design technique used in quicksort algorithm is
Quick sort algorithm is based on divide an conquer approach.
Since we conquer the array by dividing it one the basis of pivot elements till the sorted array is obtained