Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of k colours,such that the colour-pairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. The minimum value of k that satisfies this requirement is _____
-
Solution
Want to paint 52 with k-color no adjacent letter will have the same colour. This problem is 9 colourable, so k= 9
Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?
f1(n)= 2n f2(n) = n3/2
f3(n) = n log2 nf1(n) = nlog2n
-
Solution
Four matrices M1, M2, M3 and M4 of dimensions p × q, q × r,r × s and s × t respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as ((M1 × M2) × (M3 × M4)), the total number of scalar multiplications is pqr + rst + prt. When multiplied as (((M1 × M2) × M3) × M4), the total number of scalar multiplications is pqr + prs + pst.
If p= 10, q = 100, r = 20,s = 5, and t = 80,then the minimum number of scalar multiplications needed is
-
Solution
Multiply as (M1 × (M2 × M3 )) × M4 Total number of scalar multiplication is
= qrs + pqs + pst
= 10000 + 5000 + 4000= 19000
What is the probability that a divisor of 1099 is a multiple of 1096?
-
Solution
What is the value of \(\underset{n\rightarrow \infty }{lim}\)?
-
Solution
In the given figure, a DFA M has start state A and accepting state D. Which of the following regular expressions denotes the set of all words accepted by M?
-
Solution
Minimum string that it will accept = 011 and it will always be in end but as at state A and B there are looping of 1 and 0. So, it will accept (0/1)*.
∴ Regular expression = (011) * 011
Language L1 is polynomial time reducible to language L2.Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are true?
-
Solution
L2 ≤ pL4
L1 ≤ pL2
If L4 ∈ P
then L2 ∈ P
L1 ∈ P,
Hence option (c).
Consider the following :
int fun (int n)
{ if (n%2 == 0)
return n;
else return (2* fun (n – 1);
}
What is the worst case time complexity of given function ?
-
Solution
Loop terminate in O(1) time if n is even and O(2) time if n is odd.
An algorithm is made up of two modules M1 and M2. If order of M1 is f(n) and M2 is f ‘(n), then the order of the algorithm is
-
Solution
We know that, the order of the algorithm is equivalent to the total sum of the order of that modules.
So, the order of given algorithm
= Order of module M + Order of module M2
= f(n) + f '(n)
To insert n random elements into an initially empty Binary Search Tree (BST) for n≥1, the running time is
-
Solution
The procedure of inserting an element in the binary search tree takes O (h) time, where h is the height of the tree.It is known that the expected height of a randomly built binary search tree on n keys is O (log n).
∴ The running time to insert an element = O(h)= O(log n)