The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
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 rawan
User rawan
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User rawan
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
6
answers
1
GATE200350
Consider the following deterministic finite state automaton $M$. Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $1$. The number of strings in $S$ that are accepted by $M$ is $1$ $5$ $7$ $8$
commented
Jul 25, 2019
in
Theory of Computation

4k
views
gate2003
theoryofcomputation
finiteautomata
normal
10
answers
2
GATE199827
Consider the following relational database schemes: COURSES (Cno, Name) PRE_REQ(Cno, Pre_Cno) COMPLETED (Student_no, Cno) COURSES gives the number and name of all the available courses. PRE_REQ gives the information about which courses are prerequisites for ... using relational algebra: List all the courses for which a student with Student_no 2310 has completed all the prerequisites.
answered
Jul 15, 2019
in
Databases

2.4k
views
gate1998
databases
relationalalgebra
normal
1
answer
3
GATE19882xvii
Construct a DAG for the following set of quadruples: E:=A+B F:=EC G:=F*D H:=A+B I:=IC J:=I+G
commented
Jun 30, 2019
in
Compiler Design

428
views
gate1988
descriptive
compilerdesign
intermediatecode
0
answers
4
GATE199015b
Complete the following production rules which generate the language:$L= \left\{a^{n} b^{n} c^{n}\mid a, b, c \in \Sigma \right\}$ where variables $R$ and $Q$ are used to move back and forth over the current string generated $S \rightarrow aYc$ ... $Qc \rightarrow cQ$ $Q \rightarrow R'c$ $cR' \rightarrow ...$ $bR' \rightarrow ...$ $aR' \rightarrow a...$
commented
Jun 29, 2019
in
Theory of Computation

220
views
gate1990
descriptive
theoryofcomputation
grammar
contextsensitive
nongate
1
answer
5
GATE199012b
Consider the following problem. Given $n$ positive integers $a_{1}, a_{2}\dots a_n,$ it is required to partition them in to two parts $A$ and $B$ such that $\sum_{i \in A} a_{i}  \sum_{i \in B} a_{i}$ is minimised Consider a greedy ... in that part whose sum in smaller at that step. Give an example with $n=5$ for which the solution produced by the greedy algorithm is not optimal.
commented
Jun 28, 2019
in
Algorithms

236
views
gate1990
descriptive
algorithms
algorithmdesigntechniques
0
answers
6
GATE199014
The following algorithm (written in pseudopascal) work on an undirected graph G program Explore (G) procedure Visit (u) begin if Adj (u) is not empty {comment:Adj (u) is the list of edges incident to u} then begin Select an edge from Adj (u); ... edges, given that each vertex can be accessed and removed from LIST in constant time. Also show that all edges of the graph are traversed.
comment edited
Jun 25, 2019
in
Algorithms

251
views
gate1990
descriptive
graphalgorithms
unsolved
3
answers
7
GATE2007IT49
Consider the following grammars. Names representing terminals have been specified in capital letters. $\begin{array}{llll}\hline \text{$G1$ :} & \text{stmnt} & \text{$ ... $G_1$ is regular Both $G_1$ and $G_2$ are regular Both $G_1$ and $G_2$ are contextfree but neither of them is regular
commented
May 22, 2019
in
Theory of Computation

3.9k
views
gate2007it
theoryofcomputation
contextfreelanguages
normal
6
answers
8
GATE200634
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
comment edited
Jan 26, 2019
in
Theory of Computation

7.3k
views
gate2006
theoryofcomputation
finiteautomata
normal
minimalstateautomata
5
answers
9
GATE200639
We consider the addition of two $2's$ complement numbers $ b_{n1}b_{n2}\dots b_{0}$ and $a_{n1}a_{n2}\dots a_{0}$. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by $ c_{n1}c_{n2}\dots c_{0}$ ... $ c_{out}\oplus c_{n1}$ $ a_{n1}\oplus b_{n1}\oplus c_{n1}$
commented
Jan 23, 2019
in
Digital Logic

6.9k
views
gate2006
digitallogic
numberrepresentation
normal
3
answers
10
GATE200632, ISRO201635
Consider the following statements about the context free grammar $G = \left \{ S \rightarrow SS, S \rightarrow ab, S \rightarrow ba, S \rightarrow \epsilon \right \} $ $G$ is ambiguous $G$ produces all strings with equal number of $a$'s and $b$'s ... PDA. Which combination below expresses all the true statements about $G$? I only I and III only II and III only I, II and III
comment edited
Jan 23, 2019
in
Compiler Design

8.1k
views
gate2006
compilerdesign
grammar
normal
isro2016
2
answers
11
Inherently ambiguous grammar
Q Which one of following languages is inherently ambiguous? (A) The set of all strings of the form $\left\{a^nb^n,n>0 \right\}$ (B) $\left\{a^nb^nc^md^m,n,m>0 \right\}$ ... (D) Both (B) and (C) Plz explain.. ..........Is there any criteria on the basis of which we could identify inherently ambiguous grammar
commented
Jan 23, 2019
in
Theory of Computation

6k
views
theoryofcomputation
inherentlyambiguous
12
answers
12
GATE2007IT83
The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. What is the maximum cardinality of the request set, so that the head changes its direction after servicing every request if the total number of tracks are $2048$ and the head can start from any track? $9$ $10$ $11$ $12$
commented
Jan 22, 2019
in
Operating System

6.5k
views
gate2007it
operatingsystem
diskscheduling
normal
4
answers
13
GATE20064
A relation $R$ is defined on ordered pairs of integers as follows: $(x,y)R(u,v) \text{ if } x<u \text{ and } y>v$ Then R is: Neither a Partial Order nor an Equivalence Relation A Partial Order but not a Total Order A total Order An Equivalence Relation
commented
Jan 22, 2019
in
Set Theory & Algebra

1.8k
views
gate2006
settheory&algebra
normal
relations
11
answers
14
GATE2007IT28
Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed $0.5$. $5$ $6$ $7$ $10$
comment reshown
Jan 19, 2019
in
DS

6.6k
views
gate2007it
datastructures
hashing
probability
normal
3
answers
15
GATE2006IT32
Let $L$ be a contextfree language and $M$ a regular language. Then the language $L ∩ M$ is always regular never regular always a deterministic contextfree language always a contextfree language
commented
Jan 17, 2019
in
Theory of Computation

2.3k
views
gate2006it
theoryofcomputation
closureproperty
easy
4
answers
16
GATE2006IT21
Consider the following first order logic formula in which $R$ is a binary relation symbol. $∀x∀y (R(x, y) \implies R(y, x))$ The formula is satisfiable and valid satisfiable and so is its negation unsatisfiable but its negation is valid satisfiable but its negation is unsatisfiable
commented
Jan 16, 2019
in
Mathematical Logic

4.4k
views
gate2006it
mathematicallogic
normal
firstorderlogic
7
answers
17
GATE2006IT9
In a binary tree, the number of internal nodes of degree $1$ is $5$, and the number of internal nodes of degree $2$ is $10$. The number of leaf nodes in the binary tree is $10$ $11$ $12$ $15$
commented
Jan 16, 2019
in
DS

5.3k
views
gate2006it
datastructures
binarytree
normal
4
answers
18
GATE2005IT55
A binary search tree contains the numbers $1, 2, 3, 4, 5, 6, 7, 8.$ When the tree is traversed in preorder and the values in each node printed out, the sequence of values obtained is $5, 3, 1, 2, 4, 6, 8, 7.$ If the tree is traversed in postorder, the sequence obtained would be $8, 7, 6, 5, 4, 3, 2, 1$ $1, 2, 3, 4, 8, 7, 6, 5$ $2, 1, 4, 3, 6, 7, 8, 5$ $2, 1, 4, 3, 7, 8, 6, 5$
commented
Jan 15, 2019
in
DS

3k
views
gate2005it
datastructures
binarysearchtree
normal
6
answers
19
GATE2005IT50
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most $2$. If the height of the tree is $h > 0$, then the minimum number of nodes in the tree is $2^{h1}$ $2^{h1} + 1$ $2^h  1$ $2^h$
comment edited
Jan 15, 2019
in
DS

4.1k
views
gate2005it
datastructures
binarytree
normal
4
answers
20
GATE2005IT32
An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the trials are independent, the expected number of tosses is $3$ $4$ $5$ $6$
comment edited
Jan 13, 2019
in
Probability

5.8k
views
gate2005it
probability
binomialdistribution
expectation
normal
3
answers
21
GATE2005IT9
A dynamic RAM has a memory cycle time of $64$ $\text{nsec}$. It has to be refreshed $100$ times per msec and each refresh takes $100$ $\text{nsec}$ . What percentage of the memory cycle time is used for refreshing? $10$ $6.4$ $1$ $0.64$
comment edited
Jan 11, 2019
in
Digital Logic

2.9k
views
gate2005it
digitallogic
memoryinterfacing
normal
4
answers
22
GATE200351
Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$ Which of the following statements is true? $G$ ... $xy \notin L(G)$ There is a deterministic pushdown automaton that accepts $L(G)$ We can find a deterministic finite state automaton that accepts $L(G)$
comment edited
Jan 11, 2019
in
Theory of Computation

4k
views
gate2003
theoryofcomputation
contextfreelanguages
normal
2
answers
23
GATE200584a
We are given $9$ tasks $T_1, T_2, \dots, T_9$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ and a deadline $d_i$. Profit $P_i$ is earned if the task is completed before the end ... maximum profit? All tasks are completed $T_1$ and $T_6$ are left out $T_1$ and $T_8$ are left out $T_4$ and $T_6$ are left out
commented
Jan 10, 2019
in
Algorithms

2.8k
views
gate2005
algorithms
greedyalgorithm
processschedule
normal
0
answers
24
What is a good resource to learn all the rules of modular arithmetic?
For example, is there a way to calculate the value of $(7 \times 11 \times 13 \times 17) \% 5$ in terms of the values of $7\%5, 11\%5, 13\%5,$ and $17\%5 $ ?
commented
Jan 10, 2019
in
Mathematical Logic

28
views
3
answers
25
GATE200582b
Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges that have ... weighted spanning tree a weighted shortest path from $s$ to $t$ an Euler walk from $s$ to $t$ a Hamiltonian path from $s$ to $t$
commented
Jan 10, 2019
in
Algorithms

1.9k
views
gate2005
algorithms
graphalgorithms
normal
7
answers
26
GATE200550
Let $G(x) = \frac{1}{(1x)^2} = \sum\limits_{i=0}^\infty g(i)x^i$, where $x < 1$. What is $g(i)$? $i$ $i+1$ $2i$ $2^i$
commented
Jan 10, 2019
in
Combinatory

1.8k
views
gate2005
normal
generatingfunctions
2
answers
27
GATE200547
Which one of the following graphs is NOT planar? G1 G2 G3 G4
commented
Jan 10, 2019
in
Graph Theory

1.8k
views
gate2005
graphtheory
graphplanarity
normal
outofsyllabusnow
5
answers
28
GATE200542
Let $R$ and $S$ be any two equivalence relations on a nonempty set $A$. Which one of the following statements is TRUE? $R$ $∪$ $S$, $R$ $∩$ $S$ are both equivalence relations $R$ $∪$ $S$ is an equivalence relation $R$ $∩$ $S$ is an equivalence relation Neither $R$ $∪$ $S$ nor $R$ $∩$ $S$ are equivalence relations
commented
Jan 10, 2019
in
Set Theory & Algebra

2.1k
views
gate2005
settheory&algebra
normal
relations
5
answers
29
GATE20058
Let $A, B$ and $C$ be nonempty sets and let $X = ( A  B )  C$ and $Y = ( A  C )  ( B  C ).$ Which one of the following is TRUE? $X = Y$ $X ⊂ Y$ $Y ⊂ X$ None of these
commented
Jan 9, 2019
in
Set Theory & Algebra

1.3k
views
gate2005
settheory&algebra
easy
sets
1
answer
30
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
commented
Jan 8, 2019
in
Mathematical Logic

1.8k
views
gate2004
mathematicallogic
normal
propositionallogic
4
answers
31
GATE200458
A circuit outputs a digit in the form of $4$ bits. $0$ is represented by $0000$, $1$ by $0001$, …, $9$ by $1001$. A combinational circuit is to be designed which takes these $4$ bits as input and outputs $1$ if the digit $\geq$ $5$, and $0$ otherwise. If only AND, OR and NOT gates may be used, what is the minimum number of gates required? $2$ $3$ $4$ $5$
commented
Jan 8, 2019
in
Digital Logic

2.7k
views
gate2004
digitallogic
normal
minnogates
4
answers
32
GATE200448
Consider two processes $P_1$ and $P_2$ accessing the shared variables $X$ and $Y$ protected by two binary semaphores $S_X$ and $S_Y$ respectively, both initialized to 1. $P$ and $V$ denote the usual semaphore operators, where $P$ decrements the semaphore value, and $V$ increments the semaphore value. The ... $P(S_X), P(S_X); P(S_Y), P(S_Y)$ $P(S_X), P(S_Y); P(S_X), P(S_Y)$
commented
Jan 8, 2019
in
Operating System

3.5k
views
gate2004
operatingsystem
processsynchronization
normal
4
answers
33
GATE2008IT34
Consider a CFG with the following productions. $S \to AA \mid B$ $A \to 0A \mid A0 \mid 1$ $B \to 0B00 \mid 1$ $S$ is the start symbol, $A$ and $B$ ... $\{0, 1\}$ containing at least two $0$'s
commented
Jan 1, 2019
in
Theory of Computation

2.4k
views
gate2008it
theoryofcomputation
contextfreelanguages
normal
2
answers
34
Self Doubt on serializable
Why is Blind write necessary for a view serializable schedule that is not conflict serializable?
commented
Dec 30, 2018
in
Databases

119
views
transactions
view_serializable
1
answer
35
regular expression
the regular expression for the given finite automata plz provide ans step by step
commented
Dec 24, 2018
in
Theory of Computation

64
views
regularexpressions
1
answer
36
Context Free Grammar
Is 0^n 1^n 0^n 1^n where n>=0 a CFG ? Its given that its not CFG , please explain how ?
answered
Dec 23, 2018
in
Theory of Computation

35
views
1
answer
37
[Personal Doubt] View Serializability
Is every serializable schedule view serializable?, or like conflict serializable, there could be a serializable schedule which isn’t view serializable?
answered
Dec 23, 2018
in
Databases

53
views
view_serializable
databases
concurrency
6
answers
38
GATE201227
Consider the following transactions with data items $P$ and $Q$ initialized to zero: ${\begin{array}{clrc}\hline \textbf{$ ... execution leads to a serializable schedule a schedule that is not conflict serializable a conflict serializable schedule a schedule for which a precedence graph cannot be drawn
answer edited
Dec 23, 2018
in
Databases

5.4k
views
gate2012
databases
transactions
normal
9
answers
39
GATE200314
The regular expression $0^*(10^*)^*$ denotes the same set as $(1^*0)^*1^*$ $0+(0+10)^*$ $(0+1)^*10(0+1)^*$ None of the above
comment edited
Dec 7, 2018
in
Theory of Computation

4.2k
views
gate2003
theoryofcomputation
regularexpressions
easy
4
answers
40
GATE2015351
Consider the following reservation table for a pipeline having three stages $S_1, S_2 \text{ and } S_3$. $\begin{array}{ccccc} \hline \textbf{Time} \rightarrow \\\hline & \text{1}& \text{2} & \text{$3$} & \text{$4$} & \text{$ ... $} & & & \text{$X$} & \\\hline \end{array}$ The minimum average latency (MAL) is ______
comment edited
Dec 7, 2018
in
CO and Architecture

13k
views
gate20153
coandarchitecture
pipelining
difficult
numericalanswers
50,741
questions
57,235
answers
197,995
comments
104,580
users