# Recent activity by Mr_22B

1
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
2
Consider a RISC machine where each instruction is exactly $4$ bytes long. Conditional and unconditional branch instructions use PC-relative addressing mode with Offset specified in bytes to the target location of the branch instruction. Further the Offset is always with respect to ... $i,$ then the decimal value of the Offset is ____________ .
3
Consider the following grammar: stmt $\rightarrow$ if expr then expr else expr; stmt | $0$ expr $\rightarrow$ term relop term | term term $\rightarrow$ id | number id $\rightarrow$ a | b | c number $\rightarrow [0-9]$ where relop is a relational operator (e.g.. $<$ ... example. the program if $e_1$ then $e_2$ else $e_3$ has $2$ control flow paths. $e_1 \rightarrow e_2$ and $e_1 \rightarrow e_3$.
4
Consider a Binary Search Tree is created using element 1 to n in following order: 3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, ....., n – 3, n – 4, n – 5, n – 2, n – 1, n What is the worst time complexity of searching a number in the Binary Search Tree?
$S \rightarrow aBA$ $A \rightarrow \epsilon$ $B \rightarrow a$ Here in the given grammar, what will be the look ahead of B's production:- $S \rightarrow a.BA , \$ B \rightarrow .a \text{ , X}$What will come at the place of X, I think it should be "\$", As $A \rightarrow \epsilon$, So, B's lookahead should be \$. right? 1 answer 7 Boolean expression Y+(X+Y)+(X+Y')(X'+Y) IS equivalent to A)X'Y B) XY' C)Y D)X'Y' please explain i think ans is 1 but ans is given as C 1 answer 8 I read some where that if thier is one comparision at any time then only CFL otherwise CSL? plz give proof. 2 answers 9 2 answers 10 What is the time complexity to insert a new Node in a singly circular linked list at Starting ? (Number of nodes in list = N) A. O(1) B. O(N) 1 answer 11 The number of ways we can insert 11, 12, 13, 14, 15, 16, 17 in empty binary search tree such that resulting tree has the height of 6 = ___________ [height of a tree with single node is 0.] 1 answer 12 What will be complexity to reverse the directed graph?(By reverse i mean reverse direction of all edges).Assume graph is represented by adjacency list. i) No extra space ii)May use extra space 1 answer 13 E-->TE/a T-->ET/b first set of E and T?? 1 answer 14 https://www.youtube.com/watch?v=Z4rgivgkNVc&t=1s anyone please tell me if i choose f instead of b at 7:21 then answer will be different there are so many different answers possible here ?? 0 answers 15 When should one stop preparing a subject? Gate has a huge syllabus. Even in a single subject a lot of topics are there. Obviously one must understand the basics of all topics. But my question is at what point should one be satisfied with a subject preparation and ... find more questions to solve. This question is specially for people who had sat for gate before and secured a good rank. Thanks. 2 answers 16 (1). Both BFS and DFS require$\Omega (N)$storage for their operation. (2). If we double the weight of every edge in the Graph shortest path between any two vertices will not change. Which of the following is/are True ? (and in every question of shortest path we have to think about negative weight ?) 2 answers 17 2 answers 18 In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by (A) Dijkstra's algorithm starting from S (B) Warshall's algorithm (C) performing a DFS starting from S (D) performing a BFS starting from S 3 answers 19 Consider n elements that are equally distributed in k stacks. In each stack, elements of it are arranged in ascending order (min is at the top in each of the stack and then increasing downwards). Given a queue of size n in which we have to put all n elements in increasing order. What will be the time complexity of the best known algorithm? 4 answers 20 Consider the quick sort algorithm on a set of$n$numbers, where in every recursive subroutine of the algorithm, the algorithm chooses the median of that set as the pivot. Then which of the following statements is TRUE? The running time of the algorithm is$\Theta (n).$The running time ... algorithm is$\Theta (n^{1.5})$. The running time of the algorithm is$\Theta (n^{2})$. None of the above. 1 answer 21 can masters theorem be used when base condition is given in a recurrence ? can we directly apply masters theorem to any recurrence ? 6 answers 22 Let$n = m!$. Which of the following is TRUE?$m = \Theta (\log n / \log \log n)m = \Omega (\log n / \log \log n)$but not$m = O(\log n / \log \log n)m = \Theta (\log^2 n)m = \Omega (\log^2 n)$but not$m = Ο( (\log^2 n)m = \Theta (\log^{1.5} n)$10 answers 23 Consider the following functions$f(n) = 3n^{\sqrt{n}}g(n) = 2^{\sqrt{n}{\log_{2}n}}h(n) = n!$Which of the following is true?$h(n)$is$O(f(n))h(n)$is$O(g(n))g(n)$is not$O(f(n))f(n)$is$O(g(n))\$