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. So to talk about the analysis of algorithms, we'll begin with some history and some motivation. 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. Another thing that happens when we analyze algorithms is that we have to closely study them. And that helps us better understand and improve the performance of particular algorithms. Now the really, the reason most people analyze algorithms is because of the intellectual challenge. Analysis of algorithms is even more interesting and fun than programming for many people. And we hope to be able to convey that sense to you during this course. 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? 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. 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. 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. 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. So here's an example. Two very familiar sorting algorithms which I'm sure everybody's familiar with in this course. We have quicksort, the worst-case number of compares is quadratic. 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. 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.
