Recent activity by goxul / GATE Overflow for GATE CSE

4 answers

1

GATE CSE 2023 | Question: 1
Consider the following statements regarding the front-end and back-end of a compiler. S1: The front-end includes phases that are independent of the target hardware. S2: The back-end includes phases that are specific to the target hardware. S3: The back-end includes phases that are ... $\mathbf{S 3}$ are all TRUE. Only $\mathbf{S 1}$ and $\mathbf{S 3}$ are TRUE.

Consider the following statements regarding the front-end and back-end of a compiler.S1: The front-end includes phases that are independent of the target hardware.S2: The...

15.2k views

commented Feb 18, 2023

5 answers

2

GATE CSE 2020 | Question: 31
Let $G = (V, E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST ... $\Theta (\mid E \mid \mid V \mid) \\$ $\Theta(E \mid \log \mid V \mid) \\$ $\Theta( \mid V \mid)$

Let $G = (V, E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) ...

19.1k views

answered Feb 12, 2020

7 answers

3

GATE CSE 2020 | Question: 26
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}$ ... $L_1$, $L_3$, and $L_4$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_2$, $L_3$, and $L_4$ only

Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M.$L_1 = \{\left \langle M \right \r...

14.6k views

commented Feb 12, 2020

2 answers

4

GATE CSE 2020 | Question: 19
A multiplexer is placed between a group of $32$ registers and an accumulator to regulate data movement such that at any given point in time the content of only one register will move to the accumulator. The number of select lines needed for the multiplexer is ______.

A multiplexer is placed between a group of $32$ registers and an accumulator to regulate data movement such that at any given point in time the content of only one regist...

6.7k views

commented Feb 12, 2020

2 answers

5

GATE CSE 2020 | Question: 45
For $n>2$, let $a \in \{0,1\}^n$ be a non-zero vector. Suppose that $x$ is chosen uniformly at random from $\{0,1\}^n$. Then, the probability that $\displaystyle{} \Sigma_{i=1}^n a_i x_i$ is an odd number is______________

For $n>2$, let $a \in \{0,1\}^n$ be a non-zero vector. Suppose that $x$ is chosen uniformly at random from $\{0,1\}^n$. Then, the probability that $\displaystyle{} \Sigm...

12.3k views

commented Feb 12, 2020

6 answers

6

GATE CSE 2020 | Question: 47
Consider the array representation of a binary min-heap containing $1023$ elements. The minimum number of comparisons required to find the maximum in the heap is ___________.

Consider the array representation of a binary min-heap containing $1023$ elements. The minimum number of comparisons required to find the maximum in the heap is _________...

15.0k views

answered Feb 12, 2020

2 answers

7

GATE2010 TF: GA-8
A gathering of $50$ linguists discovered that $4$ knew Kannada$,$ Telugu and Tamil$,$ $7$ knew only Telugu and Tamil $,$ $5$ knew only Kannada and Tamil $,$ $6$ knew only Telugu and Kannada$.$ If the number of linguists who knew Tamil is $24$ and those who knew Kannada is also $24,$ how many linguists knew only Telugu$?$ $9$ $10$ $11$ $8$

A gathering of $50$ linguists discovered that $4$ knew Kannada$,$ Telugu and Tamil$,$ $7$ knew only Telugu and Tamil $,$ $5$ knew only Kannada and Tamil $,$ $6$ knew only...

2.3k views

commented Feb 6, 2020

3 answers

8

GATE CSE 2017 Set 2 | Question: 17
An ER model of a database consists of entity types $A$ and $B$. These are connected by a relationship $R$ which does not have its own attribute. Under which one of the following conditions, can the relational table for R be merged with that of A? Relationship ... of $A$ in $R$ is total Relationship $R$ is many-to-one and the participation of $A$ in $R$ is partial

An ER model of a database consists of entity types $A$ and $B$. These are connected by a relationship $R$ which does not have its own attribute. Under which one of the fo...

22.4k views

commented Feb 1, 2020

4 answers

9

GATE CSE 2006 | Question: 59
Consider the following translation scheme. $ S\rightarrow ER$ $ R\rightarrow *E\left \{ \text{print}(\text{ }*\text{'}); \right \} R\mid \varepsilon $ $ E\rightarrow F+E\left \{ \text{print}(\text{ }+\text{'}); \right \}\mid F $ ... $2 * 3 + 4$ $2 * +3 \ 4$ $2 \ 3 * 4 +$ $2 \ 3 \ 4+*$

Consider the following translation scheme. $ S\rightarrow ER$$ R\rightarrow *E\left \{ \text{print}(\text{‘}*\text{’}); \right \} R\mid \varepsilon $$ E\rightarrow F+...

11.1k views

commented Jan 17, 2020

11 answers

10

GATE CSE 2019 | Question: 50
What is the minimum number of $2$-input NOR gates required to implement a $4$ -variable function expressed in sum-of-minterms form as $f=\Sigma(0,2,5,7, 8, 10, 13, 15)?$ Assume that all the inputs and their complements are available. Answer: _______

What is the minimum number of $2$-input NOR gates required to implement a $4$ -variable function expressed in sum-of-minterms form as $f=\Sigma(0,2,5,7, 8, 10, 13, 15)?$ ...

30.5k views

commented Jan 7, 2020

6 answers

11

GATE CSE 2008 | Question: 74
Consider the following C functions: int f1 (int n) { if(n == 0 || n == 1) return n; else return (2 * f1(n-1) + 3 * f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 3; for(i = 2 ... $f2(n)$ are $\Theta(n)$ and $\Theta(n)$ $\Theta(2^n)$ and $\Theta(n)$ $\Theta(n)$ and $\Theta(2^n)$ $\Theta(2^n)$ and $\Theta(2^n)$

Consider the following C functions:int f1 (int n) { if(n == 0 || n == 1) return n; else return (2 * f1(n-1) + 3 * f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N];...

18.9k views

commented Jan 2, 2020

5 answers

12

GATE CSE 1997 | Question: 15
Consider the following function. Function F(n, m:integer):integer; begin if (n<=0) or (m<=0) then F:=1 else F:F(n-1, m) + F(n, m-1); end; Use the recurrence relation ... value of $F(n, m)$? How many recursive calls are made to the function $F$, including the original call, when evaluating $F(n, m)$.

Consider the following function.Function F(n, m:integer):integer; begin if (n<=0) or (m<=0) then F:=1 else F:F(n-1, m) + F(n, m-1); end;Use the recurrence relation $\beg...

4.6k views

commented Jan 2, 2020

5 answers

13

GATE CSE 2018 | Question: 43
Let $G$ be a graph with $100!$ vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and $v$ if and only if the label of $u$ can be obtained by swapping two adjacent ... denote the degree of a vertex in $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z=$ ______.

Let $G$ be a graph with $100!$ vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and ...

19.9k views

commented Jan 1, 2020

2 answers

14

Design a counter for the following binary sequence: 0,4,5,3,1,6,2,7 and repeat.Use JK flip-flops | IIIT-Hyderbad

Design a counter for the following binary sequence: 0,4,5,3,1,6,2,7 and repeat.Use JK flip-flops

29.5k views

commented Dec 29, 2019

2 answers

15

MadeEasy Test Series: Digital Logic - Digital Circuits
All the logic gates in the circuit shown below have finite propagation delay. The circuit can be used as a clock generator, if a) X = 0 b) X = 1 c) X = 0 or 1 d) X = Y

All the logic gates in the circuit shown below have finite propagation delay. The circuit can be used as a clock generator, ifa) X = 0b) X = 1c) X = 0 or 1d) X = Y

3.2k views

commented Dec 29, 2019

9 answers

16

GATE CSE 2012 | Question: 40
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $S$ and $T$. Which one will be reported by Dijkstra's shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex $v$ is updated only ... a strictly shorter path to $v$ is discovered. $\text{SDT}$ $\text{SBDT}$ $\text{SACDT}$ $\text{SACET}$

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $S$ and $T$. Which one will be reported by Dijkstra’s shortest...

26.9k views

commented Dec 26, 2019

1 answer

17

consider the following
Consider a single-level cache with an access time of 2.5 ns, a line size of 64 bytes, and a hit ratio of H 0.95. Main memory uses a block transfer capability that has a first word (4 bytes) access time of 50 ns and an access time of 5 ns ... a hit. b. Suppose that increasing the line size to 128 bytes increases the H to 0.97. Does this reduce the average memory access time?

Consider a single-level cache with an access time of 2.5 ns, a line size of 64 bytes, and a hit ratio of H 0.95. Main memory uses a block transfer capability that has a f...

8.1k views

commented Dec 23, 2019

0 answers

18

Stallings (write through)
Consider a cache with a line size of 32 bytes and a main memory that requires 30 ns to transfer a 4-byte word. For any line that is written at least once before being swapped out of the cache, what is the average number of times that the line must be written before being swapped out for a write-back cache to be more efficient that a write-through cache?

Consider a cache with a line size of 32 bytes and a main memory that requires 30 ns to transfer a 4-byte word. For any line that is written at least once before being swa...

835 views

commented Dec 23, 2019

3 answers

19

GATE CSE 2006 | Question: 30
For $s\in (0+1)^{*}$ let $d(s)$ denote the decimal value of $s ($e.g. $d (101) = 5 ).$ Let $L=\left \{ s\in (0+1)^*\mid d(s) \text{ mod } 5=2 \text{ and }d(s) \text{ mod } 7\neq 4 \right \}$Which ... following statements is true? $L$ is recursively enumerable, but not recursive $L$ is recursive, but not context-free $L$ is context-free, but not regular $L$ is regular

For $s\in (0+1)^{*}$ let $d(s)$ denote the decimal value of $s ($e.g. $d (101) = 5 ).$ Let$$L=\left \{ s\in (0+1)^*\mid d(s) \text{ mod } 5=2 \text{ and }d(s) \text{ mod ...

7.7k views

commented Dec 21, 2019

4 answers

20

GATE CSE 2019 | Question: 5
Let $U = \{1, 2, \dots , n\}$ Let $A=\{(x, X) \mid x \in X, X \subseteq U \}$. Consider the following two statements on $\mid A \mid$. $\mid A \mid = n2^{n-1}$ $\mid A \mid = \Sigma_{k=1}^{n} k \begin{pmatrix} n \\ k \end{pmatrix}$ Which of the above statements is/are TRUE? Only I Only II Both I and II Neither I nor II

Let $U = \{1, 2, \dots , n\}$ Let $A=\{(x, X) \mid x \in X, X \subseteq U \}$. Consider the following two statements on $\mid A \mid$.$\mid A \mid = n2^{n-1}$$\mid A \mi...

11.6k views

commented Dec 6, 2019

12 answers

21

GATE CSE 2003 | Question: 61
In a permutation $a_1 ... a_n$, of n distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i > a_j$. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of $1. . . n$? $\frac{n(n-1)}{2}$ $\frac{n(n-1)}{4}$ $\frac{n(n+1)}{4}$ $2n[\log_2n]$

In a permutation $a_1 ... a_n$, of n distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i a_j$.If all permutations are equally likel...

22.0k views

commented Dec 6, 2019

1 answer

22

GATE CSE 1995 | Question: 15-b
What is the equivalent minimal Boolean expression (in sum of products form) for the Karnaugh map given below?

What is the equivalent minimal Boolean expression (in sum of products form) for the Karnaugh map given below?

2.6k views

commented Nov 22, 2019

2 answers

23

GATE CSE 2004 | Question: 19
If $73_x$ (in base-x number system) is equal to $54_y$ (in base $y$-number system), the possible values of $x$ and $y$ are $8, 16$ $10, 12$ $9, 13$ $8, 11$

If $73_x$ (in base-x number system) is equal to $54_y$ (in base $y$-number system), the possible values of $x$ and $y$ are$8, 16$$10, 12$$9, 13$$8, 11$

6.4k views

commented Nov 21, 2019

1 answer

24

Cormen Edition 3 Exercise 12.1 Question 5 (Page No. 289)
Argue that since sorting $n$ elements takes $\Omega (n\ lgn)$ time in the worst case in the comparison model, any comparison-based algorithm for constructing a $BST$ from an arbitrary list of n elements takes $\Omega (n\ lgn)$ time in the worst case.

Argue that since sorting $n$ elements takes $\Omega (n\ lgn)$ time in the worst case in the comparison model, any comparison-based algorithm for constructing a $BST$ fro...

1.5k views

commented Nov 21, 2019

2 answers

25

GATE CSE 2011 | Question: 41
Consider an instruction pipeline with four stages $\text{(S1, S2, S3 and S4)}$ each with combinational circuit only. The pipeline registers are required between each stage and at the end of the last stage. Delays for the stages and for the pipeline ... under ideal conditions when compared to the corresponding non-pipeline implementation? $4.0$ $2.5$ $1.1$ $3.0$

Consider an instruction pipeline with four stages $\text{(S1, S2, S3 and S4)}$ each with combinational circuit only. The pipeline registers are required between each stag...

13.7k views

commented Nov 15, 2019

3 answers

26

GATE CSE 2015 Set 2 | Question: 42
Consider a processor with byte-addressable memory. Assume that all registers, including program counter (PC) and Program Status Word (PSW), are size of two bytes. A stack in the main memory is implemented from memory location $(0100)_{16}$ and it grows upward. The stack ... value of the stack pointer is: $(016A)_{16}$ $(016C)_{16}$ $(0170)_{16}$ $(0172)_{16}$

Consider a processor with byte-addressable memory. Assume that all registers, including program counter (PC) and Program Status Word (PSW), are size of two bytes. A stack...

17.0k views

commented Nov 15, 2019

6 answers

27

GATE CSE 2014 Set 3 | Question: 49
Consider the set of all functions $f:\{0,1, \dots,2014\} \to \{0,1,\dots, 2014\}$ such that $ f\left(f\left(i\right)\right)=i$, for all $0 \leq i \leq 2014$. Consider the following statements: $P$. For each such function it must be the case that for every ... is CORRECT? $P, Q$ and $R$ are true Only $Q$ and $R$ are true Only $P$ and $Q$ are true Only $R$ is true

Consider the set of all functions $f:\{0,1, \dots,2014\} \to \{0,1,\dots, 2014\}$ such that $ f\left(f\left(i\right)\right)=i$, for all $0 \leq i \leq 2014$. Consider th...

15.6k views

commented Nov 11, 2019

8 answers

28

GATE IT 2006 | Question: 47
Consider the depth-first-search of an undirected graph with $3$ vertices $P$, $Q$, and $R$. Let discovery time $d(u)$ represent the time instant when the vertex $u$ is first visited, and finish time $f(u)$ represent the time instant when the ... are two connected components, and $Q$ and $R$ are connected There are two connected components, and $P$ and $Q$ are connected

Consider the depth-first-search of an undirected graph with $3$ vertices $P$, $Q$, and $R$. Let discovery time $d(u)$ represent the time instant when the vertex $u$ is fi...

11.2k views

commented Nov 8, 2019

6 answers

29

GATE CSE 2019 | Question: 36
Consider the following grammar and the semantic actions to support the inherited type declaration attributes. Let $X_1, X_2, X_3, X_4, X_5$, and $X_6$ be the placeholders for the non-terminals $D, T, L$ or $L_1$ ... $X_1=T, \: X_2=L, \: X_3=T, \: X_4 = L_1$

Consider the following grammar and the semantic actions to support the inherited type declaration attributes. Let $X_1, X_2, X_3, X_4, X_5$, and $X_6$ be the placeholders...

16.6k views

commented Oct 20, 2019

3 answers

30

theory of computation
Construct minimal DFA for L = {an: n is either a multiple of three or a multiple of 5 }

Construct minimal DFA for L = {an: n is either a multiple of three or a multiple of 5 }

4.9k views

commented Oct 15, 2019

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