# 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
Consider the following circuit involving a positive edge triggered D FF. Consider the following timing diagram. Let $A_{i}$ represents the logic level on the line a in the i-th clock period. Let $A'$ represent the compliment of $A$. The correct output sequence on $Y$ over the clock periods $1$ through $5$ ... $A_{1} A_{2} A_{2}' A_{3} A_{4}$ $A_{1} A_{2}' A_{3} A_{4} A_{5}'$
3
explain the recurrence relation???
4
100 Marks, 180 Minutes, 65 Questions
5
okay. You may use <> in the toolbar to output code properly :)
6
yes,,the line upto "count=count+1" is in the loop...
7
Increment of count must be inside the loop rt?
8
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?
9
60 Marks, 108 Minutes, 40 Questions
10
60 Marks, 108 Minutes, 40 Questions
11
how can we eliminate option B unless we draw it actually...just because of argument of 'stronger answer' ?
12
60 Marks, 108 Minutes, 40 Questions
13
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.
14
It is true for big O. But for $\Theta$ notation can we say $n! = \Theta (n^n)$?
15
70 Marks, 126 Minutes, 40 Questions
16
Yes, result. I will correct the statement. Thanks.
17
60 Marks, 108 Minutes, 40 Questions
18
60 Marks, 108 Minutes, 40 Questions
19
Why you say it is a condition? It is the result of pumping lemma rt?
20
That's a perfect explanation.
21
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)$.
22
45 Marks, 81 Minutes, 30 Questions
23
(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
24
(C) $\forall i \in N, xy^iz \in L$ This is the result of Pumping Lemma for regular language
25
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
26
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
27
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$
28
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$
29
45 Marks, 85 Minutes, 29 Questions
30
46 Marks, 85 Minutes, 30 Questions
31
Yes. That was a bad mistake. I have corrected it :)
32
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}.$
33
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!$
34
Microprogrammed control unit: is faster than a hardwired control unit facilitates easy implementation of new instructions is useful when very small programs are to be run usually refers to control unit of a microprocessor
35
yeah I thought the same, but for the second part adding only the height difference from A to P wont suffice coz we need to add all those right trees also, going up from A to P...thanks
36
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.
37
44 Marks, 80 Minutes, 29 Questions
38
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$
39
51 Marks, 95 Minutes, 34 Questions
40
50 Marks, 90 Minutes, 33 Questions
41
45 Marks, 80 Minutes, 30 Questions
42
45 Marks, 80 Minutes, 30 Questions
43
55 Marks, 100 Minutes, 34 Questions
44
61 Marks, 110 Minutes, 37 Questions
45
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 :)
46
47
57 Marks, 100 Minutes, 37 Questions
48
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
49
(All reductions in polynomial time) is mentioned in the question :)
50
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.
51
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
52
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.
53
That's correct. But why?
54
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..
55
Acc to me Answer Should be option (B) Explanation : P=NP is true only when NP-complete can be reducible to P
56
68 Marks, 120 Minutes, 40 Questions
57
B. might be the answer. As NPC are the "hardest" in NP. So Reduction of a NP-complete problem to a P problem will be sufficient.
58
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
59
GATE 2012 Answer key is (C) $Q$ and $R$ are true. But correct answer should be B. When group by is not present, having is applied to the whole table "A grouped table is a set of groups derived during the evaluation of a <group by clause> or a <having clause>. ... why this shouldn't be allowed. So, ideally 'S' is more correct than 'R' or both are debatable and marks should have been given to all.
60
$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.
61
(C) Every relation in BCNF is also in 3NF. Straight from definition of BCNF.
62
100 Marks, 180 Minutes, 65 Questions
63
$L_1$ is clearly a DCFL and DCFL is closed under complement. Hence, $L_2$ is also DCFL. We can make a PDA for $L_2$ , using the same PDA for {aⁿbⁿ} as follows: Start by pushing each 'a' on to stack. When b comes start popping. If 'a' comes after a 'b' ... PDA accepts any string. Otherwise, at the end of the string, if stack is non-empty, accept the string and if stack is empty, reject the string.
64
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..
65
139 Marks, 180 Minutes, 107 Questions
66
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\}$
67
74 Marks, 100 Minutes, 46 Questions
68
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
69
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
70
Answer is (C) Poisson Probability Density Function (with mean $\lambda$) =$\dfrac{ \lambda^{k}} { \left(e^{\lambda}k!\right)}$, We have to sum the probability density function for $k = 0,1$ and $2$ and $\lambda = 3$(thus finding the cumulative mass function) =$\left(\dfrac{1}{e^{3}}\right) + \left(\dfrac{3}{e^{3}}\right) + \left(\dfrac{9}{2e^{3}}\right)$ =$\dfrac{17}{\left(2e^{3}\right)}$
71
Suppose $p$ is the number of cars per minute passing through a certain road junction between $5$ PM and $6$ PM, and $p$ has a Poisson distribution with mean $3$. What is the probability of observing fewer than $3$ cars during any given minute in this interval? $\dfrac{8}{(2e^{3})}$ $\dfrac{9}{(2e^{3})}$ $\dfrac{17}{(2e^{3})}$ $\dfrac{26}{(2e^{3})}$
72
Consider the following operation along with Enqueue and Dequeue operations on queues, where $k$ is a global parameter. MultiDequeue(Q){ m = k while (Q is not empty) and (m > 0) { Dequeue(Q) m = m – 1 } } What is the worst case time complexity of a sequence of $n$ queue operations on an initially empty queue? $Θ(n)$ $Θ(n + k)$ $Θ(nk)$ $Θ(n^2)$
73
What is the return value of $f(p,p)$, if the value of $p$ is initialized to $5$ before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value. int f (int &x, int c) { c = c - 1; if (c==0) return 1; x = x + 1; return f(x,c) * x; }
74
A binary operation $\oplus$ on a set of integers is defined as $x \oplus y = x^{2}+y^{2}$. Which one of the following statements is TRUE about $\oplus$? Commutative but not associative Both commutative and associative Associative but not commutative Neither commutative nor associative
75
150 Marks, 180 Minutes, 90 Questions
76
150 Marks, 180 Minutes, 90 Questions
77
Which of the following options is the closest in meaning to the phrase in bold in the sentence below? It is fascinating to see life forms **cope with** varied environmental conditions. Adopt to Adapt to Adept in Accept with
78
For any planar graph, $\text{n(no. of vertices) - e(no. of edges) + f(no. of faces) = 2}$ $f = 15 - 10 + 2= 7$ number of bounded faces $= \text{no. of faces -1}$ $= 7 -1=6$ So, the correct answer would be D
79
150 Marks, 180 Minutes, 85 Questions
80
Whenever $X$ is true $(X,Y)$ is true and whenever $X$ is false $(X,Y)$ is false, so the answer is (A) $X$.
81
What is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string. $\phi$ $\{\epsilon\}$ $a^*$ $\{a , \epsilon\}$
82
Let A be the $2 × 2$ matrix with elements $a_{11} = a_{12} = a_{21} = +1$ and $a_{22} = −1$ . Then the eigenvalues of the matrix $A^{19}$ are $1024$ and $−1024$ $1024\sqrt{2}$ and $−1024 \sqrt{2}$ $4 \sqrt{2}$ and $−4 \sqrt{2}$ $512 \sqrt{2}$ and $−512 \sqrt{2}$
83
The protocol data unit (PDU) for the application layer in the Internet stack is: Segment Datagram Message Frame
84
Consider the function $f(x) = \sin(x)$ in the interval $x =\left[\frac{\pi}{4},\frac{7\pi}{4}\right]$. The number and location(s) of the local minima of this function are One, at $\dfrac{\pi}{2}$ One, at $\dfrac{3\pi}{2}$ Two, at $\dfrac{\pi}{2}$ and $\dfrac{3\pi}{2}$ Two, at $\dfrac{\pi}{4}$ and $\dfrac{3\pi}{2}$
85
A process executes the code fork(); fork(); fork(); The total number of child processes created is $3$ $4$ $7$ $8$
86
100 Marks, 180 Minutes, 65 Questions
87
100 Marks, 180 Minutes, 65 Questions
88
100 Marks, 180 Minutes, 65 Questions
89
100 Marks, 180 Minutes, 65 Questions
90
100 Marks, 180 Minutes, 65 Questions
91
100 Marks, 180 Minutes, 65 Questions
92
100 Marks, 180 Minutes, 65 Questions
93
100 Marks, 180 Minutes, 65 Questions