Recent activity by ShiveshRoy / GATE Overflow for GATE CSE

1 answer

1

CMI2010-A-10
Consider the following statements. NP-complete problems are those that we know we can never solve efficiently. If we find an efficient algorithm for one NP-complete problem, then we can solve all NP-complete problems efficiently. Checking whether a number is a prime is an NP-complete ... are false but $2$ is true. $2$ and $3$ are true but $1$ is false. All three statements are false.

Consider the following statements.NP-complete problems are those that we know we can never solve efficiently.If we find an efficient algorithm for one NP-complete problem...

774 views

answer edited May 2, 2018

2 answers

2

CMI2010-A-07
For integer values of $n$, the expression $\frac{n(5n + 1)(10n + 1)}{6}$ Is always divisible by $5$. Is always divisible by $3$. Is always an integer. None of the above

For integer values of $n$, the expression $\frac{n(5n + 1)(10n + 1)}{6}$Is always divisible by $5$.Is always divisible by $3$.Is always an integer.None of the above

893 views

commented May 2, 2018

2 answers

3

GATE CSE 1994 | Question: 1.12
Generation of intermediate code based on an abstract machine model is useful in compilers because it makes implementation of lexical analysis and syntax analysis easier syntax-directed translations can be written for intermediate code generation it ... the compiler it is not possible to generate code for real machines directly from high level language programs

Generation of intermediate code based on an abstract machine model is useful in compilers becauseit makes implementation of lexical analysis and syntax analysis easiersyn...

20.1k views

comment edited Jan 9, 2018

4 answers

4

GATE CSE 2014 Set 1 | Question: 45
Consider the $4\text{-to-1}$ multiplexer with two select lines $ S_1$ and $ S_0 $ given below The minimal sum-of-products form of the Boolean expression for the output $F$ of the multiplexer is $\bar{P}Q + Q\bar{R} + P\bar{Q}R$ $\bar{P}Q + \bar{P}Q\bar{R} + PQ\bar{R} + P\bar{Q}R$ $\bar{P}QR + \bar{P}Q\bar{R} + Q\bar{R} + P\bar{Q}R$ $PQ\bar{R}$

Consider the $4\text{-to-1}$ multiplexer with two select lines $ S_1$ and $ S_0 $ given below The minimal sum-of-products form of the Boolean expression for the output $F...

13.2k views

commented Jan 7, 2018

6 answers

5

GATE CSE 2003 | Question: 45
The literal count of a Boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of $\left(xy+xz'\right)$ is $4.$ What are the minimum possible literal counts of the product-of-sum and sum-of-product ... ? Here, $X$ denotes "don't care" $(11, 9)$ $(9, 13)$ $(9, 10)$ $(11,11)$

The literal count of a Boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of $\left(xy+xz'\right)...

16.1k views

commented Jan 6, 2018

3 answers

6

TIFR CSE 2015 | Part B | Question: 6
Let $B$ consist of all binary strings beginning with a $1$ whose value when converted to decimal is divisible by $7$. $B$ can be recognized by a deterministic finite state automaton. $B$ can be recognized by a non-deterministic ... not by a deterministic push-down automaton. $B$ cannot be recognized by any push down automaton, deterministic or non-deterministic.

Let $B$ consist of all binary strings beginning with a $1$ whose value when converted to decimal is divisible by $7$.$B$ can be recognized by a deterministic finite state...

2.0k views

commented Dec 7, 2017

6 answers

7

TIFR CSE 2015 | Part B | Question: 8
Let $\sum_{1}= \left\{a\right\}$ be a one letter alphabet and $\sum_{2}= \left\{a, b\right\}$ be a two letter alphabet. A language over an alphabet is a set of finite length words comprising letters of the alphabet. Let $L_{1}$ and $L_{2}$ be the ... $L_{1}$ is countable but $L_{2}$ is not. $L_{2}$ is countable but $L_{1}$ is not. Neither of them is countable.

Let $\sum_{1}= \left\{a\right\}$ be a one letter alphabet and $\sum_{2}= \left\{a, b\right\}$ be a two letter alphabet. A language over an alphabet is a set of finite len...

4.6k views

answered Dec 7, 2017

2 answers

8

TIFR CSE 2015 | Part B | Question: 10
Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$ $L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \leq 10\right\}$ State which of the ... $L_{1}$ is regular and $L_{2}$ is not regular. $L_{1}$ is not regular and $L_{2}$ is regular. Both $L_{1}$ and $L_{2}$ are infinite.

Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$$L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wed...

3.0k views

commented Dec 7, 2017

5 answers

9

TIFR CSE 2015 | Part B | Question: 15
Consider the following grammar (the start symbol is $E$) for generating expressions. $E \rightarrow T - E \mid T + E \mid T$ $T \rightarrow T * F \mid F$ $F \rightarrow 0 \mid1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9$ With respect to this grammar, which of the following trees is the valid evaluation tree for the expression $2*3*4 - 5*6+7$?

Consider the following grammar (the start symbol is $E$) for generating expressions.$E \rightarrow T - E \mid T + E \mid T$$T \rightarrow T * F \mid F$$F \rightarrow 0 \m...

3.1k views

commented Dec 7, 2017

1 answer

10

TIFR CSE 2016 | Part B | Question: 10
A $vertex \: cover$ in an undirected graph $G$ is a subset $ C \subseteq V(G)$ such that every edge of $G$ has an endpoint in $C$. An independent set in $G$ is a subset $I \subseteq V(G)$ such that no edge has both its endpoints in $I$. Which of the ... $\mid C \mid \: \: \geq \: \: \mid V(G)\mid /2$ $C$ intersects every independent set

A $vertex \: cover$ in an undirected graph $G$ is a subset $ C \subseteq V(G)$ such that every edge of $G$ has an endpoint in $C$. An independent set in $G$ is a subset $...

829 views

commented Dec 6, 2017

1 answer

11

TIFR CSE 2016 | Part B | Question: 12
A computer program computes a function $\: f \: \{0, 1\}^* \times \{0, 1\}^* \rightarrow \{0, 1\}^*$. Suppose $f(a, b)$ ahs length $\mid b \mid ^2$, where $\mid a \mid$ and $\mid b \mid$ are the lengths of $a$ and $b$. Suppose, using this program, the following ... $n^2 < t \leq n^{\log_2 n}$ $ n^{\log_2 n} < t \leq 2^{(2n)}$ $2^{(2n)} < t$

A computer program computes a function $\: f \: \{0, 1\}^* \times \{0, 1\}^* \rightarrow \{0, 1\}^*$. Suppose $f(a, b)$ ahs length $\mid b \mid ^2$, where $\mid a \mid$ a...

734 views

commented Dec 6, 2017

3 answers

12

TIFR CSE 2017 | Part A | Question: 4
Which of the following functions asymptotically grows the fastest as $n$ goes to infinity? $(\log \: \log \: n)!$ $(\log \: \log \: n)^ {\log \: n}$ $(\log \: \log \: n)^{\log \: \log \: \log \: n}$ $(\log \: n)^{\log \: \log \: n}$ $2^{\sqrt{\log \: \log \: n}}$

Which of the following functions asymptotically grows the fastest as $n$ goes to infinity?$(\log \: \log \: n)!$$(\log \: \log \: n)^ {\log \: n}$$(\log \: \log \: n)^{\l...

4.0k views

commented Dec 6, 2017

2 answers

13

TIFR CSE 2017 | Part B | Question: 4
Let $L$ be the language over the alphabet $\{1, 2, 3, (, )\}$ generated by the following grammar (with start symbol $S$, and non-terminals $\{A, B, C\}$ ... $L$ is finite $L$ is not recursively enumerable $L$ is regular $L$ contains only strings of even length $L$ is context-free but not regular

Let $L$ be the language over the alphabet $\{1, 2, 3, (, )\}$ generated by the following grammar (with start symbol $S$, and non-terminals $\{A, B, C\}$):$ S \rightarrow ...

2.5k views

commented Dec 6, 2017

1 answer

14

TIFR CSE 2017 | Part B | Question: 6
Consider the First Order Logic (FOL) with equality and suitable function and relation symbols. Which of the following is FALSE? Partial orders cannot be axiomatized in FOL FOL has a complete proof system Natural numbers cannot be axiomatized in FOL Real numbers cannot be axiomatized in FOL Relational numbers cannot be axiomatized in FOL

Consider the First Order Logic (FOL) with equality and suitable function and relation symbols. Which of the following is FALSE?Partial orders cannot be axiomatized in FOL...

1.2k views

commented Dec 6, 2017

1 answer

15

TIFR CSE 2017 | Part B | Question: 15
A multivariate polynomial in $n$ variables with integer coefficients has a binary root if it is possible to assign each variable either 0 or 1, so that the polynomial evaluates to 0. For example, the multivariate polynomial $-2x_1^3 -x_1x_2+2$ ... is NP-hard, but not in NP is in NP, but not in P and not NP-hard is both in NP and NP-hard

A multivariate polynomial in $n$ variables with integer coefficients has a binary root if it is possible to assign each variable either 0 or 1, so that the polynomial eva...

1.1k views

answered Dec 6, 2017

2 answers

16

TIFR CSE 2010 | Part B | Question: 35
Consider the following languages over the alphabet $\{0, 1\}$. $L1=\left \{ x.x^{R}\mid x\in \left \{ 0, 1 \right \}^* \right \}$ $L2=\left \{ x.x\mid x\in \left \{ 0, 1 \right \}^* \right \}$ Where $x^{R}$ is the ... and $L2$ are context free and neither is regular. $L1$ is context free but $L2$ is not context free. Both $L1$ and $L2$ are not context free.

Consider the following languages over the alphabet $\{0, 1\}$. $L1=\left \{ x.x^{R}\mid x\in \left \{ 0, 1 \right \}^* \right \}$ $L2=\left \{ x.x\mid x\in ...

1.8k views

commented Dec 6, 2017

3 answers

17

TIFR CSE 2010 | Part B | Question: 37
Consider the program where $a, b$ are integers with $b > 0$. x:=a; y:=b; z:=0; while y > 0 do if odd (x) then z:= z + x; y:= y - 1; else y:= y % 2; x:= 2 * x; fi Invariant of the loop is a condition which is ... terminate for some values of $a, b$ but when it does terminate, the condition $z = a * b$ will hold. The program will terminate with $z=a^{b}$

Consider the program where $a, b$ are integers with $b 0$.x:=a; y:=b; z:=0; while y 0 do if odd (x) then z:= z + x; y:= y - 1; else y:= y % 2; x:= 2 * x; fiInvariant of...

3.3k views

comment edited Dec 5, 2017

1 answer

18

Test by Bikram | Operating Systems | Test 2 | Question: 30
Consider the following 3 processes with 3 binary semaphores with initial values $S_{0}=0, S_{1}=0, S_{2}=1$ ... $3$ processes? $211$ $200$ $210$ $201$

Consider the following 3 processes with 3 binary semaphores with initial values $S_{0}=0, S_{1}=0, S_{2}=1$$$ \begin{array}{|c|c|c|} \hline \textbf{P} & \textbf{Q} & \tex...

289 views

commented Feb 4, 2017

1 answer

19

Test by Bikram | Operating Systems | Test 2 | Question: 19
Assume we have a demand-paged memory. The page table is held in registers. It takes $8$ milliseconds to service a page fault if an empty page is available or the replaced page is not modified, and $20$ milliseconds if the ... The maximum acceptable page-fault rate for an effective access time of no more than $200$ ns is __________ $\%$

Assume we have a demand-paged memory. The page table is held in registers. It takes $8$ milliseconds to service a page fault if an empty page is available or the replaced...

878 views

commented Feb 4, 2017

2 answers

20

Test by Bikram | Data Structures | Test 2 | Question: 9
Suppose you have a hash table that can hold $100$ elements. It currently stores $30$ elements (in one of $30$ possible different locations in the hash table). The probability that your next two inserts will cause at least one collision is ( by assuming a totally random hash function) __________

Suppose you have a hash table that can hold $100$ elements. It currently stores $30$ elements (in one of $30$ possible different locations in the hash table). The probab...

1.5k views

answered Feb 4, 2017

1 answer

21

Test by Bikram | Data Structures | Test 2 | Question: 14
If memory is limited and the entire dictionary cannot be stored in a hash table, we can still get an efficient algorithm that almost always works. We declare an array H_TABLE of bits (initialized to zeros) from $0$ to TABLE_SIZE $- 1$. As ... If a word hashes to a location with value $2$, the word is not in the dictionary. None of the above.

If memory is limited and the entire dictionary cannot be stored in a hash table, we can still get an efficient algorithm that almost always works. We declare an array H_T...

545 views

commented Feb 3, 2017

1 answer

22

maximum no of touples
Consider the following relation: R (A B C) A primary key with 100 tuples. S (E F G) E primary key with 50 tuples. T (AE D) AE primary key with 80 tuples. U (D G H) H primary key with 10 tuples. The maximum number of possible records in the result of (R JOIN S JOIN T JOIN U)

Consider the following relation:R (A B C) A primary key with 100 tuples.S (E F G) E primary key with 50 tuples.T (AE D) AE primary key with 80 tuples.U (D G H) H primary ...

1.1k views

commented Feb 2, 2017

3 answers

23

Test by Bikram | Computer Networks | Test 1 | Question: 28
Which among the following services is provided by the transport layer? Recovery from message loss. End to end delivery of individual messages. Correct order message delivery. All of the above.

Which among the following services is provided by the transport layer?Recovery from message loss.End to end delivery of individual messages.Correct order message delivery...

771 views

commented Jan 31, 2017

1 answer

24

Test by Bikram | Digital Logic | Test 2 | Question: 27
Which among the following statements is TRUE? A circuit containing only OR and NOT gates must be a combinational circuit. SRAM is static in the sense that if the power is turned off, SRAM will continue to store data (e.g. ... in two's complement form, the negative of a number can be found by adding one and then inverting the bits.

Which among the following statements is TRUE?A circuit containing only OR and NOT gates must be a combinational circuit.SRAM is “static” in the sense that if the powe...

706 views

commented Dec 29, 2016

1 answer

25

What should be the Token Holding Time
Can anyone explain why the answer is infinite time?

Can anyone explain why the answer is infinite time?

1.4k views

commented Jun 9, 2016

3 answers

26

Which of the following is true for the left recursive grammar

6.3k views

commented May 14, 2016

3 answers

27

Is CLR(1) grammar and LR(1) grammar are same?
Whether LR(1) grammar is same as that of CLR(1) grammar. If yes then please explain and if not then what is the difference between them?

Whether LR(1) grammar is same as that of CLR(1) grammar. If yes then please explain and if not then what is the difference between them?

12.6k views

answer selected May 13, 2016

2 answers

28

How to Eliminate Indirect Left recursion from this grammar?
$\textbf{Eliminating indirect left-recursion}$ Indirect left-recursion $S\rightarrow Aa|b$ $A\rightarrow Ac| Sd |\in$

$\textbf{Eliminating indirect left-recursion}$Indirect left-recursion$S\rightarrow Aa|b$$A\rightarrow Ac| Sd |\in$

9.1k views

comment edited May 8, 2016

1 answer

29

Logical Equivalence
Does (P ⋁ Q) ⋀ (R ⋁ S) and (P ⋀ R) ⋁ (Q ⋀ S) are equivalent and also can we write (P ⋀ R) ⋁ (Q ⋀ S) as (P ⋁ Q) ⋀ (R ⋁ S) ???

Does (P ⋁ Q) ⋀ (R ⋁ S) and (P ⋀ R) ⋁ (Q ⋀ S) are equivalentand also can we write (P ⋀ R) ⋁ (Q ⋀ S) as (P ⋁ ...

453 views

asked Apr 2, 2016

4 answers

30

What will COUNT(*) returns if all the collection has only null values?
What will COUNT(*) returns if all the collection has only null values???

What will COUNT(*) returns if all the collection has only null values???

2.1k views

asked Apr 1, 2016

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