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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent activity by goxul
User goxul
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User goxul
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
3
answers
1
GATE2020CS31
Let $G = (V, G)$ 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 of the ... $\Theta (\mid E \mid \mid V \mid) \\$ $\Theta(E \mid \log \mid V \mid) \\$ $\Theta( \mid V \mid)$
answered
Feb 12
in
Algorithms

2.3k
views
gate2020cs
algorithms
6
answers
2
GATE2020CS26
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
commented
Feb 12
in
Theory of Computation

1.4k
views
gate2020cs
theoryofcomputation
decidability
3
answers
3
GATE2020CS19
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 ______.
commented
Feb 12
in
Digital Logic

1.2k
views
gate2020cs
numericalanswers
digitallogic
3
answers
4
GATE2020CS45
For $n>2$, let $a \in \{0,1\}^n$ be a nonzero 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______________
commented
Feb 12
in
Mathematical Logic

1.3k
views
gate2020cs
numericalanswers
3
answers
5
GATE2020CS47
Consider the array representation of a binary minheap containing $1023$ elements. The minimum number of comparisons required to find the maximum in the heap is ___________.
answered
Feb 12
in
Algorithms

1.5k
views
gate2020cs
numericalanswers
algorithms
2
answers
6
GATE2010 TF: GA8
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$
commented
Feb 6
in
Numerical Ability

314
views
generalaptitude
numericalability
gate2010tf
venndiagrams
3
answers
7
GATE2017217
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 $R$ is ... participation of $A$ in $R$ is total Relationship $R$ is manytoone and the participation of $A$ in $R$ is partial
commented
Feb 1
in
Databases

6.5k
views
gate20172
databases
erdiagram
normal
3
answers
8
GATE200659
Consider the following translation scheme. $ S\rightarrow ER$ $ R\rightarrow ^{*}E\left \{ print('*'); \right \} R\mid \varepsilon $ $ E\rightarrow F+E\left \{ print('+'); \right \}\mid F $ $ F\rightarrow (S)\mid id \left \{ print(id.value); \right \} $ Here id is a token that represents ... $2 * 3 + 4$ $2 * +3 \ 4$ $2 \ 3 * 4 +$ $2 \ 3 \ 4+*$
commented
Jan 17
in
Compiler Design

3.4k
views
gate2006
compilerdesign
grammar
normal
11
answers
9
GATE201950
What is the minimum number of $2$input NOR gates required to implement a $4$ variable function expressed in sumofminterms form as $f=\Sigma(0,2,5,7, 8, 10, 13, 15)?$ Assume that all the inputs and their complements are available. Answer: _______
commented
Jan 7
in
Digital Logic

8.7k
views
gate2019
numericalanswers
digitallogic
canonicalnormalform
3
answers
10
GATE200874
Consider the following C functions: int f1 (int n) { if(n == 0  n == 1) return n; else return (2 * f1(n1) + 3 * f1(n2)); } 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; i <= n ... $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)$
commented
Jan 2
in
Algorithms

6k
views
gate2008
algorithms
timecomplexity
normal
2
answers
11
GATE199715
Consider the following function. Function F(n, m:integer):integer; begin If (n<=0 or (m<=0) then F:=1 else F:F(n1, m) + F(n, m1); end; Use the recurrence relation ... the value of $F(n, m)$? How many recursive calls are made to the function $F$, including the original call, when evaluating $F(n, m)$.
commented
Jan 2
in
Algorithms

837
views
gate1997
algorithms
recurrence
normal
4
answers
12
GATE201843
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 numbers in the label ... $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z$ = ____
commented
Jan 2
in
Algorithms

7.2k
views
gate2018
algorithms
graphalgorithms
graphconnectivity
numericalanswers
2
answers
13
Design a counter for the following binary sequence: 0,4,5,3,1,6,2,7 and repeat.Use JK flipflops  IIITHyderbad
commented
Dec 30, 2019
in
Digital Logic

13.6k
views
digitallogic
flipflop
2
answers
14
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
commented
Dec 29, 2019
in
Digital Logic

1.1k
views
madeeasytestseries
digitallogic
digitalcircuits
7
answers
15
GATE201240
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 when a strictly shorter path to $v$ is discovered. $\text{SDT}$ $\text{SBDT}$ $\text{SACDT}$ $\text{SACET}$
commented
Dec 27, 2019
in
Algorithms

8.3k
views
gate2012
algorithms
graphalgorithms
normal
1
answer
16
consider the following
Consider a singlelevel 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?
commented
Dec 24, 2019
in
CO and Architecture

2.8k
views
cachememory
0
answers
17
Stallings (write through)
Consider a cache with a line size of 32 bytes and a main memory that requires 30 ns to transfer a 4byte 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 writeback cache to be more efficient that a writethrough cache?
commented
Dec 23, 2019
in
CO and Architecture

96
views
coandarchitecture
cachememory
write_through
1
answer
18
GATE200630
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 one of the following statements is true? $L$ is recursively enumerable, but not recursive $L$ is recursive, but not contextfree $L$ is contextfree, but not regular $L$ is regular
commented
Dec 22, 2019
in
Theory of Computation

2.3k
views
gate2006
theoryofcomputation
normal
identifyclasslanguage
3
answers
19
GATE20195
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^{n1}$ $\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
commented
Dec 6, 2019
in
Combinatory

3.8k
views
gate2019
engineeringmathematics
discretemathematics
combinatory
10
answers
20
GATE200361
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(n1)}{2}\) \(\frac{n(n1)}{4}\) \(\frac{n(n+1)}{4}\) \(2n[\log_2n]\)
commented
Dec 6, 2019
in
Algorithms

6.4k
views
gate2003
algorithms
sorting
normal
1
answer
21
GATE199515b
What is the equivalent minimal Boolean expression (in sum of products form) for the Karnaugh map given below?
commented
Nov 22, 2019
in
Digital Logic

579
views
gate1995
digitallogic
kmap
normal
1
answer
22
GATE19894x
Provide short answers to the following questions: A switching function is said to be neutral if the number of input combinations for which its value is 1 is equal to the number of input combinations for which its value is 0. Compute the number of neutral switching functions of $n$ variables (for a given n).
answer edited
Nov 22, 2019
in
Digital Logic

349
views
gate1989
descriptive
digitallogic
booleanalgebra
1
answer
23
GATE200419
If $73_x$ (in basex 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$
commented
Nov 22, 2019
in
Digital Logic

2.1k
views
gate2004
digitallogic
numberrepresentation
easy
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 comparisonbased algorithm for constructing a $BST$ from an arbitrary list of n elements takes $\Omega (n\ lgn)$ time in the worst case.
commented
Nov 21, 2019
in
Algorithms

265
views
cormen
algorithms
descriptive
binarysearchtree
binarytree
trees
2
answers
25
GATE201141
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 registers are as ... state under ideal conditions when compared to the corresponding nonpipeline implementation? $4.0$ $2.5$ $1.1$ $3.0$
commented
Nov 15, 2019
in
CO and Architecture

5.5k
views
gate2011
coandarchitecture
pipelining
normal
2
answers
26
GATE2015242
Consider a processor with byteaddressable 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 pointer (SP) points ... the value of the stack pointer is: $(016A)_{16}$ $(016C)_{16}$ $(0170)_{16}$ $(0172)_{16}$
commented
Nov 15, 2019
in
CO and Architecture

5.8k
views
gate20152
coandarchitecture
machineinstructions
easy
4
answers
27
GATE2014349
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$ ... the following is CORRECT? $P, Q$ and $R$ are true Only $Q$ and $R$ are true Only $P$ and $Q$ are true Only $R$ is true
commented
Nov 11, 2019
in
Set Theory & Algebra

5.8k
views
gate20143
settheory&algebra
functions
normal
4
answers
28
GATE2006IT47
Consider the depthfirstsearch 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 vertex ... There are two connected components, and $Q$ and $R$ are connected There are two connected components, and $P$ and $Q$ are connected
commented
Nov 9, 2019
in
Algorithms

3.2k
views
gate2006it
algorithms
graphalgorithms
normal
6
answers
29
GATE201936
Consider the following grammar and the semantic actions to support that inherited type declaration attributes. Let $X_1, X_2, X_3, X_4, X_5$, and $X_6$ be the placeholders for the nonterminals $D, T, L$ or $L_1$ ... $X_1=L, \: X_2=L, \: X_3=L_1, \: X_4 = T$ $X_1=T, \: X_2=L, \: X_3=T, \: X_4 = L_1$
commented
Oct 20, 2019
in
Compiler Design

3.8k
views
gate2019
compilerdesign
syntaxdirectedtranslation
2
answers
30
theory of computation
Construct minimal DFA for L = {an: n is either a multiple of three or a multiple of 5 }
commented
Oct 15, 2019
in
Theory of Computation

618
views
theoryofcomputation
finiteautomata
52,345
questions
60,506
answers
201,910
comments
95,345
users