Featured Questions / GATE Overflow for GATE CSE

100 votes

10 answers

61

GATE CSE 2014 Set 1 | Question: 51
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.

Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $...

go_editor

26.7k views

go_editor asked Sep 28, 2014

45 votes

4 answers

62

GATE CSE 2006 | Question: 84
Which one of the following grammars generates the language $ L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$? $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid a\mid b$ $A\rightarrow aA\mid \varepsilon$ $B\rightarrow Bb\mid \varepsilon$ ... $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid \varepsilon$ $A\rightarrow aA\mid a$ $B\rightarrow Bb\mid b$

Which one of the following grammars generates the language $ L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$?$S\rightarrow AC\mid CB$$C\rightarrow aCb\mid a\mid b$$A\rightar...

Rucha Shelke

12.0k views

Rucha Shelke asked Sep 26, 2014

90 votes

12 answers

63

GATE CSE 2006 | Question: 48
Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $2$ ... exist a cycle in $G$ containing $u$ and $ν$ There must exist a cycle in $G$ containing $u$ and all its neighbours in $G$

Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $...

Rucha Shelke

21.1k views

Rucha Shelke asked Sep 26, 2014

61 votes

4 answers

64

GATE CSE 2006 | Question: 38
Consider a Boolean function $ f(w,x,y,z)$. Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors $ i_{1}=\left \langle w_{1}, x_{1}, y_{1},z_{1}\right \rangle $ ... $ wx\overline{y} \overline{z}, xz, w\overline{x}yz$ $ wx\overline{y}, wyz, wxz, \overline{w}xz, x\overline{y}z, xyz$

Consider a Boolean function $ f(w,x,y,z)$. Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors...

Rucha Shelke

21.0k views

Rucha Shelke asked Sep 26, 2014

47 votes

6 answers

65

GATE CSE 2012 | Question: 31
Consider the $3$ processes, $P1, P2$ and $P3$ ... $P1, P3, P2$ FCFS: $P1, P2, P3$ RR2: $P1, P3, P2$ FCFS: $P1, P3, P2$ RR2: $P1, P2, P3$

Consider the $3$ processes, $P1, P2$ and $P3$ shown in the table. $$\small \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time} & \textbf{Time Units Req...

Arjun

19.5k views

Arjun asked Sep 26, 2014

59 votes

8 answers

66

GATE CSE 2013 | Question: 26
The line graph $L(G)$ of a simple graph $G$ is defined as follows: There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$. For any two edges $e$ and $e'$ in $G$, $L(G)$ has an edge between $v(e)$ and $v(e')$, if and only if ... planar graph is planar. (S) The line graph of a tree is a tree. $P$ only $P$ and $R$ only $R$ only $P, Q$ and $S$ only

The line graph $L(G)$ of a simple graph $G$ is defined as follows:There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$.For any two edges $e$ and $e'$ in ...

Arjun

19.1k views

Arjun asked Sep 24, 2014

77 votes

8 answers

67

GATE CSE 2005 | Question: 74
Suppose the round trip propagation delay for a $10\text{ Mbps}$ Ethernet having $48\text{-bit}$ jamming signal is $46.4\ \mu s$. The minimum frame size is: $94$ $416$ $464$ $512$

Suppose the round trip propagation delay for a $10\text{ Mbps}$ Ethernet having $48\text{-bit}$ jamming signal is $46.4\ \mu s$. The minimum frame size is:$94$$416$$464$$...

Kathleen

48.3k views

Kathleen asked Sep 22, 2014

142 votes

4 answers

68

GATE CSE 2005 | Question: 68
A $5$ stage pipelined CPU has the following sequence of stages: IF - instruction fetch from instruction memory RD - Instruction decode and register read EX - Execute: ALU operation for data and address computation MA - Data memory access - for write access, the ... taken to complete the above sequence of instructions starting from the fetch of $I_1$? $8$ $10$ $12$ $15$

A $5$ stage pipelined CPU has the following sequence of stages:IF – instruction fetch from instruction memoryRD – Instruction decode and register readEX – Execute: ...

Kathleen

46.4k views

Kathleen asked Sep 22, 2014

126 votes

18 answers

69

GATE CSE 2009 | Question: 57, ISRO2016-75
Frames of $\text{1000 bits}$ are sent over a $10^6$ $\text{bps}$ duplex link between two hosts. The propagation time is $\text{25 ms}$. Frames are to be transmitted into this link to maximally pack them in transit (within the link). What is the ... ? Assume that no time gap needs to be given between transmission of two frames. $I=2$ $I=3$ $I=4$ $I=5$

Frames of $\text{1000 bits}$ are sent over a $10^6$ $\text{bps}$ duplex link between two hosts. The propagation time is $\text{25 ms}$. Frames are to be transmitted into ...

Kathleen

48.5k views

Kathleen asked Sep 22, 2014

86 votes

7 answers

70

GATE CSE 2009 | Question: 47
While opening a $TCP$ connection, the initial sequence number is to be derived using a time-of-day (ToD) clock that keeps running even when the host is down. The low order $32$ bits of the counter of the ToD clock is to be used for the initial sequence numbers ... sequence numbers used for packets of a connection can increase? $0.015$/s $0.064$/s $0.135$/s $0.327$/s

While opening a $TCP$ connection, the initial sequence number is to be derived using a time-of-day (ToD) clock that keeps running even when the host is down. The low orde...

Kathleen

25.4k views

Kathleen asked Sep 22, 2014

90 votes

1 answer

71

GATE CSE 2009 | Question: 45
Let $R$ and $S$ be relational schemes such that $R=\{a,b,c\}$ and $S=\{c\}.$ Now consider the following queries on the database: $\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S} (r) \times s - \pi_{R-S,S}(r)\right )$ ... a,R.b From R,S Where R.c = S.c Which of the above queries are equivalent? $1$ and $2$ $1$ and $3$ $2$ and $4$ $3$ and $4$

Let $R$ and $S$ be relational schemes such that $R=\{a,b,c\}$ and $S=\{c\}.$ Now consider the following queries on the database:$\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S}...

Kathleen

24.6k views

Kathleen asked Sep 22, 2014

93 votes

10 answers

72

GATE CSE 2007 | Question: 80
Consider a machine with a byte addressable main memory of $2^{16}$ bytes. Assume that a direct mapped data cache consisting of $32$ lines of $64$ bytes each is used in the system. A $50 \times 50$ two-dimensional array of bytes is stored in the main ... data cache do not change in between the two accesses. How many data misses will occur in total? $48$ $50$ $56$ $59$

Consider a machine with a byte addressable main memory of $2^{16}$ bytes. Assume that a direct mapped data cache consisting of $32$ lines of $64$ bytes each is used in th...

Kathleen

32.4k views

Kathleen asked Sep 21, 2014

75 votes

8 answers

73

GATE CSE 2007 | Question: 53
Consider the following two statements: P: Every regular grammar is LL(1) Q: Every regular set has a LR(1) grammar Which of the following is TRUE? Both P and Q are true P is true and Q is false P is false and Q is true Both P and Q are false

Consider the following two statements:P: Every regular grammar is LL(1)Q: Every regular set has a LR(1) grammarWhich of the following is TRUE?Both P and Q are trueP is tr...

Kathleen

35.7k views

Kathleen asked Sep 21, 2014

55 votes

11 answers

74

GATE CSE 2004 | Question: 81
Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected graph, then the graph $G_1\cup G_2=(V,E_1\cup E_2)$ cannot have a cut vertex must have a cycle must have a cut-edge (bridge) has chromatic number strictly greater than those of $G_1$ and $G_2$

Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected gr...

Kathleen

11.8k views

Kathleen asked Sep 18, 2014

78 votes

7 answers

75

GATE CSE 2003 | Question: 84
Host $A$ is sending data to host $B$ over a full duplex link. $A$ and $B$ are using the sliding window protocol for flow control. The send and receive window sizes are $5$ packets each. Data packets (sent only from $A$ to $B$) are all $1000$ bytes long and the ... ? $7.69 \times 10^6$ Bps $11.11 \times 10^6$ Bps $12.33 \times 10^6$ Bps $15.00 \times 10^6$ Bps

Host $A$ is sending data to host $B$ over a full duplex link. $A$ and $B$ are using the sliding window protocol for flow control. The send and receive window sizes are $5...

Kathleen

27.8k views

Kathleen asked Sep 17, 2014

65 votes

9 answers

76

GATE CSE 2003 | Question: 43
The following is a scheme for floating point number representation using $16$ bits. Let $s, e,$ and $m$ ... between two successive real numbers representable in this system? $2^{-40}$ $2^{-9}$ $2^{22}$ $2^{31}$

The following is a scheme for floating point number representation using $16$ bits.Let $s, e,$ and $m$ be the numbers represented in binary in the sign, exponent, and man...

Kathleen

18.1k views

Kathleen asked Sep 17, 2014

59 votes

7 answers

77

GATE CSE 2003 | Question: 32
Which of the following is a valid first order formula? (Here $\alpha$ and $\beta$ are first order formulae with $x$ as their only free variable) $((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α ⇒ β]$ $(∀x)[α] ⇒ (∃x)[α ∧ β]$ $((∀x)[α ∨ β] ⇒ (∃x)[α]) ⇒ (∀x)[α]$ $(∀x)[α ⇒ β] ⇒ (((∀x)[α]) ⇒ (∀x)[β])$

Which of the following is a valid first order formula? (Here $\alpha$ and $\beta$ are first order formulae with $x$ as their only free variable)$((∀x)[α] ⇒ (∀x...

Kathleen

16.9k views

Kathleen asked Sep 16, 2014

71 votes

11 answers

78

GATE CSE 2002 | Question: 2.10
Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1..n]$ having $n$ distinct values: Choose an $i$ at random from $1..n$ If $A[i] = x$, then Stop else Goto 1; Assuming that $x$ is present in $A$, what is the expected number of comparisons made by the algorithm before it terminates? $n$ $n-1$ $2n$ $\frac{n}{2}$

Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1..n]$ having $n$ distinct values:Choose an $i$ at random from $1..n$If $A[i...

Kathleen

22.2k views

Kathleen asked Sep 15, 2014

128 votes

6 answers

79

GATE CSE 2001 | Question: 2.23
$R(A,B,C,D)$ is a relation. Which of the following does not have a lossless join, dependency preserving $BCNF$ decomposition? $A \rightarrow B, B \rightarrow CD$ $A \rightarrow B, B \rightarrow C, C \rightarrow D$ $ AB \rightarrow C, C \rightarrow AD$ $A \rightarrow BCD$

$R(A,B,C,D)$ is a relation. Which of the following does not have a lossless join, dependency preserving $BCNF$ decomposition?$A \rightarrow B, B \rightarrow CD$$A \righta...

Kathleen

51.7k views

Kathleen asked Sep 14, 2014

38 votes

4 answers

80

GATE CSE 2001 | Question: 2.4
Seven (distinct) car accidents occurred in a week. What is the probability that they all occurred on the same day? $\dfrac{1}{7^7}\\$ $\dfrac{1}{7^6}\\$ $\dfrac{1}{2^7}\\$ $\dfrac{7}{2^7}\\$

Seven (distinct) car accidents occurred in a week. What is the probability that they all occurred on the same day?$\dfrac{1}{7^7}\\$$\dfrac{1}{7^6}\\$$\dfrac{1}{2^7}\\$$\...

Kathleen

18.2k views

Kathleen asked Sep 14, 2014

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true