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

Number of spanning tree possible with n-node = n^{n - 2}.
Given, n = 7
Total number of spanning trees = 7⁵

Given array:

So, the order of elements after second pass of the algorithm is 8,15,20,47, 4,9,30,40,12,17,

Worst case time complexity of Quick sort = O(n²) when input is already sorted.
Worst case time complexity of Heap sort = O(n log n).
Worst case time complexity of Merge sort = O(n log n).

An articulation point (or cut vertex) is that vertex removing which (along with its edges) disconnects the graph.

Therefore number of articulation points is 3.

Post order traversal = ab - cd*+. As we know that post order traversal goes in the order of
LEFT CHILD → RIGHT CHILD → PARENT (ROOT)

Hence, Label of 4, 5, 2 will be a, b, - respectively
Labe! of 6, 7, 3 will be c, d, * respectively
Label of 1 will be +

The corresponding expression is - (- a - b) + e!.
This is 1 if a = - b and e is either 1 or 0, since 1! = 0! = 1.

All pairs shortest path is find using Floyd Warshall algorithm, which is an example of dynamic programming.
• Quick sort and merge sort are example of “divide and conquer” algorithms.
• MST or minimum weight spanning tree is a tree with a subset of edges such that it connects all vertices and summation of edge weight is minimum Prim’s algo and Kruskal’s algorithm are used for this, which are examples of greedy approach.
• By using Depth First Search (DFS) one can easily find set of connected components.

Since the tree is used for sorting hence taking INORDER TRAVERSAL (Left-Root-Right) we have 8 placed at the left child of the node labeled 10.

The default order of B-tree is maximum number of pointer in any node.

If the depth is d, the number of nodes n will be 2^{(d+ 1)} - 1.
So, n + 1 = 2^(d+1)
or, d = log (n + 1 ) - 1