Test: Dynamic Programming, P & NP Concepts- 1 - Computer Science Engineering (CSE) MCQ

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).

Bellman-Ford algorithm is used to find all pairs shortest distances in a graph and it is dynamic programming technique.

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

so,

3-SAT being an NPC problem, reducing NP problem to 3-SAT would mean that NP problem is NPC

X is reducible to NPC.
Hence X is also NPC

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-node undirected graph without self loop i.e., complete graph.
n-node each having degree  such each  edge so total number of edges = 

Number of comparison in worst case = n

Number of comparison in best case = 1 So, average number of comparison

In complete binary tree.
Number of internal nodes = No. of leaf node - 1
So total number of nodes = Internal nodes + Leaf node

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