The usual Θ(n2) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If,instead, we use binary search to identify the position, the worst case running time will
-
Solution
If we use binary search then there will be \(\left \lceil log_{2}(n!) \right \rceil\) comparisons in the worst case, which is Θ(n log n) ( If you want to know how \(\left \lceil log2(n!) \right \rceil\) can be equal to Θ(n log n)).But the algorithm as a whole will still have a running time of Θ(n^2) on average because of the series of swaps required for each insertion.
Consider the following graph :Among the following sequences
I.a b e g h
II.a b f e h g
III.a b f h g e
IV.a f g h b e
which are depth first tranversals of the above graph?
-
Solution
depth first traversals of the above graph:
depth first traversals is also called pre-order
I. ab e g hf
III. ab f h ge
IV. af g hbe
Consider the following three claims :
I.(n + k)m= Θ(nm), where k and m are constants
II.2n + 1= O(2n)
Which of these claims are correct?
-
Solution
(n + k)m= Θ(nm), above k and m are constants 2n+1
= O(2n). Where 2 is constant here as 2n+1 is both upper and lower bounded by 2n.
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering of natural numbers. What is the in-order traversals sequence of the resultant tree?
In a bottom-up evaluation of a syntax directed definition,inherited attributes can
-
Solution
A syntax-directed definition is a generalization of a context free grammar in which each grammar or symbol has an associated into two subsets called the synthesized and inherited attributes of that grammar symbol
If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?
-
Solution
The strings of a language L can be effectively enumerated means a Turing machine exists for language L which will enumerate all valid strings of the language. If the string is in lexicographic order then TM will accept the string and halt in the final state. But, if the string is not lexicographic order then TM will reject the string and halt in non-final state.Thus, L is recursive language.
We cannot construct PDA for language L. So, the given language is not context free.
Thus, option (d) is correct.
The regular expression 0* (10*)* denotes the same set as
-
Solution
All string that can be geneuated from given reqular expression can also be generated from this Þ(1 *0)* 1*.
Nobody knows yet if P= NP. Consider the language L defined as follows:
\(L=\left\{\begin{matrix} (0+1)\ast if\: P=NP & \\ \phi \: otherwise & \end{matrix}\right.\)Which of the following statements is true?
-
Solution
In both case( P = NP)or(P! = NP),L is Regular So L is recursive.
Consider an array multiplier for multiplying two n bit numbers.If each gate in the circuit has a unit delay, the total delay of the multiplier is
-
Solution
Number of gates used in ‘n’ bit array multiplier
(n*n)=(2n–1)*, each gate in the circuit has a unit delay.
Total delay =1 * (2n–1) = O (2n–1) = O(n).
Assuming all numbers are in 2’s complement representation,which of the following numbers is divisible by 11111011?
-
Solution
Since most singificant bit is 1, all numbers are negative, 2’s complement of divisor (11111011) =1’s complement + 1 =000001001 + 1 = 00000101. So the given number is = –5.The decimal value of option A is = – 25 so we can say – 25 is divisible by – 5