Most answered questions / GATE Overflow for GATE CSE

48 votes

10 answers

151

GATE CSE 2014 Set 3 | Question: 28
An $IP$ router with a $\text{Maximum Transmission Unit (MTU)}$ of $1500$ bytes has received an $IP$ packet of size $4404\text{ bytes}$ with an $IP$ header of length $20\text{ bytes}$. The values of the relevant fields in the header of the third $IP$ ... $1,$ Datagram Length$: 1500;$ Offset$: 370$ $\text{MF bit}$: $0,$ Datagram Length$: 1424;$ Offset$: 2960$

An $IP$ router with a $\text{Maximum Transmission Unit (MTU)}$ of $1500$ bytes has received an $IP$ packet of size $4404\text{ bytes}$ with an $IP$ header of length $20\t...

go_editor

21.3k views

go_editor asked Sep 28, 2014

61 votes

10 answers

152

GATE CSE 2014 Set 3 | Question: 14
You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is $O(n^2)$ $O(n \log n)$ $\Theta(n\log n)$ $O(n^3)$

You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the...

go_editor

30.9k views

go_editor asked Sep 28, 2014

101 votes

10 answers

153

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.8k views

go_editor asked Sep 28, 2014

127 votes

10 answers

154

GATE CSE 2014 Set 1 | Question: 44
An access sequence of cache block addresses is of length $N$ and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by $k$. What is the miss ratio if the access sequence is passed ... $\left(\dfrac{1}{N}\right)$ $\left(\dfrac{1}{A}\right)$ $\left(\dfrac{k}{n}\right)$

An access sequence of cache block addresses is of length $N$ and contains n unique block addresses. The number of unique block addresses between two consecutive accesses ...

go_editor

22.8k views

go_editor asked Sep 28, 2014

66 votes

10 answers

155

GATE CSE 2006 | Question: 54
Given two arrays of numbers $a_{1},...,a_{n}$ and $b_{1},...,b_{n}$ where each number is $0$ or $1$, the fastest algorithm to find the largest span $(i, j)$ such that $ a_{i}+a_{i+1}+\dots+a_{j}=b_{i}+b_{i+1}+\dots+b_{j}$ ... time in the key comparison mode Takes $\Theta (n)$ time and space Takes $O(\sqrt n)$ time only if the sum of the $2n$ elements is an even number

Given two arrays of numbers $a_{1},...,a_{n}$ and $b_{1},...,b_{n}$ where each number is $0$ or $1$, the fastest algorithm to find the largest span $(i, j)$ such that $ a...

Rucha Shelke

29.4k views

Rucha Shelke asked Sep 26, 2014

31 votes

10 answers

156

GATE CSE 1998 | Question: 27
Consider the following relational database schemes: COURSES (Cno, Name) PRE_REQ(Cno, Pre_Cno) COMPLETED (Student_no, Cno) COURSES gives the number and name of all the available courses. PRE_REQ gives the information about which courses are pre- ... relational algebra: List all the courses for which a student with Student_no 2310 has completed all the pre-requisites.

Consider the following relational database schemes:COURSES (Cno, Name)PRE_REQ(Cno, Pre_Cno)COMPLETED (Student_no, Cno)COURSES gives the number and name of all the availab...

Kathleen

8.1k views

Kathleen asked Sep 26, 2014

80 votes

10 answers

157

GATE CSE 2013 | Question: 29
Consider a hard disk with $16$ recording surfaces $(0-15)$ having $16384$ cylinders $(0-16383)$ and each cylinder contains $64$ sectors $(0-63)$. Data storage capacity in each sector is $512$ bytes. Data are organized cylinder-wise and the addressing ... cylinder number of the last sector of the file, if it is stored in a contiguous manner? $1281$ $1282$ $1283$ $1284$

Consider a hard disk with $16$ recording surfaces $(0-15)$ having $16384$ cylinders $(0-16383)$ and each cylinder contains $64$ sectors $(0-63)$. Data storage capacity in...

Arjun

30.2k views

Arjun asked Sep 24, 2014

40 votes

10 answers

158

GATE CSE 2005 | Question: 82a
Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges that ... of $G$ the weighted shortest path from $s$ to $t$ each path from $s$ to $t$ the weighted longest path from $s$ to $t$

Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$...

Kathleen

12.8k views

Kathleen asked Sep 22, 2014

67 votes

10 answers

159

GATE CSE 2009 | Question: 30
Consider a system with $4$ types of resources $R1$ ($3$ units), $R2$ ($2$ units), $R3$ ($3$ units), $R4$ ($2$ units). A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be ... deadlock Only $P1$ and $P2$ will be in deadlock Only $P1$ and $P3$ will be in deadlock All three processes will be in deadlock

Consider a system with $4$ types of resources $R1$ ($3$ units), $R2$ ($2$ units), $R3$ ($3$ units), $R4$ ($2$ units). A non-preemptive resource allocation policy is used....

Kathleen

34.2k views

Kathleen asked Sep 22, 2014

52 votes

10 answers

160

GATE CSE 2009 | Question: 28
Consider a $4$ stage pipeline processor. The number of cycles needed by the four instructions $I1, I2, I3, I4$ in stages $S1, S2, S3, S4$ ... the number of cycles needed to execute the following loop? For (i=1 to 2) {I1; I2; I3; I4;} $16$ $23$ $28$ $30$

Consider a $4$ stage pipeline processor. The number of cycles needed by the four instructions $I1, I2, I3, I4$ in stages $S1, S2, S3, S4$ is shown below:$$\begin{array}{|...

Kathleen

34.4k views

Kathleen asked Sep 22, 2014

93 votes

10 answers

161

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.5k views

Kathleen asked Sep 21, 2014

56 votes

10 answers

162

GATE CSE 2007 | Question: 69
The distance between two stations $M$ and $N$ is $L$ kilometers. All frames are $K$ bits long. The propagation delay per kilometer is $t$ seconds. Let $R$ bits/second be the channel capacity. Assuming that the processing delay is negligible, the $\text{minimum}$ number ... $\lceil \log_2 \frac{2LtR +K}{K} \rceil$ $\lceil \log_2 \frac{2LtR +2K}{2K} \rceil$

The distance between two stations $M$ and $N$ is $L$ kilometers. All frames are $K$ bits long. The propagation delay per kilometer is $t$ seconds. Let $R$ bits/second be ...

Kathleen

18.2k views

Kathleen asked Sep 21, 2014

57 votes

10 answers

163

GATE CSE 2007 | Question: 58
Two processes, $P1$ and $P2$, need to access a critical section of code. Consider the following synchronization construct used by the processes: /* P1 */ while (true) { wants1 = true; while (wants2 == true); /* Critical ... waiting. It requires that processes enter the critical section in strict alteration. It does not prevent deadlocks, but ensures mutual exclusion.

Two processes, $P1$ and $P2$, need to access a critical section of code. Consider the following synchronization construct used by the processes:/* P1 */ while (true) { wa...

Kathleen

27.7k views

Kathleen asked Sep 21, 2014

79 votes

10 answers

164

GATE CSE 2003 | Question: 23
In a min-heap with $n$ elements with the smallest element at the root, the $7^{th}$ smallest element can be found in time $\Theta (n \log n)$ $\Theta (n)$ $\Theta(\log n)$ $\Theta(1)$

In a min-heap with $n$ elements with the smallest element at the root, the $7^{th}$ smallest element can be found in time$\Theta (n \log n)$$\Theta (n)$$\Theta(\log n)$$\...

Disha

32.0k views

Disha asked Sep 19, 2014

52 votes

10 answers

165

GATE CSE 2004 | Question: 68
A hard disk with a transfer rate of $10$ Mbytes/second is constantly transferring data to memory using DMA. The processor runs at $600$ MHz, and takes $300$ and $900$ ... percentage of processor time consumed for the transfer operation? $5.0 \%$ $1.0\%$ $0.5\%$ $0.1\%$

A hard disk with a transfer rate of $10$ Mbytes/second is constantly transferring data to memory using DMA. The processor runs at $600$ MHz, and takes $300$ and $900$ clo...

Kathleen

27.2k views

Kathleen asked Sep 18, 2014

35 votes

10 answers

166

GATE CSE 2006 | Question: 15
Consider the following C-program fragment in which $i$, $j$ and $n$ are integer variables. for( i = n, j = 0; i > 0; i /= 2, j +=i ); Let $val(j)$ denote the value stored in the variable $j$ after termination of the for loop. Which one of the following is true? $val(j)=\Theta(\log n)$ $val(j)=\Theta (\sqrt{n})$ $val(j)=\Theta( n)$ $val(j)=\Theta (n\log n)$

Consider the following C-program fragment in which $i$, $j$ and $n$ are integer variables. for( i = n, j = 0; i 0; i /= 2, j +=i );Let $val(j)$ denote the value stored i...

Rucha Shelke

19.5k views

Rucha Shelke asked Sep 17, 2014

41 votes

10 answers

167

GATE CSE 2003 | Question: 38
Consider the set $\{a, b, c\}$ with binary operators $+$ and $*$ defined as follows: ... $(x, y)$ that satisfy the equations) is $0$ $1$ $2$ $3$

Consider the set $\{a, b, c\}$ with binary operators $+$ and $*$ defined as follows:$$\begin{array}{|c|c|c|c|} \hline \textbf{+} & \textbf{a}& \textbf{b} &\textbf{c...

Kathleen

7.1k views

Kathleen asked Sep 17, 2014

60 votes

10 answers

168

GATE CSE 2003 | Question: 36
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$

How many perfect matching are there in a complete graph of $6$ vertices?$15$$24$$30$$60$

Kathleen

50.4k views

Kathleen asked Sep 16, 2014

75 votes

10 answers

169

GATE CSE 2003 | Question: 18
In a bottom-up evaluation of a syntax directed definition, inherited attributes can always be evaluated be evaluated only if the definition is L-attributed be evaluated only if the definition has synthesized attributes never be evaluated

In a bottom-up evaluation of a syntax directed definition, inherited attributes canalways be evaluatedbe evaluated only if the definition is L-attributedbe evaluated only...

Kathleen

37.0k views

Kathleen asked Sep 16, 2014

67 votes

10 answers

170

GATE CSE 2003 | Question: 16
Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar? Removing left recursion alone Factoring the grammar alone Removing left recursion and factoring the grammar None of the above

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?Removing left recursion aloneFactoring the grammar aloneRemoving left recursion and factor...

Kathleen

27.3k views

Kathleen asked Sep 16, 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