Non-algorithms

I think the following problem statements are not algorithms because of the reasons mentioned along. Please comment and educate me further.

1. “For a given r and p, find rth p-fibonacci integer.”

p-fibonacci(1) = 1; if r = 1;
p-fibonacci(2) = 1; if r = 2;
...
p-fibonacci(p-1) = 1; if r = p -1;
p-fibonacci(r) = p-fibonacci(p-1)+p-fibonacci(p-2)+...+p(1); for r > p -1

This could not be an algorithm because the number of non-recursions and recursions are not fixed.

2. Finding whether a given integer q is prime or not based on the following algorithm:

result = true;
for (i = 2; i < trunc(sqrt(q)+1); i++) {
p = i'th prime number
if q%p = 0 {
result = false;
break;
}
}

This could not be an algorithm because the result depends on the past runs (up to sqrt(q) prime numbers).

3. we should be able to solve traveling salesman problem for a graph only once and store it in “universal memory” – so as time passes, more and more traveling salesman problems will be solved by just look up.

However, this is not an algorithmic solution because just like #2, this also depends on the past “experience” rather than algorithm itself.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s