Video 1-1: §1.1 Algorithm analysis

0:00 Introduction

0:03 So, welcome back to COMPSCI 256 and now to unit one, the first unit that starts the the real journey into our discovery of of eternal truths of algorithms. I I started last week by saying we want to get to these external truths eternal truths. Um and they need mathematical statements. If you're only looking at a specific machine, how it's done on a specific hardware, you don't get to this eternal part. Uh and the flip side of that is we need some mathematical models of what's going on. We need a model for the machine. We need a model for programs and we need a model for data that the algorithms or programs work with. And that's what we'll look at today. Uh and uh some of the the proof track techniques from last week will will pop up once um at some point later in the in the class. Uh today we'll mostly talk about definitions or for this for this unit.

1:05 Goals

1:06 So, what's the goal of of uh of this unit? Um First of all, there's an alternative to all of what I'm saying. You could often just take different um algorithms, implement them, and see which one works better. If you can do that, if you actually in the position of doing that in in an application, that might be preferable because it's the definitive answer for your specific application. But there's uh many caveats to this and often you're not able to do it that way. And definitely on a on a broader scale as an academic as as uh computer science graduates or want-to-be computer science graduates, um you should uh have an appreciation for the difference between running time and uh the analysis of an algorithm and then these uh asymptotic complexities. I think this is just the language that uh computer scientists use and so you have to be a little bit familiar with that. Uh then in terms of models, we have models for data, the typical ones. You might have seen those before. Maybe just not under this uh term model of data.

2:12 Look at best, worst, and average case and sometimes more. In terms of machine models, uh we'll look at the RAM model, which some of you may have seen. But I'm not sure if any of you has seen the word RAM model in all its uh in all its details. I like to give this in some detail because I remember when I was taught about algorithms uh in the simpler model, there was always a gap and I'll come back to that gap. The word RAM model nicely answers that gap. On the other hand, it looks a little more scary than it needs to be for most of what we're doing, but I want to give this as a background.

2:51 Uh then um we'll look at asymptotic notation, big O classes. Uh we'll see why we want to use those and I want you to be able to analyze some simple algorithms, uh but nothing too crazy. So, that's what we'll do in the next hour or so. Maybe uh subject to a little break and we started late, so let's see how much uh how far we get.

3:18 Intuition

3:25 Before we start talking about um the more intricate models, I want to give some some intuition starting from zero in a sense about what algorithms are themselves. Uh remember we need we need a model for programs, but this is even on a higher level. For me, an an algorithm is a sequence of instructions. Uh that's as simple as that. It's like a cooking recipe, hence this picture. Uh algorithm as a term has has attained a different meaning in in uh in media and etc. as some combination of a machine learning system plus implications on society and is often used in a somewhat negative uh connotation. Uh but the the meaning of algorithms in in computer science is usually restricted to just this. It's some sequence of instructions that solves a problem. Uh so, we want to be a little more precise, but what I try to stress here is uh Facebook, for example, has implemented some system to decide what you see on your feed and people call this an algorithm, but it's much more than just a simple set of instructions. There's a lot more going in. There's design decisions and there's lots of machine learning and data bias etc.

4:42 Um so, I'll I'll try to uh be clear that when we talk about an algorithm, it's always this old school algorithm in a sense. Uh a sequence of instructions um with these well-defined properties. So, first of all, we want it to be mechanically executable. It should be as precise as needed to be executed on a computer. And that can be uh painstakingly detailed sometimes. In particular, we can't appeal to common sense of humans. That doesn't work. We have to avoid all such. We have to spell specify everything in detail.

5:23 Uh a minor thing that you wouldn't normally uh come across, but in in some applications, it's important to make the distinction. An algorithm has to be finite in length. You can't describe how to write an algorithm where you have to write down infinitely many lines of code. Uh it wouldn't really work well with executing that, but yeah. And um a last thing is this is a little more subtle. We want to solve not just a single instance, but we want to solve a generic problem or a generic task. So, not just uh the addition of two concrete numbers, but the addition of two numbers in general or at least the addition of two numbers from a certain range in general. That distinction is sometimes not so clear, not so formal. Uh but it's usually in in the examples we look at, it's clear that there's a well-defined algorithmic problem and the algorithm is trying to solve that.

6:23 A typical example of an algorithm could be bubble sort that probably all of you have seen. Uh the underlying problem is sorting a list of uh a list of data, say a list of numbers. Uh list usually means it's given in an array, but not necessarily so.

6:42 Uh and uh an algorithm for me is is again a bit a bit vague. Uh it's the underlying idea how to solve this problem, not necessarily a concrete um set of uh a concrete set of lines of code that does this. So, there might be a single algorithm like bubble sort and you can write different implementations of that same algorithm. For example, in different languages or even the same language, different implementations that are slightly more tricky and cunning in in avoiding certain inefficiencies. So, there's the kind of more abstract idea, that's the algorithm for me. Uh I think that this point is a bit vague, but again, in many examples, it's kind of clear. Bubble sort, you could say the idea is that you always compare two adjacent ones and if they're out of order, you've you've you swap them. That's kind of the essence of bubble sort and you can implement that in in many ways in a program.

7:42 Data structure

7:46 A second term somewhat related is a data structure. Um that's essentially some algorithms plus uh a specific rule how to store certain data that's associated with this.

8:00 Uh and again, yeah, this is in in examples mostly is is more clear what this means. And we'll talk it about this at length in unit two. So, maybe I'll I'll leave it with that. Uh in the the main difference between an algorithm and a data structure is that an algorithm runs once. It's in a sense a box uh where you put maybe that's something to put on on this. An algorithm is a box. You feed some input into it and then it computes and it eventually it spits out some output. That's the traditional model that we'll work with. Um And a data structure by contrast is something that uh sits there over time and you can repeatedly query it or change it. Uh you have different operations that you can apply to it. And it has a state that's preserved between those.

9:02 Most of you will have seen one example at least, binary search trees. There's many others. Uh we'll come to that in unit two in more detail. Are those basic um those basic terms clear? Uh as always, I'll I'll try to look at uh the Slido questions if you want to ask a question or just scream. Uh either works.

9:29 What is algorithm analysis

9:33 Okay, with these with these two preparations, let's look at what the analysis of algorithms uh is like. And what's what's it for? Uh why do we want to analyze algorithms? For many algorithmic problems, uh there are different options how you can solve it. There's different algorithms and then many different implementations of algorithms or in other cases different data structures. Uh and you would like to choose a suitable one for your task for your application. And uh for us suitable or good usually means that it's fast uh and maybe also uses not excessive amounts of space. But we'll focus mostly on on the running time. That's the traditional objective in computer science. And in in many in many cases this is the the core uh hurdle to overcome. Um and algorithm analysis is a way to compare different algorithms. So it can tell you if you have two different algorithms, which one might be more efficient, which one might be faster or in terms of space, which one is more space efficient.

10:47 Uh and also secondary goal is it can make actual predictions, quantitative predictions about how long something will take. And that's important because it means uh you can then decide if a certain approach that requires you to use a certain algorithm on a certain uh input of a certain size, whether that's at all feasible. If the prediction is it will take 5 years of computing time, it's probably not the way to go. Whereas if it says it takes 5 seconds and you would rather have it run in 1 second, maybe that's something you can squeeze by uh working a bit harder on optimizing it. But if the discrepancy is so big, then you know up front this won't work. So that's the two goals. We want to have uh a clean way of comparing algorithms and we want to have a way of predicting how well would things work uh in a certain scenario.

11:40 Limitations of experiments

11:43 Now you could as I said before, take the different options you have, implement them and test it. And there's nothing wrong with that. Uh the only the only thing to keep in mind is there are some limitations to that approach. You usually test it on some machine and it's not clear what happens on another machine. Uh things can sometimes vary a lot. Uh then you will have to decide on some inputs that you evaluate the methods on. Uh if you're lucky, these are representative for the application uh you want to use them in. If not, then you will get results that don't really tell you much. Uh and the last point is maybe a little more uh important in this context. You'll test a specific implementation of the idea, not the idea itself, because you have to implement it in some concrete way to even just run it. And sometimes there's just a little trick needed to make an implementation good and then you would get vastly different results.

12:43 Uh and the more abstract analysis uh can sometimes sidestep this issue. Uh what's definitely clear from an academic perspective, this is this is not what we want in terms of universal truths. Uh this is the opposite of that. It's very specific to a certain certain scenario and it's not clear if it survives a certain generation of computers or uh a certain scenario of inputs and all all these things listed here. So what we would like to focus on instead is uh have some some more abstraction that takes away some of the specifics while keeping those that are relevant hopefully hopefully.

13:27 Uh and by by taking it into the realm of mathematics, we can prove statements. They will be a bit more abstract, but they will be proven and will never be invalidated unlike um the results from experiments. And they will give us concrete hypothesis that we can test uh because every model makes some assumptions and we can then validate those, but it will be more clear what we have to validate.

13:53 And as I said many times before, the this hinges on having concrete models of machines, programs and data. Let's start with the easiest one. I think that's the data models. You can uh take different different approaches to this. Um the most versatile or most widely used ones are these. You can be very pessimistic. You always assume the universe conspires against you and gives you the worst possible input for this algorithm. Uh that might may seem a little uh out of this world. On the other hand, if you can prove a strong worst-case guarantee for your algorithm, you're fine because nothing worse can ever happen. So uh if that's good enough, you're you're definitely fine. Uh the best case is the opposite. You're you're very optimistic and assume you always get the the easiest input. Uh that's not usually useful for predicting running time, but it's good for looking at the discrepancy between those two. If there's a huge gap between those two, maybe the third one is interesting to look at.

14:02 Data models

15:01 Uh and that's if you average over all possible inputs or some slightly more sophisticated models if you if you have a a good idea for uh what inputs are more likely to occur in your situation. Uh we'll usually assume uh in the context of sorting, for example, we assume that every ordering of the input is equally likely and we're we'll work from there.

15:29 Why do people like these models? Uh they're not necessarily the most realistic for a concrete application. Uh but the the big benefit of these models is that they reduce all inputs of a certain size to one to one number, to one parameter. So we we usually look at we group inputs by size uh and sometimes it's not so clear what size means, but in in many examples it's quite clear. If you're sorting, it's the number of elements. If it's a graph, it might be the number of vertices and edges. Uh some things like this. If it's a matrix, maybe it's the the number of entries in the matrix. Um sometimes the number of non-zero entries. So this depends on the algorithmic problem, but it's usually relatively intuitive.

16:16 So you take uh you fix the size of the input and then you stipulate these models. So you take the worst of all inputs for a given size or the average of all inputs for a given size.

16:32 And the the goal of this is to get the performance of an algorithm as a function of the input size. That's that's the goal. So we get uh a single parameter that uh we assume drives uh the complexity of an input. Like the Okay, the underlying assumption behind this is if your input gets bigger, if you have more data, it takes more time to to compute whatever function you're computing. And that's usually reasonable because for almost all problems you have to read at least the data before you can do anything useful with it. And so uh there's inevitably some dependence on the size of the data. Okay?