search
Log In

Recent questions tagged gate2004

2 votes
0 answers
1
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 Prince Kumar 1 207 views
40 votes
7 answers
2
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 packet ... other overheads. $325.5$ $\text{Kbps}$ $354.5$ $\text{Kbps}$ $409.6$ $\text{Kbps}$ $512.0$ $\text{Kbps}$
asked Apr 24, 2016 in Computer Networks jothee 7.6k views
45 votes
4 answers
3
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{Operation }& \text{Instruction size (in Words)} \\\hline \text{MOV $R_1,5000$} & \text{$R1$} \ ... text{2 clock cycles }\\\hline \end{array} The total number of clock cycles required to execute the program is $29$ $24$ $23$ $20$
asked Apr 24, 2016 in CO and Architecture jothee 8k views
32 votes
3 answers
4
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 operation requires the first operand to be in the register. If $E1$ and $E2$ do not have any com­mon ... 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 Vikrant Singh 4.9k views
20 votes
5 answers
5
Choose the best matching between the programming styles in Group 1 and their characteristics in Group 2. ... $P-3\quad Q-4 \quad R-1\quad S-2$ $P-3\quad Q-4\quad R-2\quad S-1$
asked Sep 19, 2014 in Programming Kathleen 2.3k views
38 votes
1 answer
6
$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\}$ ... $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 Kathleen 4.9k views
17 votes
2 answers
7
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 $G$ ... $\left\{w \mid N_b(w) = 3k, k \in \left\{0, 1, 2, \right\}\right\}$
asked Sep 19, 2014 in Compiler Design Kathleen 2.2k views
20 votes
4 answers
8
The language $\left\{a^mb^nc^{m+n} \mid m, n \geq1\right\}$ is regular context-free but not regular context-sensitive but not context free type-0 but not context sensitive
asked Sep 19, 2014 in Theory of Computation Kathleen 1.9k views
23 votes
3 answers
9
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 Kathleen 2.2k views
59 votes
7 answers
10
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 leaf-nodes}\\\text{in left-subtree of $ ... the worst-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 Kathleen 11.1k views
29 votes
8 answers
11
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 $
asked Sep 19, 2014 in Algorithms Kathleen 6.5k views
18 votes
7 answers
12
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)$ $O(n \log n)$ $O(n^2)$ $O(2^n)$
asked Sep 19, 2014 in Algorithms Kathleen 6.4k views
45 votes
12 answers
13
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 fragment written in a C like language: counter = 0; for (i=1; i<=n; i++) { if a[i] == 1) counter++; ... 0;} } 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 Kathleen 8.3k views
36 votes
8 answers
14
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$
asked Sep 19, 2014 in Algorithms Kathleen 4.1k views
16 votes
4 answers
15
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 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 Kathleen 3.6k views
48 votes
4 answers
16
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)}$ $^{{\large\sum\limits_{k=0}^{\left (\frac{n^2-3n}{2} \right )}}.\left(n^2-n\right)}C_k\\$ $^{\left(\frac{n^2-n}{2}\right)}C_n\\$ $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2-n}{2}\right)}C_k$
asked Sep 19, 2014 in Graph Theory Kathleen 5.7k views
16 votes
4 answers
17
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 Kathleen 2.6k views
26 votes
6 answers
18
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 Kathleen 3.5k views
23 votes
2 answers
19
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 or column, is $\leq a +b$ $\leq \max(a, b)$ $\leq \min(M-a, N-b)$ $\leq \min(a, b)$
asked Sep 19, 2014 in Linear Algebra Kathleen 3.7k views
42 votes
6 answers
20
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 Kathleen 5.2k views
17 votes
3 answers
21
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 Kathleen 3k views
33 votes
7 answers
22
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? $\{1\}$ $\{1\}, \{2, 3\}$ $\{1\}, \{1, 3\}$ $\{1\}, \{1, 3\}, \{1, 2, 3, 4\}, \{1, 2, 3, 5\}$
asked Sep 19, 2014 in Set Theory & Algebra Kathleen 3.8k views
25 votes
3 answers
23
The following is the incomplete operation table of a $4-$ ... $c\;a\;e\; b$ $c\; b\; a\; e$ $c\; b\; e\; a$ $c\; e\; a\; b$
asked Sep 19, 2014 in Set Theory & Algebra Kathleen 2.3k views
18 votes
3 answers
24
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 Kathleen 2.4k views
22 votes
2 answers
25
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 Kathleen 2.4k views
30 votes
4 answers
26
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$ $nanoseconds$ each. Assuming constant clocking rate, the total time taken to process $1000$ data items ... will be: $\text{120.4 microseconds}$ $\text{160.5 microseconds}$ $\text{165.5 microseconds}$ $\text{590.0 microseconds}$
asked Sep 19, 2014 in CO and Architecture Kathleen 6.4k views
39 votes
9 answers
27
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 CO and Architecture Kathleen 11.3k views
29 votes
2 answers
28
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 of $13$ bits, a next address field $(X),$ and a MUX select field $(Y).$ There are $8$ status bits in the input of the MUX. ... 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 and Architecture Kathleen 5.2k views
16 votes
4 answers
29
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$
asked Sep 19, 2014 in Digital Logic Kathleen 5.3k views
13 votes
3 answers
30
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 number of cache misses for the following sequence of block addresses is: $8, 12, 0, 12, 8$. $2$ $3$ $4$ $5$
asked Sep 19, 2014 in CO and Architecture Kathleen 5.8k views
...