Video 2-1: Algorithm Analysis

0:02 In the second unit, we'll look at some some mathematical models for the machines and the inference and the algorithms so that we can live up to this promise of eternal truths of mathematically proven statements. Um I'll try to do this a bit quicker because uh some of you have seen this before and it's it's uh not particularly deep. My point for this lecture for this unit again is um we want to have some some formal understanding of what is going on in case we need to check the details. Most of the time, we will not be required to go to all the level of detail that I'm going to show you in the models, but I want you to have the right buzzwords to check it up um to check up on it if if you ever wonder about some some detail where this makes a difference. The first of the less uh satisfying questions is what is an algorithm?

0:59 And I don't have a definitive answer that is mathematically rigorous because it is a bit of um an informal term. Uh I Effectively, an algorithm for us is a sequence of instruction, a recipe for computation, hence this picture. Um to be a bit more precise, it must be mechanically executable. So, I One option is to give a program in a in a formal programming language. At least there should be no common sense needed, whatever that means, right? Uh the also the description of this algorithm must be finite. It You cannot simply say, "Ah, now do any of these cases." And uh there might be infinitely many cases that you have to solve. The last bit is the one that is a bit harder to grasp in in formal terms. I would want an algorithm to be something that is a bit more general than a specific program. It shouldn't just solve a specific task like adding up two concrete numbers, but it should be the general problem of adding up two numbers, no matter how large.

2:01 And so this is a bit informal, but often times when you see concrete examples, you'll know what I mean. A typical example might be bubble sort as a sorting algorithm. There's different ways how to code that up in any specific programming language. But you might for all of the versions that you can write still recognize oh, this is essentially going through the list comparing adjacent elements and when uh say the left is larger than the right, you swap them. And you do this bubble up the largest to the right end. That's the essence of bubble sort, but you can write different programs that essentially have the same idea. So the abstract idea is what I would want to call an algorithm and the rest would be a concrete implementation or a program. Uh we here also think of algorithms as always in this function abstraction, there's some input that goes into this this program and then there's some output produced.

3:00 That's um that's encompassing for all that we we look at in terms of algorithms. Uh the second um concept that is related is a data structure. Uh we'll touch a bit on this as well, so um let me also define a bit what I mean by that. Uh it's two things. It's for one a way to encode data in a specific way, so ultimately how do I represent the data that this uh data structure abstractly represents in computer zeros and ones? And second for um the operations that the data structure supports, what are the algorithms that you execute for each of them? And usually these algorithms may either just read the encoded data or they may also change it. Then we call these queries or updates. But all of them are operations that have to be specified with some concrete algorithm. An example that many of you will have seen is a binary search tree. There's a specific way of say having a node with say a left and a right child pointer and a value stored.

4:04 And then there's a algorithms for searching in a binary search tree or for inserting new elements and so on and so forth. That's the two main protagonists and they're a bit of a bit informal because it's a bit hard to say what is a a class of problems solved. But I think for the examples we'll see is always clear what is meant. That's the hope. Otherwise you ask.

4:38 Now with that said, let's come to this second formal statement that we want to make about algorithms. From now on I will assume that we're talking already about an algorithm that is correct. So we've done our uh loop invariant proof that the output it produces is what we wanted. Even when the algorithm is proven correct, we still may want some algorithms more than others and that's about uh their performance. For that we need to analyze algorithms. A good algorithm is usually one that is faster and maybe uses less space. Specifically for data structures, that's also an important part. In principle, you could have other uh goals that you optimize for, but we'll focus on these resource goals. Um I would like you to think of the analysis of algorithms as um a way for two the same same technique that tries to achieve two different things. First of all, it's a way to comp- com- compare different options that you have for implementing some uh for solving some abstract problem and maybe one is better than the other.

5:48 How do you find out? By analyzing and comparing the running times. Um seemingly different is to predict how fast an algorithm might be in practice in a certain application. And the point is that you can often do this up to some maybe factor two or five. You can you can predict how fast something will be by maybe running a tiny experiment and then projecting how how the algorithm's performance will scale. And that allows you very quickly to check if the approach you have in mind is likely to succeed maybe with a little bit of tweaking or is completely unthinkably slow. And this is important to do whenever you design some larger system because you do not want to spend three weeks implementing to then notice that this is completely hopeless. You want to find out before you do all the implementation work. And algorithm analysis can can allow you to do that.

6:50 Of course, the alternative is to just implement the algorithm and run it and then you see whether it's fast enough or not. If it takes three weeks to implement all the parts uh of the system and test it, this may be out of the question already. But there's more subtle problems with this approach as well. Because whenever you do concrete experiments, it's a bit hard to to uh know whether they generalize to other scenarios.

7:15 Like uh there's there's many abstract ideas how you can uh criticize this. Let me give the concrete example where I was involved in in sorting algorithms for standard libraries. You don't know where these will run. So, optimizing for your specific laptop is great, but then if uh the other uh many people that will run this code have slightly different hardware, you don't know what they will get as performance. Whereas if you have some more abstract understanding why the algorithm is faster slow, then likely that is going to translate to other machines in a similar way. And again, on the theme of universal truths, we want something that survives the current hardware and is is a on a slightly higher level of abstraction, but has a better half-time. What that means is we need models of the machine. What does it mean at a higher level of abstraction? What do I mean by that? And we need models for the data and algorithms.

8:19 The easiest are the data models. Uh usually in computer science, we're uh making a very simple assumption here. By and large, the most prominent is to focus on worst-case performance. So, uh if you have a good guarantee that no matter how how bad the input will be, your algorithm has a certain performance or or better, then that is universally true. And this sounds I think this is more relevant than ever because it may be that someone conspires against you in the literal sense and tries to make your algorithm get slow by uh feeding it malicious input. More relevant than ever in uh rampant cybersecurity incidents. So, maybe worst-case performance is is a better defense there. Uh if you are sure that your system is not used in adversarial scenarios, maybe the average case is more representative. Uh but also a bit harder to analyze. Uh usually all of these, um we will interpret as over all inputs of a fixed size.

9:26 So, as a concrete example, say we look at sorting algorithms, then it could be the length of the array or the number of elements that we sort is our size n. And then worst case means among all those of a fixed size n. So even if you pick these simple data models, worst case performance, it is still a function of this input size. And this is people do this almost universally because it's clear that if you have a larger input or a larger data set, anything you do will take longer. The question is as you make your data set bigger and bigger, how much worse does your performance get? I will get to that in in the next section in more detail.