Register

Recent questions tagged gatecse-2004

1 1 vote
2 2 answers
393
393 views
#GATE 2004.#Algoritms#asymptoticAnalysis
what does the following algorithm approximate?(Assume m>1,Epsilon>0) x=m; y=1; while (x-y>Epsilon) { x=(x+y)/2; y=m/x;}print(x);a)log...
User Avatar
91 91 votes
13 answers 13 answers
34.0k
34.0k views
GATE CSE 2004 | Question: 57
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 ...
User Avatar
79 79 votes
6 answers 6 answers
29.7k
29.7k views
GATE CSE 2004 | Question: 64
Consider the following program segment for a hypothetical CPU having three user registers $R_1, R_2$ and $R_3.$$$ \begin{array}{|l|l|c|} \hline \text{Instruction} & \text...
User Avatar
62 62 votes
5 answers 5 answers
20.6k
20.6k views
GATE CSE 2004 | Question: 10
Consider the grammar rule $E \rightarrow E1 – E2$ for arith­metic expressions. The code generated is targeted to a CPU having a single user register. The sub­traction ope...
User Avatar
37 37 votes
5 answers 5 answers
11.6k
11.6k views
GATE CSE 2004 | Question: 90
Choose the best matching between the programming styles in Group 1 and their characteristics in Group 2.$$\begin{array}{|ll|ll|}\hline \rlap{\textbf{Group 1}} & & \rlap{...
User Avatar
67 67 votes
5 answers 5 answers
17.6k
17.6k views
GATE CSE 2004 | Question: 89
$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 lang...
User Avatar
32 32 votes
3 answers 3 answers
12.6k
12.6k views
GATE CSE 2004 | Question: 88
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 o...
User Avatar
32 32 votes
4 answers 4 answers
10.5k
10.5k views
GATE CSE 2004 | Question: 87
The language $\left\{a^mb^nc^{m+n} \mid m, n \geq1\right\}$ isregularcontext-free but not regularcontext-sensitive but not context freetype-0 but not context sensitive
User Avatar
55 55 votes
6 answers 6 answers
14.1k
14.1k views
GATE CSE 2004 | Question: 86
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 eveneven ...
User Avatar
158 158 votes
15 answers 15 answers
58.6k
58.6k views
GATE CSE 2004 | Question: 85
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)$ ...
User Avatar
66 66 votes
7 answers 7 answers
30.4k
30.4k views
GATE CSE 2004 | Question: 84
The recurrence equation$ T(1) = 1$$T(n) = 2T(n-1) + n, n \geq 2$evaluates to$2^{n+1} - n - 2$$2^n - n$$2^{n+1} - 2n - 2$$2^n + n $
User Avatar
40 40 votes
7 answers 7 answers
28.2k
28.2k views
GATE CSE 2004 | Question: 83, ISRO2015-40
The time complexity of the following C function is (assume $n 0$)int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); }$O(n)$$...
User Avatar
85 85 votes
13 answers 13 answers
32.7k
32.7k views
GATE CSE 2004 | Question: 82
Let $A[1,\ldots,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...
User Avatar
79 79 votes
13 answers 13 answers
22.0k
22.0k views
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 gr...
User Avatar
49 49 votes
7 answers 7 answers
16.3k
16.3k views
GATE CSE 2004 | Question: 80
A point is randomly selected with uniform probability in the $X-Y$ plane within the rectangle with corners at $(0,0), (1,0), (1,2)$ and $(0,2).$ If $p$ is the length of t...
User Avatar
137 137 votes
9 answers 9 answers
26.7k
26.7k views
GATE CSE 2004 | Question: 79
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ?$^{\left(\frac{n^2-n}{2}\right)}C_{\left(\frac{n^2-3n} {2}\right)}$$^{{\l...
User Avatar
42 42 votes
7 answers 7 answers
13.3k
13.3k views
GATE CSE 2004 | Question: 78
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 b...
User Avatar
50 50 votes
7 answers 7 answers
21.2k
21.2k views
GATE CSE 2004 | Question: 77
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$
User Avatar
64 64 votes
7 answers 7 answers
18.1k
18.1k views
GATE CSE 2004 | Question: 76
In an $M \times N$ matrix all non-zero entries are covered in $a$ rows and $b$ columns. Then the maximum number of non-zero entries, such that no two are on the same row ...
User Avatar
95 95 votes
13 answers 13 answers
31.0k
31.0k views
GATE CSE 2004 | Question: 75
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 pa...
User Avatar
58 58 votes
7 answers 7 answers
15.3k
15.3k views
GATE CSE 2004 | Question: 74
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 $1...
User Avatar
57 57 votes
8 answers 8 answers
20.9k
20.9k views
GATE CSE 2004 | Question: 73
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,...
User Avatar
49 49 votes
8 answers 8 answers
12.1k
12.1k views
GATE CSE 2004 | Question: 72
The following is the incomplete operation table of a $4-$element group.$$\begin{array}{|l|l|l|l|l|} \hline \textbf{*} & \textbf{e}& \textbf{a} &\textbf{b} & \textbf{c}\\\...
User Avatar
41 41 votes
7 answers 7 answers
16.0k
16.0k views
GATE CSE 2004 | Question: 71
How many solutions does the following system of linear equations have?$-x + 5y = -1$$x - y = 2$$x + 3y = 3$infinitely manytwo distinct solutionsuniquenone
User Avatar
45 45 votes
5 answers 5 answers
13.3k
13.3k views
GATE CSE 2004 | Question: 70
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 v...
User Avatar
54 54 votes
5 answers 5 answers
28.2k
28.2k views
GATE CSE 2004 | Question: 69
A 4-stage 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$ $nano...
User Avatar
82 82 votes
11 answers 11 answers
41.6k
41.6k views
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$ clo...
User Avatar
51 51 votes
2 answers 2 answers
19.8k
19.8k views
GATE CSE 2004 | Question: 67
The microinstructions stored in the control memory of a processor have a width of $26$ bits. Each microinstruction is divided into three fields: a micro-operation field o...
User Avatar
38 38 votes
5 answers 5 answers
26.4k
26.4k views
GATE CSE 2004 | Question: 66
Let $A = 1111 1010$ and $B = 0000 1010$ be two $8-bit$ $2’s$ complement numbers. Their product in $2’s$ complement is$1100 0100$$1001 1100$$1010 0101$$1101 0101$
User Avatar
33 33 votes
4 answers 4 answers
23.6k
23.6k views
GATE CSE 2004 | Question: 65
Consider a small two-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, use the least recently used (LRU) scheme. The num...
User Avatar
Page: