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

64,352 total views, 6 views today

Some Reduction Inferences

April 19, 2016 by ibia Leave a Comment

How to solve problems by reduction?

12,812 total views

Grammar: Decidable and Undecidable Problems

December 7, 2015 by Arjun Suresh 9 Comments

Decidable and undecidable problems on context free grammars.

37,355 total views, 1 views today

Closure Property of Language Families

December 7, 2015 by Arjun Suresh 9 Comments

Closure Properties of language families

60,350 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

11,749 total views, 1 views today

GATE Overflow
Aptitude Overflow

Answered: GATE CSE 2017 Set 2 | Question: 31

The following solution is based on the idea shared by @Sachin Mittal sir. Given, $g_y(z) = (1 – \beta + \beta z)^N$ $= g_y(z) = ((1 – \beta) + \beta z)^N$ Using binomial expansion, $= g_y(z) = \sum_{k=0}^{N}{\binom{N}{k}(1 – \beta)^{N-k}(\beta z)^k}$ $= g_y(z) = \sum_{k=0}^{N}{\binom{N}{k}(1 – \beta)^{N-k}(\beta)^k(z)^k}$ Let $a = (1 – \beta)$ and $b = \beta$ $= g_y(z) = \sum_{k=0}^{N}{\binom{N}{k}a^{N-k}b^k(z)^k}$ comapring $g_x(z) = \sum_{j=0}^{N}p_jz^j$ to the above $eq^n$ we know that each of the terms in the above summation will give $P(Y = j) = p_j, where$ $0 \leq j \leq N$ and $\because E(x) = \sum_{k=0}^{N}k*p_k$ $= E(x) = \sum_{k=0}^{N}{\binom{N}{k}a^{N-k}b^{k}k}$ $= E(x) = Nb(a + b)^{N-1}$… [...]

The initial IP datagram will be fragmented into two IP datagrams at I1. No other fragmentation will occur. --------------------------------------------------------------------------------------------------------- Link A-R1: Length = 940; ID = x; DF = 0; MF = 0; Offset = 0 Link R1-R2: (1) Length = 500; ID = x; DF = 0; MF = 1; Offset = 0 (2) Length = 460; ID = x; DF = 0; MF = 0; Offset = 60 Link R2-B: (1) Length = 500; ID = x; DF = 0; MF = 1; Offset = 0 (2) Length = 460; ID = x; DF = 0; MF =… [...]

Answered: Tanenbaum- Q30(Network layer)

Here μ is 2 million and λ is 1.5 million, so ρ=λ/μ is 0.75, and from queueing theory, each packet experiences a delay four times what it would in an idle system. The time in an idle system is 500 nsec, here it is 2 μsec. With 10 routers along a path, the queueing plus service time 20 μsec. #Solutioninthemanual [...]

Answered: GATE CSE 2011 | Question: 38

Given M1, M2, M3, M4 first of all we take first three matrix and see which combination is giving minimum number of multiplication. combination #1: M1*(M2*M3) → Here for M2*M3 no. of multiplication is q*r*s and then we will multiply M1 with the resultant matrix of M2*M3 and no. of multiplication will be p*q*s , so total no. of multiplication in M1*(M2*M3) is q*r*s + p*q*s = 10000 + 5000 = 15000 combination #2: (M1*M2)*M3 → Here for M1*M2 no. of multiplication is p*q*r and then we multiply M3 with the resultant matrix of M1*M2 and no. of multiplication will be p*r*s, so total no. of multiplication… [...]

Answered: UGCNET-Dec2019-II: 18

B) Sutherland-Hodgeman algorithm .. The Cohen–Sutherland algorithm is a computer-graphics algorithm used for line clipping. The algorithm divides a two-dimensional space into 9 regions and then efficiently determines the lines and portions of lines that are visible in the central region of interest (the view-port). Sutherland–Hodgman Algorithm is to clip polygon edges. A convex polygon and a convex clipping area are given. Input is in the form of vertices of the polygon in clockwise order. The Liang-Barsky algorithm is a line clipping algorithm. This algorithm is more efficient than Cohen–Sutherland line clipping algorithm and can be extended to 3-Dimensional clipping.… [...]

Answered: Andrew S. Tanenbaum Edition 5th Exercise 4 Question 20 (Page No. 352)

The smallest Ethernet frame is 512 bits, so at 1 Gbps we get 1,953,125 or almost 2 million frames/sec. However, this only works when frame bursting is operating. Without frame bursting, short frames are padded to 4096 bits, in which case the maximum number is 244,140. For the largest frame (12,144 bits), there can be as many as 82,345 frames/sec. [...]

Answered: CAT2019-2: 80

Given that , $a_{1} – a_{2}+a_{3}- a_{4}+ \dots + (-1)^{n-1} a_{n}=n \quad \longrightarrow (1)$ Now, put the various of $n$ and observe. $ n=1 \Rightarrow a_{1} = 1$ $ n=2 \Rightarrow a_{1} - a_{2} =2 \Rightarrow a_{2}=-1$ $ n=3 \Rightarrow a_{1} -a_{2} +a_{3} =3 \Rightarrow a_{3} =1$ $ n=4 \Rightarrow a_{1} -a_{2} +a_{3} -a_{4} =4 \Rightarrow a_{4} = -1$ $ n=5 \Rightarrow a_{1} – a_{2} +a_{3} - a_{4} +a_{5} =5 \Rightarrow a_{5} =1$ $ n=6 \Rightarrow a_{1}-a_{2} +a_{3}-a_{4} +a_{5} -a_{6} =6 \Rightarrow a_{6} = -1$ We observe that , when $n=\text{odd} \Rightarrow a_{\text{odd}} =1$ $ n=\text{even} \Rightarrow a_{\text{even}} = -1$ Now,… [...]

Answered: CAT2019-2: 79

Given that, $2^{6x}+2^{3x+2}-21 =0$ $ \Rightarrow \left ( {2^{3x}} \right)^2 +2^{3x}+2^2-21 =0 \longrightarrow (1)$ Let $2^{3x}$ be $K.$ Now, From equation (1,)we get $ \Rightarrow K^2 +4K-21 =0$ $ \Rightarrow k^2 +7k -3k-21 =0$ $ \Rightarrow K(k+7)-3(K+7)=0$ $ \Rightarrow (K+7)(K-3)=0$ $ \Rightarrow \boxed {K=-7,3}$ $ \Rightarrow K \neq {-7}$ because $2^{3x}$ not be $-7$ for any value of $x$ So, $ \boxed {k =3}$ $ \Rightarrow 2^{3x}=3$ Taking $\log_{2}$on the both sides. $ \Rightarrow\log_{2}2^{3x} =\log_{2}3$ $ \Rightarrow 3x \log_{2}2 = \log_{2}3$ $ \Rightarrow 3x = \log_{2}3$ $ \Rightarrow \boxed{ x = \frac {\log_{2}3}{3}}$ Correct Answer $: C$ [...]

Answered: CAT2019-2: 93

$\boxed {H^{2}=P^{2}+B^{2}}$ $ (20)^{2}=x^{2}+x^{2}$ $ \Rightarrow 400=2x^{2}$ $ \Rightarrow 200 = x^{2}$ $ \Rightarrow \sqrt{200}= x$ $ \Rightarrow x =10 \sqrt {2} $ $ \triangle{ APB } = \triangle {APC} $ $ \Rightarrow \frac{1}{2} AC \times BA = \frac {1}{2} BC \times AP$ $\boxed {\frac{AC\times BA}{BC} = AP}$ $ \Rightarrow \frac {10 \sqrt{2} \times 10 \sqrt {2}}{20}=AP$ $ \Rightarrow \frac{100 \times 2}{20}=AP$ $AP=10cm$ Correct Answer $:A$ [...]

Answered: CAT2019-2: 96

Given that, $ (2n+1) + (2n+3) + (2n+5)+ \dots + (2n+47) = 5280$ Here, the first term $a = 2n+1$ And, common difference $d = (2n+3) – (2n+1)$ $\Rightarrow d = 2n+3-2n-1 = 2 $ Let $’x’$ be the number of terms. The last term $l=a+(x-1)d$ $ \Rightarrow 2n+47 =2n+1+(x-1)2$ $ \Rightarrow 47=1+2x-2$ $ \Rightarrow 2x =48$ $ \Rightarrow \boxed {x=24}$ Now, the sum of A.P. $= \frac {x}{2} \left [ {a+l} \right]$ $ \Rightarrow 5280 = \frac {24}{2} \left [{2n+1+2n+47 } \right] $ $ \Rightarrow 12(4n +48) = 5280 $ $ \Rightarrow 12 \times 4 (n+12) =5280$ $ \Rightarrow… [...]

Answered: CAT2019-2: 100

Given that, Amal $ \Rightarrow P=12000, R=8\%$, at $1$ year compound interest. $\qquad \Rightarrow P=10000, R=6\%$, at semi-annually compound interest. When interest is calculated semi-annually then, the rate will be half and time will be doubled. $R=3\%, T=2$ years. Amal first $CI:$ $ \boxed {\text{Amount } = P \left ( 1+\frac{R}{100} \right)^T}$ $ \Rightarrow A=12000 \left (1+ \frac{8}{100} \right)^{1}$ $ \Rightarrow A=12000 \times \frac{108}{100}$ $ \Rightarrow A=12960$ $\because CI = A-P $ $\quad = 12960-12000$ $ \therefore \boxed{CI=960}$ Amal second $CI:$ $ \Rightarrow A=10000 \left (1+ \frac{3}{100} \right)^2$ $\Rightarrow A= 10000 \times \frac{103}{100} \times \frac{103}{100}$ $ \Rightarrow A=10609$ $\because CP=A-P$ $… [...]

Answered: CAT2019-2: 99

Given that, $15,{\color{Red}{19}},23,27,31,35,{\color{Red}{39}},\dots, 415 \quad \longrightarrow (1)$ $14,{\color{Red}{19}},24,29,34,{\color{Red}{39}}, \dots ,464 \quad \longrightarrow (2)$ Let $’n’$ be a number of common terms in the two sequences. Common difference in sequence $1 = 4,$ and in sequence $2 = 5.$ $\therefore$ The LCM of $(4,5)=20\quad $ (Common difference of new sequnce) Now, the sequence will be, $19,39,59,79,99,\dots , l \left(\leqslant 415\right) \quad \longrightarrow (3)$ We know that, last term $l=a+(n-1)d ,$ where $a = $ first term, $d = $ common difference, $n = $ number of terms. Now, $l \leqslant 415$ $\Rightarrow 19+(n-1)20 \leqslant 415\quad [\because a =19,d = 20]$ $\Rightarrow 19+20n-20 \leqslant 415$ $\Rightarrow… [...]

%d bloggers like this: