Theory of Computation

P, NP, NP-Complete, NP-Hard

July 9, 2016 by arjun Leave a Comment

It might be because of the name but many graduate students find it difficult to understand $NP$ problems. So, I thought of explaining them in an easy way. (When explanation becomes simple, some points may be lost. So, please do refer standard text books for more information) $P$ Problems As the name says these problems […]

56,098 total views, 64 views today

Some Reduction Inferences

April 19, 2016 by ibia Leave a Comment

How to solve problems by reduction?

11,355 total views, 6 views today

Grammar: Decidable and Undecidable Problems

December 7, 2015 by Arjun Suresh 9 Comments

Decidable and undecidable problems on context free grammars.

33,817 total views, 34 views today

Closure Property of Language Families

December 7, 2015 by Arjun Suresh 9 Comments

Closure Properties of language families

54,126 total views, 38 views today

Discussion on Decidability

October 25, 2015 by Arjun Suresh Leave a Comment

GATE CSE discussion on decidability portion of theory of Computation

10,787 total views, 5 views today

GATE Overflow
Aptitude Overflow

Answered: GATE2005-70

Answered: GATE2005-70

While DMA transferring 4B data from buffer to Memory which will take 4 memory cycle to transfer, in parallel disk will again generate 4B data in buffer, this will happen in pipeline fashion. [...]

Answered: GATE2008-31

Just Use digital Logic Concept. convert V → + and ^ → . So whose answer is P + Q’. They are matched :) [...]

Answered: GATE2008-30

Confused in A and C :( [...]

Answered: GATE2016-2-GA-05

Assume roots (α,β) = (2,2) because Product of roots α*β = 2*2 = 4 is satisfying as per question. Let n=3 (α^n+β^n)/(α^−n+β^−n) = (2^3+2^3)/(2^-3+2^-3) = (8+8)/(1/8)+(1/8) = 16/(1/4) = 16*4 = 64 Now trying option elimination with n=3 Option B = 4^n = 4^4= 64 Matching with our answer 64 which was calculated above [...]

Answered: GATE2003-38

Given Equation $\cdot (a*x) + (a*y) = c ............ eq(1)$ $\cdot (b*x) + (c*y) = c ............ eq(2)$ Now adding both the eqn we get $(a+b)*x + (a+c)*y =2c$ Now the solution pair(s) should also satisfy this eqn as well. Simplifying the above eqn using table $(a+b)*x + (a+c)*y =2c$ $a*x + c*y =2c$ [using ‘+’ Table a+b=a and a+c=c] ……………..eq(3) Now we have to find (x,y) such that [ $a*x=c$ and $c*y=c$ in order to get 2c in RHS in eq 3] Using ‘*’ Table we found that (i) $a*x=c$ only if x=c (ii) $c*y=c$ only if y={a,b} Therefore… [...]

Answered: GATE2014-1-39

Make pair of elements and compare value in pair, which is greater or which is smaller ?. We have 50 such pairs, then we need 50 comparisons to separate all number in two groups. One group of smaller element from each pair and one group of larger elements from each pair both containing 50 elements each To find minimum in smaller element group of 50 elements will take 49 comparisons. To find maximum in greater element group of 50 elements will take 49 comparisons. Total comparisons = 50 + 49 + 49 = 148 [...]

Answered: NIELIT 2017 DEC Scientific Assistant A - Section A: 6

All of the girls agree that the first three numbers are 995. Three of them agree that the fourth number is 9. Three agree that the fifth number is 2. Three agree that the sixth number is 6; three others agree that the seventh number is also 6. "Option A" is the best choice because it is made up of the numbers that most of the girls agree they saw. [...]

Answered: NIELIT 2016 MAR Scientist D: 8

Answered: NIELIT 2016 MAR Scientist D: 8

Correct Answer: (D) Explanation: This game introduces the idea of reciprocal causation. For example, the constraint that says “If A, then B, and if B, then A” should be transcribed in one of the following two ways, based on the configurations of the other variables in the diagram: You will run into reciprocal causation in the final constraint of this logic game. Here are the final diagrams that you should create: Notice how the reciprocal causation constraints are diagrammed. Be aware of the implications of these constraints. For instance, if $B$ is not sent (diagram B), then $A$ cannot… [...]

Answered: NIELIT 2016 MAR Scientist D: 7

Answered: NIELIT 2016 MAR Scientist D: 7

Correct Answer: (D) Explanation: This game introduces the idea of reciprocal causation. For example, the constraint that says “If A, then B, and if B, then A” should be transcribed in one of the following two ways, based on the configurations of the other variables in the diagram: You will run into reciprocal causation in the final constraint of this logic game. Here are the final diagrams that you should create: Notice how the reciprocal causation constraints are diagrammed. Be aware of the implications of these constraints. For instance, if $B$ is not sent (diagram B), then $A$ cannot… [...]

Answered: NIELIT 2016 MAR Scientist D: 6

Answered: NIELIT 2016 MAR Scientist D: 6

Correct Answer: (A) Explanation: This game introduces the idea of reciprocal causation. For example, the constraint that says “If $A$, then $B$, and if $B$, then $A$” should be transcribed in one of the following two ways, based on the configurations of the other variables in the diagram: You will run into reciprocal causation in the final constraint of this logic game. Here are the final diagrams that you should create: Notice how the reciprocal causation constraints are diagrammed. Be aware of the implications of these constraints. For instance, if $B$ is not sent (diagram B), then $A$ cannot be sent… [...]

Answered: NIELIT 2016 MAR Scientist D: 33

The answer is (C). three [...]

Answered: NIELIT 2016 MAR Scientist D: 32

The answer is (B). $K$ and $L$ [...]

%d bloggers like this: