Let G be an arbitrary graph with n nodes and k components.If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between
-
Solution
Vertex is removed, then component between is k + 1 and n – k.
Let T(n) be the number of different binary search trees on n distinct elements.
Then T(n)=\(\sum_{k=1}^{n}\)T(K-1)T(x), where x is
-
Solution
n couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not to accompanies by her husband. The number of different gatherings possible at the party is
-
Solution
n couples means,number of persons in party= 2n.If wife need not accompanied by her husband, then, we choose,2nPn × 2n way gathering possible at the party.
Let A be a sequence of 8 distinct integers sorted in ascending order.How many distinct pairs of sequences, B and Care there such that (i) each is sorted in ascending order, (ii) B has 5 and C has 3 elements, and (iii) the result of merging Band C gives A?
-
Solution
Distinct pairs of sequence B and C = 28= 256.
Let P(E) denote the probability of the event E. Given P(A) = 1,P(B) = 1⁄2, the values of P(A | B) and P(B | A) respectively are
-
Solution
Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___.
-
Solution
Soln :6
Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.
-
Solution
Soln : 358
The implementation of optional alogarith for merging sequences is
as follows :Total no. of comparisons (44 – 1) + (94 – 1) + (65 – 1) + (159 – 1)= 358
Consider two strings A= “qpqrr” and B = “pqprqrp”. Let x be the length of the longest common sub sequence (not necessarily contiguous) between A and B and let y be the number of such longest common sub sequences between A and B. Then x + 10y= ___.
-
Solution
Soln : 34
x →length of longest common sub sequence between A and By →number of longest common sub sequence between A and BA = “qpqrr”B = “pqprqrp”
The longest common sub sequence between A and B is having longest is
∴x = 4
Common sequences are:
1.qpqr2. pqrr3. qprr
∴y = 3
∴x +10y = 4 + 10 × 3 = 34
The maximum number of super keys for the relation schema R(E, F, G, H)with E as the key is _____.
-
Solution
Maximum no. of super keys = 2n–1= 24–1 = 23 = 8
A FAT(file allocation table) based file system is being used and the total overhead of each entry in the FAT is 4 bytes in size. Given a 100 × 106 bytes disk on which the file system is stored and data block size is 103 bytes, the maximum size of a file that can be stored on this disk in units of 106 bytes is____________.
-
Solution