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.

Â