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 becomes simple, some points may be lost. So, please do refer standard text books for more information) $\textsf{P}$ Problems As the name says these problems […]

69,497 total views, 2 views today

Some Reduction Inferences

April 19, 2016 by ibia Leave a Comment

How to solve problems by reduction?

13,607 total views, 5 views today

Discussion on Decidability

October 25, 2015 by Arjun Suresh Leave a Comment

Discussion on decidability portion for GATE CSE 2016

Discussion on Decidability

October 25, 2015 by Arjun Suresh Leave a Comment

GATE CSE discussion on decidability portion of theory of Computation

12,378 total views

Identify the Class of a Given Language

September 26, 2015 by Arjun Suresh 4 Comments

How to identify the class of a language

29,058 total views, 3 views today

GATE Overflow
Aptitude Overflow

Answered: NIELIT 2021 Dec Scientist B - Section B: 94

To find the complement of any boolean expression following steps are there: Convert $0$ to $1$ and vice versa. Convert $+$ to $*$ and vice versa Take variables complement, $A\leftrightharpoons \bar A$ So complement of the given expression is as follow: $Y=ABC+AB\bar C+\bar A\bar BC+\bar ABC$ $Y=AB(C+\bar C)+\bar AC(\bar B+B)$ $Y=AB+\bar AC$ $Y^c=(\bar A+\bar B)*(A+\bar C)$ Option $(A)$ is correct. [...]

Answered: NIELIT 2021 Dec Scientist B - Section B: 62

We have 9000 4 digit numbers. now we need 4 digit number contain at most 2 different digit which is equal to total number – all 4 digits different – 3 digits different. =9000- 9*9*8*7 -9*9*8*6 [3 different digit can place 6 ways that’s why multiply by 6 in 3 different digit] = 576 (option A) [...]

Answered: NIELIT 2021 Dec Scientist B - Section B: 66

Dijkstra Algorithm cannot be applied on graph which has negatives edges as well as graph with negative cycle. If the graph has negative edge it still can give you wrong results. correct ans B. PS. https://www.quora.com/What-are-the-limitations-of-Dijkstras-algorithm-greedy-approach [...]

Answered: NIELIT 2021 Dec Scientist B - Section B: 69

page number offset m-n bit n nit logical address space =2^m. so m bit require to represent the address space page size=2^n. so n bit require for offset. so page number =m-n. Ans is option B. [...]

Answered: NIELIT 2021 Dec Scientist B - Section B: 87

Answered: NIELIT 2021 Dec Scientist B - Section B: 87

$(503201)_6\rightarrow(39601)_{10}\rightarrow(21222301)_4$ Base $6$ to base $10$ conversion: $(1*6^0+0*6^1+2*6^2+3*6^3+0*6^4+5*6^5=(39601)_{10}$ Now base $10$ to base $4$ conversion: Option $(C)$ is correct. [...]

Answered: NIELIT 2021 Dec Scientist B - Section B: 70

correct answer option B. A bottom up parser generates Reverse of Rightmost derivation . PS:-https://www.d.umn.edu/~rmaclin/cs5641/Notes/Lecture8.pdf [...]

Answered: CAT2020-1: 54

Given that, area of rectangular metal sheet $ = 135 \; \text{sq inches}.$ Now, we can draw the diagram. Diagram Let the length and breadth of the rectangle be $l$ and $b$ respectively. Let the radius of a circle be $r \; \text{inches}.$ $lb = 135$ Let the painted area be $3x.$ Then left unpainted area will be $2x.$ So, $3x + 2x = 135$ $\Rightarrow 5x = 135$ $ \Rightarrow \boxed{x = 27}$ The painted area (area of circle) $ = 3 \times 27 = 81 \; \text {sq inches}.$ The left unpainted area $ = 2 \times 27… [...]

Answered: CAT2020-1: 53

Let the volumes of $ A, B,$ and $C$ be $3x, 4x$ and $7x.$ Weights of the same volume of the metals $ A, B,$ and $C$ are in the ratio $5:2:6.$ So, the ratio of the weights in the overall alloy. $A:B:C = (3x \times5) : (4x \times 2) : (7x \times 6)$ $ \Rightarrow A:B:C = 15 : 8 : 42 $ $\therefore$ The weight of metal $C = 130 \times \frac{42}{65} = 84 \; \text{kg}.$ Short Method$:$ $\qquad \qquad A \quad B \quad C$ Volume$: \quad3 : 4 : 6$ Weight$: \quad 5 : 2 : 6 \; (1… [...]

Answered: CAT2020-1: 52

Given that, Veeru$:$ Principle $(P_{1}) = \text{Rs} \; 10000$ Rate $(R_{1}) = 5 \%$ Joy$:$ Principle $(P_{2}) = \text{Rs} \; 8000$ Rate $(R_{2}) = 10 \%$ Let the time after Joy’s investment, when the balances become equal be $n$ years. i.e., principal plus accumulated interest $ P_{1} + \left[ \dfrac{P_{1} \times R_{1} \times (n+2)}{100} \right] = P_{2} + \left[ \dfrac{P_{2} \times R_{2} \times (n)}{100} \right] $ $ \Rightarrow 10000 + \left[ \dfrac {10000 \times 5 \times (n+2)}{100} \right] = 8000 + \left[ \dfrac{ 8000 \times 10 \times (n)}{100} \right] $ $ \Rightarrow 2000 + 500 (n+2) = 800n $ $ \Rightarrow 2000 + 500n + 1000 = 800n… [...]

Answered: CAT2020-1: 51

Given that, the product of $3- \text{digit}$ numbers is more than $2$ but less than $7.$ Let the $3- \text{digit}$ number be $xyz.$ Then, $ 2< x \times y \times z < 7 $ $ \Rightarrow x \times y \times z = 3 (or) 4 (or) 5 (or) 6 $ Case$1:$ When $x \times y \times z = 3$ Three possibilities. Case$2:$ When $x \times y \times z = 4$ Six possibilities. Case$3:$ When $x \times y \times z = 5$ Three possibilities. Case$4:$ When $x \times y \times z = 6$… [...]

Answered: CAT2020-3: 75

Let us assume that the total marks is $100x$ Then Bishnu marks =$52x$ Asha marks = $64x$ Now according to the question, if $y$ is the mark obtained by Ramesh, $52x=y-23 \longrightarrow (1)$ $64x=y+34 \longrightarrow (2)$ Equation $(2)-(1)$ $\Rightarrow 12x=57 $ $\Rightarrow x= \frac{57}{12}$ $\therefore 84x=\frac{57*84}{12}=399$ Note: $84x$ means scored obtain by Gita that is $84 \%$ So option $B$ is correct. [...]

Answered: CAT2020-3: 52

Let us assume Tom age is $x$ then: Dick’s age= $3x$ Harry’s age=$2.3x=6x$ Now according to the given question, Dick’s age is 1 year less than the average age of all three, $\therefore 3x=\left (\frac{3x+6x+x}{3} \right )-1$ $\Rightarrow 3x=\left (\frac{10x}{3} \right )-1$ $\Rightarrow 1=\frac{10x}{3}-3x$ $\Rightarrow 1=\frac{10x-9x}{3}$ $\Rightarrow 1=\frac{x}{3}$ $\Rightarrow x=3$ So Tom age is $3$ year, Harry’s age is $=6x=6*3=18$ year. $\therefore$ Harry’s age is $18$ year. [...]

%d bloggers like this: