0:02

Welcome back. Today we're going to do some math and some science. Not a lot, but we

Â need to have a scientific basis for understanding the performance of our

Â algorithms to properly deploy them in practise. So today we're going to talk,

Â about how to, observe performance characteristics of algorithms. We're going

Â to look at how to make mathematical models and how to classify algorithms according

Â to the order of growth of their running time. We'll talk a bit about the theory of

Â algorithms and also how to analyze memory usage. So to put this all in perspective,

Â we're going to think about these issues from the point of view of different types

Â of characters. So the first one is the programmer who needs to solve a problem

Â and get it working and get it deployed. Second one is the client who wants to use

Â the whatever program did to get the job done. Third one is the theoretician,

Â that's somebody who really wants to understand what's going on. And, and the

Â last one is kind of a team, this basic blocking and tackling sometimes necessary

Â to get, you know, all these things done. So, there's a little bit of each one of

Â these in today's lecture. And actually when you're a student you have to think

Â that you might be playing any or all of these roles some day. So, it's pretty

Â important to understand the different points of view. So, the key that we'll

Â focus on is running time. And actually the idea of understanding the running time of

Â a computation goes way back even to Babbage and probably before. And here's a

Â quote from Babbage, "As soon as an analytical engine exists, it will

Â necessarily guide the future course of the science. Whenever any result is sought by

Â its aid, the question will arise by what course of calculation can these results be

Â arrived at by the machine in the shortest time". If you look at Babbage's machine

Â called the analytic engine, it's got a crank on it. And literally the concern

Â that Babbage had in knowing how long a computation would take is, how m any times

Â do we have to turn the crank. It's, it's not that different, in today's world. The

Â crank may be something electronic that's happening a billion times a second. But

Â still, we're looking for, how many times does some discreet operation have to be

Â performed in order to get a computation done. So, there are lot of reasons to

Â analyse algorithms. In the context of this course we are mainly interested in

Â performance prediction. And we also want to compare the performance of different

Â algorithms for the same task, and to be able to provide some guarantees on how

Â well they perform. Along with this, is understanding some theoretical basis for

Â how algorithms perform. But primarily, the practical reason that we want to be

Â analyzing algorithms and understanding them is to avoid performance bugs. We want

Â to have some confidence that our algorithms going to complete the job in

Â the amount of time, that, that we think it will. And it's very, very frequent to see,

Â in today's computational infrastructure, a situation where the client gets bad

Â performance, because the programmer did not understand the performance

Â characteristics of the algorithm. And today's lecture is about trying to avoid

Â that. Now, we're going to focus on performance and comparing algorithms in

Â this course. There's later courses in typical computer science curricula that

Â have more information about the theoretical basis of algorithms and I'll

Â mention a little bit about that later on. But our focus is on being able to predict

Â performance and comparing algorithms. Now there's a long list of success stories in

Â designing algorithm with better performance in, in enabling the solution

Â of problems that would otherwise not be solved. And I'll just give a couple of

Â examples. One of the first and most famous is the so called FFT algorithm. That's an

Â algorithm for breaking down the wave form of n samples of a signal into periodic

Â components. And that's at the basis for dvds and jpegs and, and many other appl

Â ications. There's an easy way to do it that takes time proportional to N^2. But

Â the FFT algorithm, takes only N log N steps. And the difference between N log N

Â and N^2 is, is the difference between being able to solve a large problem and

Â not being able to solve it. A lot of the digital technology, digital media

Â technology that we have today is enabled by that fast algorithm. Another example

Â was actually developed by Andrew Appel, who's now the chair of computer science

Â here at Princeton. And it was developed when he was an undergraduate for his

Â senior thesis. It's a fast algorithm for the N body simulation problem. The easy

Â algorithm takes time proportional to N^2, but Appel's algorithm was an N log N

Â algorithm that again, meant that scientists can do N body simulation for

Â huge values of N. And that enables new research. S0, o the challenge is that we

Â usually face is, will my program be able to solve a large practical input? And, and

Â actually, the working programmer is actually faced with that all the time.

Â Why, why is my program running so slowly? Why does it run out of memory? And that's

Â faced programmers for a really long time and the insight to address this. Deuter

Â Kanoof, in the 1970s, was that, we really can use the scientific method to

Â understand the performance of algorithms in operation. Maybe we're not unlocking

Â new secrets of the universe but, we can use the, scientific method, and treat the

Â computer, as something to be studied in that way and come to an understanding of

Â how our program are going to perform. And let's take a look at that in more detail.

Â So this just a quick summary of what we mean by the scientific method, which has,

Â been successful for a couple of centuries now. So, what we're going to do is,

Â observe from some feature of the natural world. In this case, it's going to be the

Â running time of our program on a computer. Then we're going to develop hypothesis

Â some model that's consistent with the observations, and we're going to hope

Â that, that hypothesis is good enough that it'll allow us to predict something.

Â Usually predict a running time for larger problem size, or on a different computer.

Â And then we'll verify the predictions by making more observations, and validate

Â until we're comfortable that our model hypothesis and observations all agree.

Â That's a way to get comfort that we understand the performance of our

Â programs. Now, the within the scientific method, there's some basic principles and

Â the, the first is that if you're going to run experiments, you should expect that

Â somebody else should be able to run experiments and get the same result. And

Â also the hypotheses have to have a specific property that the experiment can

Â show the hypothesis to be wrong. So, it has to be carefully crafted, and we'll be

Â sure to try to do that. So, and again the future of the natural world that we're

Â studying is some particular computer that exists in the natural world. It changes

Â the algorithm from an abstraction to a, some, some kind of actual physical thing

Â happening like electrons racing around inside the computer.

Â