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.

Â