0:03

Welcome to analytic combinatorics part one.

Â Analytic combinatorics is the quantitative study of the property of large discrete

Â structures.

Â One of the main applications of analytic combinatorics the analysis algorithms.

Â So this first lecture in the book on which this course is based is titled

Â The Analysis of Algorithms.

Â For much more information on the context of analysis of algorithms and

Â analytic combinatorics, take a look at the introductory lecture.

Â From the Analysis of Algorithms to Analytic Combinatorics,

Â a Journey with Philippe Flajolet.

Â Which tells the history of how my friend and

Â colleague Philippe Flajolet and I developed this material.

Â 0:54

First question that we want to ask is why analyze an algorithm at all?

Â And the answers to this question are fairly straightforward.

Â One thing that we want to do is classify, not just algorithms but

Â also problems according to their level of difficulty.

Â Another thing that's very important is we want to be able to predict performance and

Â compare algorithms.

Â We want to know how much time our algorithms are going to take.

Â And we want to know which algorithm is better than which other one for

Â our particular tasks.

Â 1:50

Now, the field goes way back.

Â In fact, the first computational device is attributed to Babbage.

Â It was a mechanical device.

Â And this quote shows that even Babbage understood that we're going to need to

Â understand something about our methods of computation.

Â As soon as an analytic engine exists,

Â it will necessarily guide the future course of the science.

Â Well he was right about that.

Â 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?

Â 2:26

That was very important to Babbage because this thing was mechanical.

Â In fact, if you look closely, there's a crank.

Â And the question Babbage was interested in was,

Â how many times are we going to have to turn the crank.

Â Obviously, a very important question.

Â And really not so different than the kinds of questions that we ask today.

Â When we ask whether we can get a task done before our cell phone runs out of

Â battery power or whatever other scarce resource we care about.

Â 2:58

Even Turing, which many people think of as a theoretician, was

Â very practical when it came to actually getting things done with computers.

Â He says, it is convenient to have a measure of the amount of work involved in

Â a computing process, even if it has to be a very crude one.

Â We may count up the number of times that various elementary operations

Â are applied in the whole process.

Â Again this is 1940s, before computers were coming into widespread use.

Â But Turing saw that we're going to have to know how our algorithms are performing.

Â And we're going to be able to have to be able to count the resources they consume.

Â But the field really came into existence in the 1960s.

Â When Don Knuth published the first of his series of seven volumes,

Â four of which have now been published.

Â And he's the one who really put the study of the analysis of algorithms on

Â a scientific basis.

Â Before Knuth, people thought that it was going to be just too complicated to

Â really figure out what kind of resources programs consumed.

Â And Knuth simply laid out pretty straightforward steps for

Â what we need to do to analyze an algorithm.

Â First, get it running, implement it and understand its

Â performance by running experiments, develop a good implementation.

Â 4:19

Second, extract the process a little bit by defining some

Â unknown quantities that represent the basic operations.

Â Then determine the cost of each basic operation.

Â And then develop some kind of model for the input.

Â And with that model analyze the frequency of execution of the unknown quantities.

Â Each one of these tests have a little bit of complication to them, but

Â still they're relatively straightforward.

Â And with all that information, then we can calculate, say the total running time.

Â Which is, for every quantity,

Â we just add up its frequency of execution times its cost.

Â 5:01

A very straightforward process and pretty close

Â to the one that I'll be talking about in the next segment of this lecture.

Â Now this has great benefits.

Â First, I as I mentioned it's the scientific foundation for

Â analysis of algorithms.

Â It gives us a process whereby we can develop mathematical models,

Â develop hypotheses about performance and comparing algorithms.

Â And then test those hypotheses scientifically.

Â You certainly can predict performance and

Â compare algorithms if you analyze algorithms like Knuth.

Â Now it does have some drawbacks.

Â The first drawback is the input model might be unrealistic.

Â And that's certainly still a problem that plagues people today.

Â And the second drawback is that there might be too much detail in this analysis.

Â And that is a bigger problem that actually we try to address

Â with analytic combinatorics.

Â So that'll be a theme that we'll come back to often in this course,

Â is how do we suppress detail while still getting accurate results.

Â Now in the 1970s, and even up to the present day, the study of algorithms

Â has revolved around books by Aho Hopcroft and Ullman.

Â Cormen, Leiserson, Rivest, and Stein and others, they try to address

Â Knuth drawbacks by first of all, just analyzing the worst-case cost.

Â And what that does is it takes the model pretty much out of the picture.

Â What we want is a guarantee on the worst-case running time of an algorithm.

Â And the second thing is we just use big O-notation and

Â just try to get an upper bound on the worst-case cost.

Â And that's a way to get a lot of the detail out of the analysis.

Â So, we're looking at a guaranteed upper bound on the cost of an algorithm.

Â And that addresses both of those drawbacks of Knuth.

Â And then the idea is to classify algorithms according to this cost.

Â And that was extremely successful approach that unleashed an age of algorithm design.

Â Where people were able to try out all kinds of new ideas.

Â And drive down these guaranteed worst case costs with the ultimate goal

Â of developing optimal algorithms.

Â Where the worst case cost is equal to the best possible.

Â But this approach also has a drawback.

Â And the serious drawback of this approach is that you cannot use it,

Â generally, to predict performance or compare algorithms.

Â That's an elementary fact that's often overlooked, but in this course,

Â it's important to lay out right at the outset.

Â 8:03

You can have the algorithm, and we'll look at this algorithm in more

Â detail later to make that obvious for you, those of you that haven't seen it.

Â So according to the classification from the theory of algorithms,

Â it would be classified as an O(N squared), or a quadratic algorithm.

Â Merge sort, we can prove the worst case number comparisons analog N.

Â And actually, any algorithm has to use that much, so

Â you can say that merge sort is optimal.

Â And it gets classified as an N log N algorithm.

Â That's where the theory of algorithms would leave those.

Â But it's a problem because quicksort actually is twice

Â as fast as mergesort in practice, and it uses half as much space.

Â So even though the theory of algorithms would classify mergesort as better,

Â in practice quicksort is much better.

Â And there is many many examples like this, hashing versus balanced binary

Â search trees and many, many other examples like this.

Â So how do we know that quicksort is twice as fast as mergesort?

Â Well, we're going to look at that,

Â that's what the analysis of algorithms is all about.

Â Enabling us to make precise, quantitative statements about the performance

Â of algorithms, that we can test in practical implementations.

Â So our bottom line is you cannot use big O upper bounds to predict performance or

Â compare algorithms.

Â 9:29

Now, with that background I just want to take a minute to put analytic

Â combinatorics into context.

Â So this is the summary of the last couple of slides.

Â The drawbacks of Knuth's approach is the model might be unrealistic and

Â there might be too much detail in the analysis.

Â The AHU/CLRS approach, the worst case performance might not be relevant.

Â And can't use big O upper bounds to predict performance or compare algorithms.

Â What analytics combinatorics can provide is number one,

Â [COUGH] by the end of part two you'll see.

Â Calculus for developing models that can help us use more

Â complicated models to help understand algorithm performance.

Â And also, can provide general theorems that allow us to avoid

Â too much detail in the analysis.

Â In this course, in part one,

Â we're going to take a look from the beginning of the underlying mathematics.

Â And try to describe just what analytic combinatorics is.

Â And then look at a lot of classical results in analysis of algorithms in

Â combinatorics to set the stage for part two.

Â Where we get to the real recent research in developments and

Â analytic combinatorics.

Â That's a history and motivation of Analysis of Algorithms.

Â