0:01
This lecture is going to describe what an algorithm is.
So, algorithms are a way of describing what a computer can do,
and we talk about them in the context of computer science and
computational biology all the time, but algorithms don't really need computers.
An algorithm is really just a very clear,
step-by-step series of instructions on how to do something.
So here is an example of an algorithm.
It's a recipe that tells you how to make chocolate brownies.
So you preheat the oven, you melt some chocolate chips and some butter together,
cool it off, stir in some eggs, then stir in the additional ingredients,
spread them out in a pan, and bake them in an oven.
Now presuming you know what all those words mean and
you know what some of the instructions require you to do,
such as preheat the oven, this is a complete set of instructions that lets
you go from a written description to an actual product.
So algorithms don't need computers.
They're just a way of describing in full detail something that we want to get done.
So, now switching to a more computational example one, another kind of algorithm
that we often, that we often deal with is how to find a maximum in some space.
So this is, this is a common a common sort of task in a variety of optimization
problems, in computer science and computational biology and in other fields.
So one way if you were trying to find a, if you, to find a maximum,
imagine you're in a, you're actually walking around in a landscape and
you want to find the highest place in that landscape.
Well, one way you could do that is you could just look around you and
find the direction in which you would be going uphill most rapidly.
In other words, the steepest slope.
And take a step in that direction.
And just keep doing that.
And with that algorithm, if you look at this little example of,
this cartoon example here, that algorithm would take you from
a valley up to the nearest peak, to the top of the nearest peak.
At some point, following that algorithm, you wouldn't be able to proceed.
So remember, the algorithm is look around,
find the area with the steepest upward slope and go that way.
So if you're in an area where everywhere you look it's downward,
you can no longer proceed, so the algorithm would halt at that point.
Now one interesting thing about this algorithm,
there's a whole family of algorithms like this,
is that it's not actually guaranteed to find the highest point in the world.
It'll just find the highest point in your local environment.
But still, it's a useful kind of algorithm and it's a way to think about the problem.
2:14
So let me talk about a, a, another, one more algorithm, and, a very,
very common problem we have in computer science is sorting.
There's all kinds of reasons for sorting.
Sometimes we want to put things in alphabetical order,
want to put things in numeric order, or you want to rank things in some other way.
So there's many algorithms for sorting.
Here I'm going to just illustrate one of them.
Let's consider the digits 0 through 9, and suppose they're given to us and
they're not in order, and we want to sort them to put them in order.
They might be, say, attached to something else.
Maybe they're rankings of, of candidates for something and
you want to put them in the right order from, from where 0 will be the minimum.
So one algorithm for doing that says the following.
First, put all the objects in some sort of list data structure
where you can scan through the list from beginning to end.
Now go to the beginning of the list,
compare the first two objects, in this case, 6 and 3.
If they're in the wrong order, simply flip them.
And now move on and see if compare 6 to the next item in the list.
If they're in the right order, okay, we're going to go back to the beginning and now
scan forward until we find two ord, two items that are in the wrong order again.
So we do that.
We get to 8 and 1 and we say oh, wrong order, so we flip those, and
then keep going from there.
We look at 8 and 9.
They're in the right order.
So we'll go back again to the beginning of the list,
scan forward till we get the first pair which is in the wrong order.
There's 6 followed by 1, so we flip those.
We move on and continue this process, always flipping things until we,
till we find obviously the right order.
Moving back to the beginning of the list and
scanning forward until eventually the entire list is sorted.
This algorithm is guaranteed to work.
If you write this down in code, it will always sort your list.
It's not the most efficient algorithm possible, because it actually makes many
passes through the list, and depending on how scrambled the numbers were
in the beginning, it might or might not give you an answer very quickly.
So for, we'll be talking about efficiency in another lecture, but this,
this is a way of introducing idea of efficient algorithms.
So an algorithm is a complete and precise description of how to do something.
But if the amount of data you're dealing with is large,
you also want to think about, how do I do that as fast as possible?
So just because the algorithm completes, and it gives you the correct answer,
doesn't mean it's always the best algorithm to use.
And that bubble sort algorithm, which is what I've just described,
is in fact not the fastest way to sort a list of numbers.
There are better ways to do it.
Steven Salzberg, PhDProfessor
Jeff Leek, PhDAssociate Professor, Biostatistics
