Recent activity by rawan

6 answers

1

GATE2003-50
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

10 answers

2

GATE1998-27
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 pre-requisites for ... using relational algebra: List all the courses for which a student with Student_no 2310 has completed all the pre-requisites.

answered Jul 15, 2019 in Databases | 2.4k views

1 answer

3

GATE1988-2xvii
Construct a DAG for the following set of quadruples: E:=A+B F:=E-C G:=F*D H:=A+B I:=I-C J:=I+G

commented Jun 30, 2019 in Compiler Design | 428 views

0 answers

4

GATE1990-15b
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

1 answer

5

GATE1990-12b
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

0 answers

6

GATE1990-14
The following algorithm (written in pseudo-pascal) 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

3 answers

7

GATE2007-IT-49
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 context-free but neither of them is regular

commented May 22, 2019 in Theory of Computation | 3.9k views

6 answers

8

GATE2006-34
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

5 answers

9

GATE2006-39
We consider the addition of two $2's$ complement numbers $ b_{n-1}b_{n-2}\dots b_{0}$ and $a_{n-1}a_{n-2}\dots a_{0}$. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by $ c_{n-1}c_{n-2}\dots c_{0}$ ... $ c_{out}\oplus c_{n-1}$ $ a_{n-1}\oplus b_{n-1}\oplus c_{n-1}$

commented Jan 23, 2019 in Digital Logic | 6.9k views

3 answers

10

GATE2006-32, ISRO2016-35
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

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

12 answers

12

GATE2007-IT-83
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

4 answers

13

GATE2006-4
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

11 answers

14

GATE2007-IT-28
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

3 answers

15

GATE2006-IT-32
Let $L$ be a context-free language and $M$ a regular language. Then the language $L ∩ M$ is always regular never regular always a deterministic context-free language always a context-free language

commented Jan 17, 2019 in Theory of Computation | 2.3k views

4 answers

16

GATE2006-IT-21
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

7 answers

17

GATE2006-IT-9
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

4 answers

18

GATE2005-IT-55
A binary search tree contains the numbers $1, 2, 3, 4, 5, 6, 7, 8.$ When the tree is traversed in pre-order 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 post-order, 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

6 answers

19

GATE2005-IT-50
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^{h-1}$ $2^{h-1} + 1$ $2^h - 1$ $2^h$

comment edited Jan 15, 2019 in DS | 4.1k views

4 answers

20

GATE2005-IT-32
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

3 answers

21

GATE2005-IT-9
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

4 answers

22

GATE2003-51
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

2 answers

23

GATE2005-84a
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

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

GATE2005-82b
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

7 answers

26

GATE2005-50
Let $G(x) = \frac{1}{(1-x)^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

2 answers

27

GATE2005-47
Which one of the following graphs is NOT planar? G1 G2 G3 G4

commented Jan 10, 2019 in Graph Theory | 1.8k views

5 answers

28

GATE2005-42
Let $R$ and $S$ be any two equivalence relations on a non-empty 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

5 answers

29

GATE2005-8
Let $A, B$ and $C$ be non-empty 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

1 answer

30

GATE2004-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 valid valid a contradiction None of the above

commented Jan 8, 2019 in Mathematical Logic | 1.8k views

4 answers

31

GATE2004-58
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

4 answers

32

GATE2004-48
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

4 answers

33

GATE2008-IT-34
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

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

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

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

6 answers

38

GATE2012-27
Consider the following transactions with data items $P$ and $Q$ initialized to zero: ${\begin{array}{|c|l|r|c|}\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

9 answers

39

GATE2003-14
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

4 answers

40

GATE2015-3-51
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