1. Is the problem of searching through a binary tree for a particular value a polynomial problem? Justify your answer. 2. Design an algorithm for calculating the Fibonacci series of a given number. Is...

1.
Is the problem of searching through a binary tree for a particular value a polynomial problem? Justify your answer.

2.
Design an algorithm for calculating the Fibonacci series of a given number. Is your solution efficient? Is your solution a polynomial or nonpolynomial one?

3.
Give an example of a scenario in which there is a fine line of distinction between deterministic and nondeterministic algorithms.

4.
Design a Turing machine for a palindrome detector. The program should check a string

of symbols on the tape and return a true(1) if it is a palindrome, else false(0).