The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged gate2004
+3
votes
1
answer
1
gate 2004 algorithms
let A[1,2,...n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is ø(m). consider the following program segment in C: counter=0; for(i=1;i<n; i++) {if (A[i] ==1) counter++; else {f(counter); counter=0; } } tge complexity of program segment is:
asked
Jul 26, 2017
in
Algorithms
by
mitalitak
(
37
points)

316
views
gate2004
algorithms
timecomplexity
+2
votes
0
answers
2
previous year
Consider a parity check code with three data bits and four parity check bits. Three of the code words are 0101011, 1001101 and 1110001. Which of the following are also code words? 0010111 0110110 1011010 0111010 plz give the solution in detail I and III I, II and III II and IV I, II, III and IV
asked
Apr 5, 2017
in
Computer Networks
by
Prince Kumar 1
(
227
points)

143
views
gate2004
+21
votes
3
answers
3
GATE200457
Consider three IP networks $A, B$ and $C$. Host $H_A$ in network $A$ sends messages each containing $180$ $bytes$ of application data to a host $H_C$ in network $C$. The TCP layer prefixes $20$ byte header to the message. This passes through an intermediate network $B$. The maximum ... overheads. $325.5$ $\text{Kbps}$ $354.5$ $\text{Kbps}$ $409.6$ $\text{Kbps}$ $512.0$ $\text{Kbps}$
asked
Apr 24, 2016
in
Computer Networks
by
jothee
Veteran
(
98.5k
points)

2.7k
views
gate2004
computernetworks
ipv4
tcp
normal
+24
votes
3
answers
4
GATE200464
Consider the following program segment for a hypothetical CPU having three user registers R1, R2 and R3. Instruction Operation Instruction Size (in words) MOV R1, 5000 R1 $\leftarrow$ Memory[5000] 2 MOV R2(R1) R2 $\leftarrow$ Memory[(R1)] 1 ADD R2, R3 R2 ... fetch and decode : 2 clock cycles per word The total number of clock cycles required to execute the program is 29 24 23 20
asked
Apr 24, 2016
in
CO & Architecture
by
jothee
Veteran
(
98.5k
points)

3.1k
views
gate2004
coandarchitecture
machineinstructions
normal
+24
votes
3
answers
5
GATE200410
Consider the grammar rule $E \rightarrow E1  E2$ for arithmetic expressions. The code generated is targeted to a CPU having a single user register. The subtraction operation requires the first operand to be in the register. If $E1$ and $E2$ do ... evaluated first Evaluation of $E1$ and $E2$ should necessarily be interleaved Order of evaluation of $E1$ and $E2$ is of no consequence
asked
Nov 12, 2014
in
Compiler Design
by
Vikrant Singh
Boss
(
13.5k
points)

1.9k
views
gate2004
compilerdesign
targetcodegeneration
normal
+17
votes
4
answers
6
GATE200490
Choose the best matching between the programming styles in Group 1 and their characteristics in Group 2. Group 1 Group 2 P. Functional Q. Logic R. Objectoriented S. Imperative 1. Commonbased, procedural 2. Imperative, abstract data types 3. Sideeffect free, declarative, expression evaluations 4. Declarative, clausal ... R4 S1 P4 Q3 R2 S1 P3 Q4 R1 S2 P3 Q4 R2 S1
asked
Sep 19, 2014
in
Programming
by
Kathleen
Veteran
(
59.4k
points)

966
views
gate2004
programming
normal
programmingparadigms
+21
votes
1
answer
7
GATE200489
$L_1$ is a recursively enumerable language over $\Sigma$. An algorithm $A$ effectively enumerates its words as $\omega_1, \omega_2, \omega_3, \dots .$ Define another language $L_2$ over $\Sigma \cup \left\{\text{#}\right\}$ as $\left\{w_i \text{# ... $S_2$ are true $S_1$ is true but $S_2$ is not necessarily true $S_2$ is true but $S_1$ is not necessarily true Neither is necessarily true
asked
Sep 19, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.4k
points)

2.4k
views
gate2004
theoryofcomputation
turingmachine
difficult
+12
votes
2
answers
8
GATE200488
Consider the following grammar G: $S \rightarrow bS \mid aA \mid b$ $A \rightarrow bA \mid aB$ $B \rightarrow bB \mid aS \mid a$ Let $N_a(w)$ and $N_b(w)$ denote the number of a's and b's in a string $\omega$ respectively. The language $L(G)$ over $\left\{a, b\right\}^+$ generated by ... {0, 1, 2, \right\}\right\}$ $\left\{w \mid N_b(w) = 3k, k \in \left\{0, 1, 2, \right\}\right\}$
asked
Sep 19, 2014
in
Compiler Design
by
Kathleen
Veteran
(
59.4k
points)

851
views
gate2004
compilerdesign
grammar
normal
+13
votes
4
answers
9
GATE200487
The language $\left\{a^mb^nc^{m+n} \mid m, n \geq1\right\}$ is regular contextfree but not regular contextsensitive but not context free type0 but not context sensitive
asked
Sep 19, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.4k
points)

697
views
gate2004
theoryofcomputation
normal
identifyclasslanguage
+18
votes
3
answers
10
GATE200486
The following finite state machine accepts all those binary strings in which the number of $1$’s and $0$’s are respectively: divisible by $3$ and $2$ odd and even even and odd divisible by $2$ and $3$
asked
Sep 19, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.4k
points)

978
views
gate2004
theoryofcomputation
finiteautomata
easy
+38
votes
6
answers
11
GATE200485
A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is: $$\Large \min \left ( \substack{\text{number of leafnodes}\\\text{in leftsubtree of $x$}}\;,\; \ ... case time complexity of the program is? $\Theta (n)$ $\Theta (n \log n)$ $\Theta(n^2)$ $\Theta (n^2\log n)$
asked
Sep 19, 2014
in
DS
by
Kathleen
Veteran
(
59.4k
points)

5k
views
gate2004
binarysearchtree
normal
datastructure
+22
votes
4
answers
12
GATE200484
The recurrence equation $ T(1) = 1$ $T(n) = 2T(n1) + n, n \geq 2$ evaluates to $2^{n+1}  n  2$ $2^n  n$ $2^{n+1}  2n  2$ $2^n + n $
asked
Sep 19, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.4k
points)

3.1k
views
gate2004
algorithms
recurrence
normal
+13
votes
4
answers
13
GATE200483, ISRO201540
The time complexity of the following C function is (assume $n > 0$) int recursive (int n) { if(n == 1) return (1); else return (recursive (n1) + recursive (n1)); } $O(n)$ $O(n \log n)$ $O(n^2)$ $O(2^n)$
asked
Sep 19, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.4k
points)

3.7k
views
gate2004
algorithms
recurrence
timecomplexity
normal
isro2015
+31
votes
9
answers
14
GATE200482
Let $A[1, n]$ be an array storing a bit ($1$ or $0$) at each location, and $f(m)$ is a function whose time complexity is $\Theta(m)$. Consider the following program fragment written in a C like language: counter = 0; for (i=1; i<=n; i++) { if a[i] == 1) counter++ ... } The complexity of this program fragment is $\Omega(n^2)$ $\Omega (n\log n) \text{ and } O(n^2)$ $\Theta(n)$ $o(n)$
asked
Sep 19, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.4k
points)

3.2k
views
gate2004
algorithms
timecomplexity
normal
+23
votes
8
answers
15
GATE200481
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 cutedge (bridge) Has chromatic number strictly greater than those of $G_1$ and $G_2$
asked
Sep 19, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.4k
points)

2k
views
gate2004
algorithms
graphalgorithms
normal
+9
votes
3
answers
16
GATE200480
A point is randomly selected with uniform probability in the $XY$ plane within the rectangle with corners at $(0,0), (1,0), (1,2)$ and $(0,2).$ If $p$ is the length of the position vector of the point, the expected value of $p^{2}$ is $\left(\dfrac{2}{3}\right)$ $\quad 1$ $\left(\dfrac{4}{3}\right)$ $\left(\dfrac{5}{3}\right)$
asked
Sep 19, 2014
in
Probability
by
Kathleen
Veteran
(
59.4k
points)

1.6k
views
gate2004
probability
uniformdistribution
expectation
normal
+29
votes
2
answers
17
GATE200479
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2  3n)}{ 2}$ edges ? $^{\left(\frac{n^2n}{2}\right)}C_{\left(\frac{n^23n} {2}\right)}$ $^{{\large\sum\limits_{k=0}^{\left (\frac{n^23n}{2} \right )}}.\left(n^2n\right)}C_k\\$ $^{\left(\frac{n^2n}{2}\right)}C_n\\$ $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2n}{2}\right)}C_k$
asked
Sep 19, 2014
in
Graph Theory
by
Kathleen
Veteran
(
59.4k
points)

2.6k
views
gate2004
graphtheory
permutationsandcombinations
normal
counting
+9
votes
4
answers
18
GATE200478
Two $n$ bit binary strings, $S_1$ and $S_2$ are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where the two strings differ) is equal to $d$ is $\dfrac{^{n}C_{d}}{2^{n}}$ $\dfrac{^{n}C_{d}}{2^{d}}$ $\dfrac{d}{2^{n}}$ $\dfrac{1}{2^{d}}$
asked
Sep 19, 2014
in
Probability
by
Kathleen
Veteran
(
59.4k
points)

1.1k
views
gate2004
probability
normal
+16
votes
5
answers
19
GATE200477
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is $2$ $3$ $4$ $5$
asked
Sep 19, 2014
in
Graph Theory
by
Kathleen
Veteran
(
59.4k
points)

1.5k
views
gate2004
graphtheory
graphcoloring
easy
+12
votes
2
answers
20
GATE200476
In an $M \times N$ matrix all nonzero entries are covered in $a$ rows and $b$ columns. Then the maximum number of nonzero entries, such that no two are on the same row or column, is $\leq a +b$ $\leq \max(a, b)$ $\leq \min(Ma, Nb)$ $\leq \min(a, b)$
asked
Sep 19, 2014
in
Linear Algebra
by
Kathleen
Veteran
(
59.4k
points)

1.8k
views
gate2004
linearalgebra
normal
matrices
+22
votes
3
answers
21
GATE200475
Mala has the colouring book in which each English letter is drawn two times. She wants to paint each of these $52$ prints with one of $k$ colours, such that the colour pairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of $k$ that satisfies this requirement? $9$ $8$ $7$ $6$
asked
Sep 19, 2014
in
Combinatory
by
Kathleen
Veteran
(
59.4k
points)

2k
views
gate2004
permutationsandcombinations
+10
votes
3
answers
22
GATE200474
An examination paper has $150$ multiple choice questions of one mark each, with each question having four choices. Each incorrect answer fetches $0.25$ marks. Suppose $1000$ students choose all their answers randomly with uniform probability. The sum total of the expected marks obtained by all these students is $0$ $2550$ $7525$ $9375$
asked
Sep 19, 2014
in
Probability
by
Kathleen
Veteran
(
59.4k
points)

1.2k
views
gate2004
probability
expectation
normal
+20
votes
7
answers
23
GATE200473
The inclusion of which of the following sets into $S = \left\{ \left\{1, 2\right\}, \left\{1, 2, 3\right\}, \left\{1, 3, 5\right\}, \left\{1, 2, 4\right\}, \left\{1, 2, 3, 4, 5\right\} \right\} $ is necessary and sufficient to make $S$ a complete lattice under the partial order defined by set containment? ... \{2, 3\}$ $\{1\}, \{1, 3\}$ $\{1\}, \{1, 3\}, \{1, 2, 3, 4\}, \{1, 2, 3, 5\}$
asked
Sep 19, 2014
in
Set Theory & Algebra
by
Kathleen
Veteran
(
59.4k
points)

1.6k
views
gate2004
settheory&algebra
partialorder
normal
+16
votes
2
answers
24
GATE200472
The following is the incomplete operation table of a 4element group. * e a b c e e a b c a a b c e b c The last row of the table is c a e b c b a e c b e a c e a b
asked
Sep 19, 2014
in
Set Theory & Algebra
by
Kathleen
Veteran
(
59.4k
points)

882
views
gate2004
settheory&algebra
groups
normal
+11
votes
3
answers
25
GATE200471
How many solutions does the following system of linear equations have? $x + 5y = 1$ $x  y = 2$ $x + 3y = 3$ infinitely many two distinct solutions unique none
asked
Sep 19, 2014
in
Linear Algebra
by
Kathleen
Veteran
(
59.4k
points)

997
views
gate2004
linearalgebra
systemofequations
normal
+13
votes
1
answer
26
GATE200470
The following propositional statement is $\left(P \implies \left(Q \vee R\right)\right) \implies \left(\left(P \wedge Q \right)\implies R\right)$ satisfiable but not valid valid a contradiction None of the above
asked
Sep 19, 2014
in
Mathematical Logic
by
Kathleen
Veteran
(
59.4k
points)

981
views
gate2004
mathematicallogic
normal
propositionallogic
+17
votes
4
answers
27
GATE200469
A 4stage pipeline has the stage delays as 150, 120, 160 and 140 nanoseconds respectively. Registers that are used between the stages have a delay of 5 nanoseconds each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will be 120.4 microseconds 160.5 microseconds 165.5 microseconds 590.0 microseconds
asked
Sep 19, 2014
in
CO & Architecture
by
Kathleen
Veteran
(
59.4k
points)

2.5k
views
gate2004
coandarchitecture
pipelining
normal
+21
votes
6
answers
28
GATE200468
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 clock cycles to initiate and complete DMA transfer respectively. If the size of the transfer is 20 Kbytes, what is the percentage of processor time consumed for the transfer operation? 5.0% 1.0% 0.5% 0.1%
asked
Sep 19, 2014
in
Operating System
by
Kathleen
Veteran
(
59.4k
points)

4.3k
views
gate2004
operatingsystem
disks
normal
coandarchitecture
+16
votes
1
answer
29
GATE200467
The microinstructions stored in the control memory of a processor have a width of 26 bits. Each microinstruction is divided into three fields: a microoperation field of 13 bits, a next address field ($X$), and a MUX select field ($Y$). There are 8 status bits in the input of the ... what is the size of the control memory in number of words? 10, 3, 1024 8, 5, 256 5, 8, 2048 10, 3, 512
asked
Sep 19, 2014
in
CO & Architecture
by
Kathleen
Veteran
(
59.4k
points)

2.5k
views
gate2004
coandarchitecture
microprogramming
normal
+14
votes
2
answers
30
GATE200466
Let A = 1111 1010 and B = 0000 1010 be two 8bit 2’s complement numbers. Their product in 2’s complement is 1100 0100 1001 1100 1010 0101 1101 0101
asked
Sep 19, 2014
in
Digital Logic
by
Kathleen
Veteran
(
59.4k
points)

2k
views
gate2004
digitallogic
numberrepresentation
easy
Page:
1
2
3
4
next »
Quick search syntax
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
Recent Posts
BARC Interview Experience 15th June 2018
COAP Admission and IITD, IITK Interview Experience 2018
MS Interview Experience at IITK
Effect of Academic/ Career Gap during Mtech Placements at IIT/NIT
Gate Rank Improvement
Follow @csegate
Gatecse
Recent questions tagged gate2004
Recent Blog Comments
thanks for the info .but qstn 1.4 time complexity ...
What was your GATE rank and score this time ...
finish all subjects first then start taking all ...
@Arjun sir Address Confirmation mail not ...
Those who pay till today  June 17 can expect the ...
36,075
questions
43,521
answers
123,666
comments
42,747
users