jump to navigation

Random Question (1) October 25, 2009

Posted by jagadeeshbp in Uncategorized.
Tags: ,
add a comment

Are there transformers for P problems, like SAT in NP-Complete? For all problems X in P, there’s a single problem Y s.t. Y is polynomial time reducible to X?

P=NP and Erik Demaine of MIT April 27, 2009

Posted by jagadeeshbp in Uncategorized.
Tags: , , ,
add a comment

Revisiting Algorithm Analysis April 24, 2009

Posted by jagadeeshbp in Uncategorized.
Tags: , , ,
add a comment

Yet again, another subject that I dreaded due to the incomprehensible and intangible approach in which the subject was taught. One fundamental question I had was, knowing the definition of Big O notation, what does O(f(n)) really mean?

Let me try to put them in my perspective. Think that I am planning to go and buy a new shirt and I do not know what its exact cost is. But to make sure that I have enough money to buy one, I kind of predict, it would cost at the maximum of say a $1000 (I would love it as a gift, better). That is sort of the upper bound. I know that the cost will not go beyond that; even in the worst case.

Big O notation is similar to that. It defines an upperbound to the complexity of the function. Consider the case of sorting n elements, the time taken (considering time complexity, we can worry about space complexity some other time) is given by the function f(n) = n^3+n^2+1. By the definition of Big O, the upper bound is O(f(n)) = n^3. We can get this by removing all constants, and lower order terms, leaving us with just n^3.

By definition, f(n) = O(g(n)) means that for some constants n_0>0 and C>0, 0 leq f(n) leq C.g(n), forall n geq n_0

Let us try to interpret this. 0leq f(n) part means that we are considering the positive values of f(n).

Following shows how the graphs of the functions f(x) = x^3+x^2+14, f(x) = x^3 and f(x) = 2.x^3 looks like.

It is can be seen that f(x) = 2.x^3 is above f(n) = x^3+x^2+1 forall x ge 0.

So we have for f(n) = n^3+n^2+1,
O(f(n) = g(n), where g(n) = n^3, C = 2 and n_0 = 0.

Taylor’s Formula November 14, 2007

Posted by jagadeeshbp in Uncategorized.
add a comment

Let f(x) be a function continous over the closed interval, [a,b] such thatf(x) has (n+1)^{th} derivative, which is written as f^{(n+1)}(x); then:

f(b) = f(a) + f'(a) (b-a) + ... + \frac{f^{(n)}(a)}{n!} (b-a)^n + \frac{f^{(n+1)}(z)}{(n+1)!} (b-a)^{(n+1)}

PROOF:

Let

H = f(b) - f(a) - f'(a) (b-a) - .. - \frac{f^{(n)}(a) }{n!}(b-a)^n

Also,

K = \frac{H}{(b-a)^(n+1)}

Consider a polynomial,

g(x) = f(b) - f(x) - f'(x)(b-x) - f''(x)(b-x)^2... - \frac{f^{(n)}(x)}{n!}(b-x)^n - K(b-x)^{n+1}

We can see that,

g(a) = H - K(b-a)^{n+1} = 0

Similarly,

g(b) = f(b) - f(b) - f'(b)(b-b) - ... - \frac{f^{(n)}(b) }{n!}(b-b)^{n} - K(b-b)^{n+1} = 0

Fuzzy Logic April 10, 2007

Posted by jagadeeshbp in Uncategorized.
1 comment so far

This was one subject which kept haunting me through out the engineering curriculum. Not only was that my ma’am, teaching the subject, make any sense; but also, the text book, reminded me more of heiroglyphics.

Life went on smoothly, after some how I managed to pass the paper. Finally a job demanded me to shift to a far off place, requiring me to take care of myself. Its all easy I thought. All except a single job, washing. I hated washing. So I decided to buy one of the best washing machines around (all that my pocket could afford, though).

Seeing me, the shop keeper greeted me so well. I threw at him all my requirements. So he showed me a beautiful washing machine (which I hope works). It had a lot of features, gratifying the needs of the lazy soul inside me. He said it had an additional feature, it can automatically decide on the amount of water, detergent and all such inputs required, which is supported by fuzzy logic. Think of the devil, and here comes the devil himself. This theory, has decided with whatever mind it had, not to leave me alone, till my grave may be.

Even my shopkeeper keeps talking about fuzzy logic and its uses. The engineer inside me got hurt a lot. So a decision came to browse through a couple of pages on the web till I can spell the word fuzzy logic in a proper way.

I am now in my office. Is this sentance true. It is true if I am inside the office. It is false if I am outside the office. So what will happen if I am at the gate. It is partly true and partly false. Just like a half full glass is half empty too.

In normal, classic logic, every statement, proposition, has a value of 0 or 1, depending on it is true or false. So in a situation like the one mentioned previously, we cant assign a proper value like this. The value is 0.5 in that case.

Now, think of a statement P. Its truth value assignment is p. p=1 means the statement is true. p=0 means the statement is false. Here comes fun, think of those paradox that your friends used to bombard you with. Think, of a statement like, “this statement is false”.

Let’s call that statement P. Its truth value is p. The truth value for the converse of P (i.e. Not-P) is (1-p). The statement says, in words, that the truth value of P is (1-p). This means if p=0, p becomes (1-0) =1 and if p=1, (1-p) gives 0. So the value of p keeps oscillating. The only case where this becomes true is when p=0.5. That is permissible with fuzzy logic.