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

60,233 total views, 28 views today

Some Reduction Inferences

April 19, 2016 by ibia Leave a Comment

How to solve problems by reduction?

12,185 total views, 10 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

11,312 total views, 2 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

26,310 total views, 6 views today

GATE Overflow
Aptitude Overflow

Answered: CMI-2019-DataScience-A: 15

A, B, C are true [...]

Answered: CMI-2019-DataScience-A: 5

$p(x) =(5x^2+6x+1)(x+1)(2x+3)=(5x+1)(x+1)^2(2x+3) $ And $q(x) =(5x^2-9x-2)(2x^2+5x+3) \\= (5x^2-10x+x-2)(2x^2+2x+3x+3)= (5x+1)(x-2)(2x+3)(x+1) $ $\therefore$ Common divisors are A.$\{ 2x+3, x+1, 5x+1\}$ [...]

Answered: CMI-2018-DataScience-A: 13

Assume there are $a,b$ and $c$ numbers of songs in the first, second and third playlist respectively.. Therefore $a+b+c=n$. The number we can choose one song from each playlist is $abc$. We have to find the maximum value of $abc$ corresponding to the condition $a+b+c=n$. Let $L=abc-\lambda(a+b+c)$ Therefore $\frac{\partial L}{\partial a}=bc-\lambda, \frac{\partial L}{\partial b}=ac-\lambda, \frac{\partial L}{\partial c}=ab-\lambda$ For $\frac{\partial L}{\partial a}=\frac{\partial L}{\partial b}=\frac{\partial L}{\partial c}=0$ we get $ab=bc=cd=\lambda$ and $a=b=c$ Therefore $a^2b^2c^2=\lambda^3 \Rightarrow a^6=\lambda^3\Rightarrow a=\sqrt{\lambda}=b=c$ By the given condition $a+b+c=n\Rightarrow 3\sqrt{\lambda}=n\Rightarrow \sqrt{\lambda}=\frac{n}{3}$ Therefore the maximum value of $abc$ is $({\sqrt{\lambda}})^3=\frac{n^3}{27}$ Therefore the number of ways of choosing three songs consisting of one song… [...]

Answered: UGCNET-June2014-II: 21

The given graph is Bipartite, 3-Regular graph on 8 vertices. Also the given graph in the question is Hypercube graph on 8 vertices i.e. the given graph is $Q_3.$ Option C is $Q_3$, So option C is correct answer. We can note that Graph in Option A,B,D have at least one vertex of degree 4, but in the given graph every vertex has degree 3, So, given graph is Not isomorphic to graph in option A,B,D. [...]

Answered: CMI2016-B-7ai

$M(101)$, Here $n=101$ which is grater then $100$ comes under $n>100$ which return $n-10$. so value of $M(101) =101-10= 91$ correct answer is $91$. [...]

Answered: CMI-2018-DataScience-A: 16

By A.M-G.M inequality we know that $\frac{a_1+a_2+\dots +a_n}{n}\geq \sqrt[n]{a_1 a_2 \dots a_n}$ Therefore we have $\frac{a+b+c+d}{4}> \sqrt[4]{abcd}$ and $\frac{u+v+w+x}{4}> \sqrt[4]{uvwx}$. [ Note: since a,b,c,d are not all equal therefore equality does not hold in this case] Multiplying these inequalities $(a+b+c+d)(u+v+w+x)>16\sqrt[4]{abcduvwx}=16$ Therefore we got option A is true [...]

Answered: TIme Compound Interest question no. 18

Let’s divide the problem in terms of cash inflows and outflows. Profit earned=Inflows-Outflows Initial Inflow=25,00,000 After 1st year:- Inflow=20%of25,00,000=5,00,000 Outflow=5,00,000(As he paid off this amount of loan at the end of 1st year) Net gain=Inflow-Outflow=0 Loan amount at the end of 1st year= 25,00,000(1.12)=28,00,000 Amount after repayment of 5,00,000=23,00,000 As CI is calculated annually, the new amount will be calculated on the outstanding amount after the end of 1st year. Amount to be paid off at the end of 2nd year=23,00,000(1.12)=2576000 After 2nd year:- Inflow=20% of 25,00,000-5,00,000 Outflow=2576000 Overall gain=Initial Inflow+Inflow in 2 yrs – outflow at the end… [...]

Answered: Logical Sequence of words

4.Infancy [...]

Answered: CAT2019-1: 37

D cannot be 7. G,K,J can be (4,7,3) in this case D=6 or (8,3,7) where D can be 6 again, (7,4,6) where D can be 3. Please refer to my points 5&6 in the below link for detailed reasoning of what values of G,K,J can be. https://aptitude.gateoverflow.in/5476/cat2019-1-35?show=7805#a7805 [...]

Answered: CAT2019-1: 36

B=9 B is the second target for decoding, B+1=1, this is only possible if 9+1=10 and another 1 carried in from previous digit addition is included making it 9+1+1=11. So, B=9. Please refer to my answer in the below link for a detailed approach. https://aptitude.gateoverflow.in/5476/cat2019-1-35?show=7805#a7805 [...]

Answered: CAT2019-1: 35

A=1 I’ll try to reason out how I decoded all the encodings in this question and will paste the reference link in the subsequent questions. B(9) H(5) A(1) A(1) G F(0) + A(1) H(5) J F(0) K F(0) A(1) A(1) F(0) G C(2) A(1) F(0) A good place to start is to figure out A & F. It’s given that F+F=F, this is only possible when F=0. A is an overflow digit of 5 digit addition for 2 numbers, this implies that A can only be 1. Max possible result of 2 digit addition including Carry-In from the previous… [...]

Answered: NIELIT 2019 Feb Scientist D - Section D: 21

Option (C) Let x litres of hydrogen peroxide solution should be added, then 0.03x + (0.3)(6) = 0.12(x + 6) x = 9.25 $\approx$ 9 litres. [...]

%d bloggers like this: