0:00
In this lecture I'm going to talk about efficiency, and
the concept of computational efficiency or algorithmic efficiency.
Efficiency is a very key topic in computer science.
And it's important for all the algorithms you, you, try to implement or
try to run, especially with big data.
And genomics today really does deliver big data.
So I'm going to illustrate this topic with just one example.
So let's consider the problem of how we deliver the mail every day.
So, mail is collected from various sites, and
brought to central locations, we'll call it a warehouse.
And the warehouse for
a particular reason will contain all the mail supposed to be delivered that day.
So, one way we might consider an algorithm for delivering the mail would be that
the mailman goes in his truck to the warehouse, picks up all the mail for,
say, my house, drives over to my house,
delivers the mail and then goes back to the warehouse.
Picks up the mail for my neighbor, drives to the neighbor's house,
delivers the mail to the neighbor, and then drives back.
And so on. Now, that algorithm will definitely get
the job done.
It will get all the mail delivered but to all the people who need their mail.
But, as most of you probably realized right away,
if we're talking about more than a few houses,
this mailman is not going to get much mail delivered in the course of a day.
And the problem is that the mail truck is going back and
forth many more times than it needs to.
So, clearly it would be more efficient if the mail truck could go to the warehouse,
pick up the mail for my house, and my neighbors house, drive to my house,
deliver my mail, and then drive, or just walk, if the houses are close to each
other, to the next house, deliver the mail there, and then go back to the warehouse.
So, in the concept of algorithmic efficiency this is actually
a class of problems that sometimes called traveling salesman problems, where,
what you want to do is much more sophisticated than what I just described.
What you want to do is think about, how much mail can the truck fit?
Go to the warehouse and essentially, like to fill the truck each time,
and you'd like to deliver all that mail before going back to the warehouse.
And to do that efficiently you'd like the truck to be able to drive
to as few places as, as possible.
Covering as little distance as possible,
and getting as much mail delivered as possible in the same amount of time.
So to do that, you really want to look at say a map of all the houses in an area,
and here's a picture an overhead picture of a neighborhood.
And you want to look at an area and say, okay, [SOUND] if I can put mail for
a hundred houses or a thousand houses in the truck at once, can I find a,
a map that allows the truck to visit all those houses as efficiently as possible,
delivering a little bit of mail at each house, and then finally, at the end,
when the truck is empty, only then going back to the warehouse.
And, and re-filling the truck.
So that's an example of an efficient algorithm,
actually that's not the algorithm,
that's an example of how we think about making an algorithm efficient.
We look at what the computer is doing, we look at how often, for example,
it's going back and forth to memory to retrieve data and
we ask, is there a way to do that in fewer steps.
Is there a way to do that in less time and using less memory,
and that's what we talk, that's what we mainly talk about, efficient algorithms.
Steven Salzberg, PhDProfessor
Jeff Leek, PhDAssociate Professor, Biostatistics
