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

53,304 total views, 68 views today

Some Reduction Inferences

April 19, 2016 by ibia Leave a Comment

How to solve problems by reduction?

10,880 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

10,496 total views, 5 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

23,109 total views, 14 views today

GATE Overflow
Aptitude Overflow

Answered: GATE1988-2-ii

This will clear all your doubts https://www.youtube.com/watch?time_continue=4&v=QRAL0v6yWzo&feature=emb_title [...]

Answered: Doubt Question on Transaction schedules

Answered: Doubt Question on Transaction schedules

number of view equivalant schedules = 10 and conflict equivalant = 6 anyone can suggest how to rotate the image? [...]

Answered: Andrew S. Tanenbaum (OS) Edition 4 Exercise 3 Question 41 (Page No. 259)

i) For 4096 bytes 65536 / 4096 = 16 pages(total) text = 32768 / 4096 = 8 pages data = 16386 / 4096 = 5 pages stack = 15870 / 4096 = 4 pages 8+5+4 = 17, the answer is no. ii) For 512 bytes 65536 / 512 = 128 pages(total) text = 32768 / 512 = 64 pages data = 16386 / 512 = 33 pages stack = 15870 / 512 = 31 pages 64+33+31 = 128, the answer is yes. [...]

Answered: GATE2010-1

Answered: GATE2010-1

Draw two non isomorphic graphs like this You can clearly see that |s| = |t| and both trees are different to each other but they satisfy the property mentioned in the question ANSWER: C [...]

Answered: GATE2013-26

Answered: GATE2013-26

Everything you need to know about LINE GRAPHS You won’t find anything better than this anywhere as its from NPTEL IIT MADRAS. [...]

Answered: GATE2004-54

For access control Ethernet(802.3) uses CSMA/CD. In CSMS/CD collision is resolved by binary backoff algorithm which says if a collision occurs then the stations which involved in collision have to wait $wait = k * Time$ here K is a number chosen from ($0 - 2^n-1$) n is collision number as A has Successfully Transmit 1 packet and B has undergone first collision when A and B collide again for B second collision happened as for A new packets ! collision occurred A can wait between (0 or 1) before retransmission B can wait between (0-3) before retransmission (as it… [...]

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

$\textrm{Given that:}$ $log_{10}(2^x+x-41)=x(1-log_{10}5)$ $\because log_aa=1$ $\textrm{We can use this property here, $log_{10}10=1$}$ $\implies$ $log_{10}(2^x+x-41)=x(log_{10}10-log_{10}5)$ $\implies$ $log_{10}(2^x+x-41)=x(log_{10}(\frac{10}{5}))$ $(\because log_ax-log_ay=log_a(\frac{x}{y}))$ $\implies$ $log_{10}(2^x+x-41)=x(log_{10}2)$ $\implies$ $log_{10}(2^x+x-41)=log_{10}2^x$ $(\because log_ax^n=n*log_ax)$ $\textrm{compair both side we get:}$ $\implies$ $2^x+x-41=2^x$ $\implies$ $x=41$ $\textrm{Option b is correct.}$ [...]

Answered: NIELIT 2019 Feb Scientist C - Section D: 19

$\textrm{Given that:}$ $x=\frac{\sqrt10+\sqrt2}{2},y=\frac{\sqrt10-\sqrt2}{2}$ $\textrm{first find $x^2+xy+y^2$}$ $\implies$ $x^2+xy+y^2+xy-xy$ $\implies$ $x^2+2xy+y^2-xy$ $\implies$ $(x+y)^2-xy….(1)$ $\textrm{Let find x+y first:}$ $\implies$ $\frac{\sqrt10+\sqrt2}{2}+\frac{\sqrt10-\sqrt2}{2}$ $\implies$ $\frac{2*\sqrt10}{2}$ $\implies$ $x+y=$ $\sqrt10...(2)$ $\textrm{Let find x*y:}$ $\implies$ $\frac{\sqrt10+\sqrt2}{2}*\frac{\sqrt10-\sqrt2}{2}$ $\implies$ $\frac{(10-2)}{4}$ $\implies$ $x*y=$$2...(3)$ $\textrm{Substitute eq (2) &(3) into (1), we get:}$ $\implies$ $(\sqrt{10})^2-2$ $\implies$ $8$ $\textrm{Now find l$og_2(8)$,which is equal to 3}$ $\textrm{Option D is correct.}$ [...]

Answered: NIELIT 2019 Feb Scientist C - Section C: 19

$\textrm{Given that: }$ $a^x=b ….(1)$ $b^y=c ….(2)$ $c^z=a….(3)$ $\textrm{taking log in above equations we get:}$ $\implies$ $xlog_2a=log_2b$ $\implies$ $x=\frac{log_2b}{log_2a}….(4)$ $\textrm{in the same way}$ $y=\frac{log_2c}{log_2b}….(5)$ $z=\frac{log_2a}{log_2c}…..(6)$ $\textrm{multiply equations (4),(5),(6).}$ $\implies$ $x*y*z=\frac{log_2b}{log_2a}*\frac{log_2c}{log_2b}*\frac{log_2a}{log_2c}$ $\implies$ $x*y*z=1$ $\textrm{Option C is correct.}$ [...]

Logical reasoning

Each question below contains six statements followed by four sets of combinations of three; Choose the set in which the statement are logically related. A. Final year students would like a good career. B. All final year students are eligible as candidates for MBA entrance examination. C.Final year students are eligible for a good career. D. Some of those who are candidates for an MBA entrance examination are final year students. E. All those eligible as candidates for an MBA entrance examination are eligible for a good career. F. All those who would like a good career are entitled to… [...]

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

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

Now, if 6th reading is x, the x+x+3+x+8= 93.8 after solving, x=27.6 [...]

Answered: NIELIT 2019 Feb Scientist C - Section C: 15

Difference = 500 5% = 500. 100% = (500 *100)/5 = 10000. 100% is the labeled price. So, TV price = 10000 - 20% of 10000 = 80% of 10000 = 8000. [...]

%d bloggers like this: