# Recent exams in GATE

## Select an Exam

 Exam Category Select GATE ISRO TIFR UGC NET GATE Overflow Tests Tests by Mentors External Tests Exam Type Full Length Random Subject Wise
1
Clcok frequency becomes low means time period of clock becomes high. When this time period increses beyond the time period in which the non-volatile memory contents must be refreshed, we loose those contents. So, clock frequence can't go below this value. The ... or else will loose their contents. Non-volatile memory are being developed and computers in future should be tailor made for that.
2
okay. You may use <> in the toolbar to output code properly :)
3
yes,,the line upto "count=count+1" is in the loop...
4
Increment of count must be inside the loop rt?
5
def brian(n): count = 0 while ( n != 0 ) n = n & ( n-1 ) count = count + 1 return count Here n is meant to be an unsigned integer. The operator & considers its arguments in binary and computes their bit wise AND. For example, 22 & 15 gives 6 ... of 15 is 00001111, and the bit-wise AND of these binary strings is 00000110, which is the binary representation of 6. What does the function brian return?
6
60 Marks, 108 Minutes, 40 Questions
7
60 Marks, 108 Minutes, 40 Questions
8
how can we eliminate option B unless we draw it actually...just because of argument of 'stronger answer' ?
9
60 Marks, 108 Minutes, 40 Questions
10
Let $n$ be the number of vertices. Total number of incoming edges $= 7 \times n$. This should be equal to the total number of outgoing edges. So, either all vertices must have 7 edges leaving or some should have more than 7 leaving while others could have less than 7 ... leaving it. So, (c) is the correct answer. Only if we restrict $n$ to 8, exactly seven edges need to leave every vertex.
11
It is true for big O. But for $\Theta$ notation can we say $n! = \Theta (n^n)$?
12
70 Marks, 126 Minutes, 40 Questions
13
Yes, result. I will correct the statement. Thanks.
14
60 Marks, 108 Minutes, 40 Questions
15
60 Marks, 108 Minutes, 40 Questions
16
Why you say it is a condition? It is the result of pumping lemma rt?
17
That's a perfect explanation.
18
n! corresponds to n*(n-1)*(n-2)*....*1 which is $\Theta (n^n)$. So by taking $\log$ to both terms, the answer comes out to be $\Theta(n \log n)$.
19
45 Marks, 81 Minutes, 30 Questions
20
(B)1, 3 and 4 only As from the given options, Myhill-Nerode theorem is useful by providing necessary and sufficient condition for proving that a language regular. Pumping lemma is often used to prove that a language is non-regular. Drawing an NFA can be useful to prove a language is regular. Forming a regular expression can also help us prove if it is a regular language
21
(C) $\forall i \in N, xy^iz \in L$ This is the result of Pumping Lemma for regular language
22
General aptitude is a vast area but for GATE they ask only from a small section which is clearly mentioned in GATE syllabus. Many people won't prepare for these but it is advisable to just read the sections mentioned in GATE syllabus from a recommended book ... from one of the recommended books such as Kenneth H. Rosen. For more books: http://gatecse.in/gatecse/index.php?title=Best_books_for_CSE
23
Which of the following are useful in proving a language to be regular? Myhill-Nerode theorem Pumping lemma Drawing an NFA Forming a regular expression (A) All of these (B) 1, 3 and 4 only (C) 2, 3 and 4 only (D) 3 and 4 only
24
Let $L$ be a regular language and $w$ be a string in $L$. If $w$ can be split into $x, y$ and $z$ such that $|xy| \leq$ number of states in the minimal DFA for $L$, and $|y| > 0$ then, (A) $\forall i \in N, xy^iz \notin L$ (B) $\exists i \in N, xy^iz \in L$ (C) $\forall i \in N, xy^iz \in L$ (D) $\exists i \in N, xy^iz \notin L$
25
is wrong. Microprogrammed CU can never be faster than hardwired CU. Microprogrammed CU it has an extra layer on top of hardwired CU and hence can only be slower than hardwired CU. is a suitable answer as we can add new instruction by changing the content of control ... control makes more sense. control unit can also be hardwired, so this is also not correct. Reference: Slides Correct Answer: $B$
26
45 Marks, 85 Minutes, 29 Questions
27
46 Marks, 85 Minutes, 30 Questions
28
Yes. That was a bad mistake. I have corrected it :)
29
First we need to find different number of inputs for $f$ given that permutations are equivalent. Now given two binary string $x,y$: $x$ is a permutation of $y$ iff $x$ has same number of ones and zeros as $y$. So the total number of different inputs is n+1 ( namely input with ... $2^{n + 1}.$
30
A function $f:\left\{0, 1\right\}^{n}\rightarrow \left\{0, 1\right\}$ is called symmetric if for every $x_{1}, x_{2},....,x_{n} \in \left\{0, 1\right\}$ and every permutation $\sigma$ of $\left\{1, 2,...,n\right\}$ ... $2^{n+1}$ $2^{n}$ $2^{2n}/n!$ $2^{2n}$ $n!$
31
Answer should be (D). We first find $a$ in the BST in $O(\log n)$ time. Now there are two possibilities, b can be in the right subtree of $a$ or b can be in the right subtree of any of the parents of $a$. For the first case, we simply search for $b$, in the right ... $N(x)$ denote the no. of elements in the subtree rooted at $x$ and if LEFT(a), RIGHT(b) returning 0 for NULL.
32
44 Marks, 80 Minutes, 29 Questions
33
Complexity of the algorithm is $O(n)$ and is irrespective of the success of if case as both if as well as else is $O(1)$ operation. If you say exactly, the complexity in terms of comparisons will be 1. $n-n/2-1$ (number of elements for which first if succeeds) $+ 2 \times (n/2)$ (number of elements for which first if fails) $= 3n/2 -1$ 2. $(n-1)/2 + 2\times (n-1)/2$ $=3(n-1)/2$
34
51 Marks, 95 Minutes, 34 Questions
35
50 Marks, 90 Minutes, 33 Questions
36
45 Marks, 80 Minutes, 30 Questions
37
45 Marks, 80 Minutes, 30 Questions
38
55 Marks, 100 Minutes, 34 Questions
39
61 Marks, 110 Minutes, 37 Questions
40
Np. Anyway good to highlight the "polynomial time" :) Reduction of an NPC problem to a P problem (in polynomial time) would imply 2 things: 1) All problems in NP are reducible to this problem in P because all NP problems are reducible to NPC problems. 2) We can ... by definition of class P. This implies that all problems in NP are solvable in polynomial time, or NP = P Thats the exact answer :)
41
42
57 Marks, 100 Minutes, 37 Questions
43
Simple linear search to find max min algo maxmin(a,n,max,min) { max=min=a[1]; for i=2 to n do { if a[i]>max then max:=a[i]; else if a[i]<min then min:=a[i]; } } 1.Average case complexity of the above algo given that the first if conditions fails for n/2 elements 2.Average case complexity of the above algo if the first condition fails 1/2 times plz xplain
44
(All reductions in polynomial time) is mentioned in the question :)
45
Option B is the most correct answer. (To know why it is not THE correct answer read the tail section of this answer) The reasons are as follows. A problem p in NP is NP-complete if every other problem in NP can be transformed into p in ... The answer is partially correct because when we say reduction, we usually mean polynomial time reduction, but neverthless it doesnt hurt to be precise.
46
These two links are very good for paging. https://courses.cs.washington.edu/courses/cse451/08wi/os-paging.ppt http://www.cs.columbia.edu/~junfeng/10sp-w4118/lectures/l21-page.pdf
47
Actually many NP problems have been reduced to P problem (like Primality testing) and still P=NP? is an unsolved problem. Only if we can reduce all NP problems to P, we can say P=NP. And that is the main reason why NP-Complete class is formed. You can read the definition of NP-Complete once more and everything will be clear.
48
That's correct. But why?
49
Thats a very good guess and based on the choice it is correct. But had the choice contained "None of these" it wouldn't work :) The answer is there in the definition itself of NPC..
50
Acc to me Answer Should be option (B) Explanation : P=NP is true only when NP-complete can be reducible to P
51
68 Marks, 120 Minutes, 40 Questions
52
i think option A is abosolute correct and i have some doubt on option B, because NPC represents hard problems soving in non deterministic time is there anything we can able to say NP=NPC
53
$I_1$ is a correct inference. $I_2$ is not a correct inference as it was not mentioned what would have happened if it hadn't rained- They might have played or they might not have played.
54
(C) Every relation in BCNF is also in 3NF. Straight from definition of BCNF.
55
We can get a DFA for $L = \{x \mid xx &#8714; A\}$ as follows: Take DFA for $A$ $\left(Q, \delta, \Sigma, S, F\right)$ with everything same except initially making $F = \phi$. Now for each state $D \in Q$, consider 2 separate DFAs, one with $S$ as the start state and $D$ as the final ... . But if we make $L$ from $A$ as per (d), it'll be $L = \{a^nb^nc^n \mid n \ge 0\}$ which is not context free..
56
139 Marks, 180 Minutes, 107 Questions
57
Let $Σ = \{a, b, c\}$. Which of the following statements is true? For any $A ⊆ Σ^*$, if $A$ is regular, then so is $\{xx \mid x ∊ A\}$ For any $A ⊆ Σ^*$, if $A$ is regular, then so is $\{x \mid xx ∊ A\}$ For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{xx \mid x ∊ A\}$ For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{x \mid xx ∊ A\}$
58
74 Marks, 100 Minutes, 46 Questions
59
Consider $L_1 = \left\{a^nb^nc^md^m \mid m,n \ge 1\right\}$ $L_2 = \left\{a^nb^n \mid n \ge1\right\}$ $L_3 = \left\{(a+b)^*\right\}$ Intersection of $L_1$ and $L_2$ is (A) Regular (B) CFL but not regular (C) CSL but not CFL (D) None of these
60
Consider the following languages $A=\left\{ \langle M\rangle \mid \text{ TM M accepts at most 2 distinct inputs} \right\}$ $B=\left\{\langle M \rangle \mid \text{ TM M accepts more than 2 distinct inputs} \right\}$ Identify the correct statement from the ... $A$ is not Turing recognizable Both $A$ and $B$ are Turing recognizable Neither $A$ nor $B$ is Turing recognizable