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 […]

80,879 total views, 22 views today

Some Reduction Inferences

April 19, 2016 by ibia Leave a Comment

How to solve problems by reduction?

15,482 total views, 5 views today

Grammar: Decidable and Undecidable Problems

December 7, 2015 by Arjun Suresh 9 Comments

Decidable and undecidable problems on context free grammars.

44,211 total views, 7 views today

Closure Property of Language Families

December 7, 2015 by Arjun Suresh 9 Comments

Closure Properties of language families

69,767 total views, 11 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,608 total views, 2 views today

GATE Overflow
Aptitude Overflow

The below question is from Made Easy Test series The diagram shows single bus detached DMA configuration for a system. How many times system bus is used for single data transfer using DMA(Consider only data transfer, not command or status transfer) 1 2 3 0 Here answer according to their solution is option B. Reason: One access of system bus for data transfer from i/o to DMA and other for data transfer from DMA to memory. My Doubt: In DMA their is direct data transfer from i/o to memory so system bus is accessed only once. Is this… [...]

Answered: igate Test Series

Since the question directly mentions the sorting algorithm name that is merge sort and we can use a modified merge sort that returns the number of inversions of an array A[1 ∶ N] in O(N log N) time. Reference. → Cormen(3rd ed.), Chap-2, Page no-42 The key idea is to use the array index to find the number of inversions(as we know that while finding inversions two things (1: i < j, 2: A[i] >A[j] ) are of prime importance.) we use the fact that if we replace an element by its position in the same sorted array, the inverse count will remain the… [...]

Answered: Regular expression

Yes ! it is starting and ending with a. and both contains same strings. [...]

Answered: Compiler Design: Syntax Directed Translation

*+ for sure [...]

Answered: made easy gate cs question bank

y=10 [...]

Answered: C- programming

Before the Int Main() datatype and variable declared [...]

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: