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 $\textsf{NP}$ problems. So, I thought of explaining them in an easy way. (When explanation […]

81,075 total views, 12 views today

Some Reduction Inferences

April 19, 2016 by ibia Leave a Comment

How to solve problems by reduction?

15,521 total views, 2 views today

Discussion on Decidability

October 25, 2015 by Arjun Suresh Leave a Comment

GATE CSE discussion on decidability portion of theory of Computation

13,632 total views, 1 views today

Identify the Class of a Given Language

September 26, 2015 by Arjun Suresh 4 Comments

How to identify the class of a language

32,533 total views, 6 views today

Theory of Computation Preparation Resources for GATE CSE

June 21, 2015 by Arjun Suresh 17 Comments

Materials for GATE preparation in Theory of Computation

96,266 total views, 19 views today

GATE Overflow
Aptitude Overflow

Answered: made easy test series

$T_{0}=0\ ,\ T_{1}=1\ given\ in\ question $ Let's there is $T{_{2}}=T{_{1}}+T {_{0}}$ $T{_{1}}\ will\ call\ first\ and\ return\ 1\ and\ make\ space\ for \ T{_{0}}$ $it\ means\ T{_{1}}\ and\ T{_{0}}\ will\ share\ same\ space$ $say\ n=4$ $T_{1}$ $T_{2}$ $T_{3}$ $T_{4}$ $T_{1}\ and\ T_{0}\ values\ are\ store\ in\ table\ so \ no\ need\ to\ evaluate\ them.$ $in\ this\ question\ maximum\ number\ of\ function\ call\ before\ stack\ overflow\ is\ $ $n*4=48$ n=12 [...]

Answered: GATE CSE 2014 Set 1 | Question: 39

compare in pairs like- compare arr[0],arr[1] and arr[1],arr[2] ….. total 50 comparisions for each comparison store bigger one in A list and smaller one in B list maximum of arr will be in A and min will be in B, finding max in A and min in B each will take 49 comparisions total 50+49+49=148 [...]

Answered: GATE CSE 2017 Set 2 | Question: 31

Answered: GATE CSE 2017 Set 2 | Question: 31

This is the toughest question of 2017 GATE exam but you can easily understand the answer like this….….. [...]

What is the difference between frame & fragmented packet? [...]

The DMA mechanism can be configured in a variety of ways, which are: Single-bus detached DMA. Single-bus integrated DMA-I/O I/O bus In Question – Single bus detached DMA is mentioned and in this two “system bus” cycles are needed. @Chaitanya Kale, When the data is about to be transferred, the DMA controller gets access to the system bus from the CPU. But if we consider this then bus is busy for data preparation as well as data transfer but this shouldn't happen as bus should be busy only during data transfer time. When the device has a lot of data to be transferred, we will surely… [...]

Answered: Simplified Boolean expression for A'BC+AB'C'+A'B'C'+AB'C+ABC

option d correct [...]

Answered: CAT 1996 | Question: 48

DACB [...]

Answered: NIELIT 2022 Feb Scientist C - Section D: 26

(p+1)^3 = p^3 + 1 + 3p(p+1) =[p^3+3p^2+3p] + 1 =7+1=8 therefore p+1=2 => p=1 so answer is 3 [...]

Answered: NIELIT 2022 Feb Scientist D - Section A: 30

When two values given a,b then Number of numbers between a,b (including extreme values) = a-b+1 Number of numbers between a,b (excluding extreme values) = a-b-1 From question, 1,2,3…….7position………23positon……..Last position[L] We can write as (23-7)-1=(L-23)-1 [ becoz the person exactly between me(L) and my friend(7position) is on the 23rd position ] 15=L-24 L=39(Answer) [...]

Answered: NIELIT 2022 Feb Scientist D - Section C: 1

let x = amount for he bought + amount spent on repair x--->[x+(20%of x)=1.2x]--->[1.2x-(10% of 1.2x)=1.08x]--->[1.08x+(10%of1.08x)] Given in question 1.08x+(10% of 1.08x)=1188 from this x=1000 you get Required answer = 1000 – 110 = 890. Therefore answer is option D [...]

Answered: NIELIT 2017 OCT Scientific Assistant A - Section A: 33

Part filled in $1 $ minute: $\frac{1}{10}+\frac{1}{30}=\frac{2}{15}$ Part filled in $5 $ minute: $\frac{2}{15}\times 5=\frac{2}{3}$ Unfilled part= $1-\frac{2}{3}=\frac{1}{3}$ so this is filled by tape first by alone,hence will be filled in $30\times \frac{1}{3}=10$ minute. So option (C) is correct. [...]

%d bloggers like this: