lecture

algorithm - a recipe

search algorithms
Linear search vs. binary search
choose a good algorithm, because CPU speed can only go so far


Linear search - sequentially examine each element in collection, see if it is what you are looking for

int i = 0;
while(A[i] != 6)
{
i = i + 1;
}
if (A[i] == 6)
cout << "We found it at position " << i;
else
cout << "Sorry, we did not find it";

Analysis of Algorithms
Euler's rule
sum of:
1 + 2 + 3 ..... + n
(n+1) * (n/2) =
(n^2 + n) / 2
divide by n
about n
on the order of n
O(n)

What if the numbers are sorted?
we can use binary search.
is O(log n)
log base 2 of n

1 million elements in my collection
in linear search, about 1 million operations
in binary search, about 20 operations

Computers cannot do everything

http://www.claymath.org/millennium/

Traveling salesman problem
not solvable in amount of time we have
using algorithm i described


next quiz next wednesday