cs313 ยป

In this course, we're going to do a considerable amount of algorithm analysis, which is why we're going to do an overview of the techniques and notations that we're going to use. If you've already had an algorithm course before and it terms like Big O-notation or RAM or a worst-case running time are already meaningful to you, then you might try and go directly for the quizzes for the respective sections. Let's try it out with a little quiz. What I want you think about is the various factors that we need to take into account when we are analyzing an algorithm or more precisely, when we are analyzing the running time of an algorithm because that would depend on the number of factors. What I would like you to think about is what factors can determine the running time of an algorithm. So here are six different possibilities. First the size of the input, secondly the content or structure of the input, third the type of computer that we are using for the algorithm, fourth the amount of memory the computer has, five how the algorithm is implemented, and six the programming language that we're using to implement the algorithm. I want you think of each of those six aspects and then make a check mark where you think that this aspect can influence the running time of an algorithm.

There's three simplifications that we'll introduce to make analyzing algorithms easier for us. The first one is we will talk about a way that we can analyze algorithms without actually having to implement them, which we already that a lot of times. The second simplification is going to be that we're not going to consider all possible inputs that an algorithm can be run on, but we're going to only consider the worst possible inputs and I'll say more about what that means too. And finally, I'll introduce a notation to you called Big O-notation that will allow us to ignore details that for now we'll call unnecessary, so that we can really focus on the parts that are important for an algorithm and ignore those that we're not interested in. What do these simplifications actually look like or how are we going to go about those simplifications. First of all, to analyze an algorithm without implementing, we're going to consider a special kind of computer, which is not really a computer but a model that comes pretty close and that model is called the RAM. Looking at the worst possible inputs is a concept called worst-case running time, and finally to be able to ignore all unnecessary details, we'll use a type of notation called Big O-notation or Landau notation. So let's start out with our theoretical computer called the RAM.

The answer here is that all of these six factors can influence the running time of an algorithm. So the size of the input, I think that's a rather obvious one so in the example of Alice-- if she is running her algorithm on a very small network that takes much shorter time than if she is running it on the huge Python communication center network for example. The structure of the input can also influence the running time of an algorithm. So for example if the network was structured in a way that we find that it can be covered with one or two monitoring devices, then the algorithm could worked in a way that we could immediately stop and not need to look at more complex assignments. Finally, the type of computer that we're using that is also very obvious one. If you're using a computer that is much faster so say we're using a huge workstation instead of a super laptop, then the algorithm would run much faster. The amount of memory the computer has that can also be a very important factor, although it might not be obvious at first sight while the memory has to do with running time. Let's say the memory of your computer is not enough to keep all the data that the algorithm is using and it has to use the hard disk for example to do some of the work or the memory is not enough and the algorithm has to recalculate certain parts of the solution. Memory is also an important factor for running time. How the algorithm is implemented that is of course very important. So are you using an implementation that is very efficient or do you have unnecessary code or any data structures that are inefficient that can make a huge difference in the practice when we run an algorithm. And finally the programming language use that is of course a debate that many people like to have that it certainly a factor. So there are some programming languages that will make an algorithm run a lot faster than other programming languages. And so you need to think about if efficiency matters, they usually also use a programming language that is suited for that. That's quite a lot of factors to look at and actually, I think there are lots of other factors that would also determine the running time of an algorithm. So that's why when we talked about analyzing algorithms, we'll have to work with the number of simplifications to focus on what's really important and not have to take account of all these factors and all the countless others that you might think of.

The goal of working with a model computer instead of a real computer is that we want to have a machine, which is as easy as possible but still let us capture the main aspects of a real computer. And the reason why you want to have a simple computer is that a real computer contains lots of parts that are not really interesting when we want to analyze an algorithm and also you might have different computers that run at different speeds but actually that doesn't really say something about your algorithm. In the next year, when the faster computer model comes along, you can already run your algorithm a bit faster but that doesn't really say that your algorithm has become better. So our goal here is to strip down a computer that you used to to a model that is as simple as possible but still has basically the same capabilities as a real computer. So we will do this as a quiz and what I want you to think about is what are the essential components for having a minimal computer model. And what I mean by essential is that the computer must still be able to solve problems to perform any computation that this machine here could but also not anymore. So what I would like you do is to check off each of those boxes if you think that this component of a computer is essential to keep in a computer model. So do you need a memory to store your results in? Do you need a graphics card? Some sort of input and output? Do you need a mouse? Do you need a monitor? Some sort of file system? An operating system? Programming capabilities? Or a CD-ROM? And keep in mind that we are looking for a model that is as simple as possible.

Now, of course, the answers to these are a little bit subjective depending on what you want to model, but I think that there are three components that are absolutely essential to keep. The first one is you need a memory for the computer because, otherwise, it will not really be able to perform any computations. The second one is you need some sort of input and some sort of output. It doesn't really have to be a graphical output or be displayed on the monitor, but you need to be able to tell the computer what the input is that it's suppose to work on and you need to have some way of reading the output once the computer is done. And you'll also need some sort of flexibility in the processing that the computer is doing, so we expect it to have certain programming capabilities. All the other components I think are not essential, so you do not necessarily need a graphic's card as long as you have a certain type of output. You certainly don't need a mouse to input anything. You don't need a monitor. You don't need a file system or operating system because if you really want that you can emulate that using the programming capabilities and you certainly also do not need a CD-ROM as long as you have some way of providing the input.

As we saw in the quiz, there are three things that our basic machine model needs to have. One is the memory, the second one is some sort of input/output capabilities, and finally, we need to have certain programming capabilities. There's a lot of different models that have these capabilities, but in this course, we're going to use a model called the RAM, and RAM stands for Random Access Machine. So, there are many different ways of defining a Random Access Machine, and we'll use a model similar to the one defined by Steven Skiena and his book, The Algorithm Design Manual. The first thing that the RAM has is the memory and that memory can of course be used for input, for output, and for holding the program that the RAM is running on, but as simplification, we're going to split the memory into three parts. We're just going to use this memory here for intermediate results and output, and we're going to have a separate memory for the input and a separate memory to hold the program. And, these two memories here on the left side are read only meaning that the RAM cannot modify the input, it can only read the input, and the RAM can also not modify the program. It could only read the program, and usually, when we will talk about the memory requirements of an algorithm, what we will be talking about is how much of this memory here the RAM is using. Generally, there is no limit of how much of this memory here we have so we always have as much as we want, but the memory is divided into single cells, and each of these cells has a limited capacity so each of these cells cannot have arbitrarily large values, but there are as many cells as the algorithm needs. Now, if we're running a program on the RAM, what we're mainly interested in is the time that this program is going to run for a given input, and there are basically three rules for how long the RAM requires to execute a program. Simple operations such as adding two numbers, multiplying them, or executing an if or for. Those all take one time step. If you have a loop in your program such as a four-loop, this will count not as a simple operation but count as often as it runs. So, if you have a loop that executes a simple operation 100 times, that will count as 100 time steps, and finally, you' ll also get something for free accessing memory. So, reading a part of the input or writing something into a memory cell here, that is free. That means that actually takes zero time steps. And these three rules give us a simple way of determining the running time of an algorithm or program or also of comparing the running time of two programs because all we need to do is count the number of time steps that we expect the RAM to execute for a given input. Let's practice this for a little bit.

We're going to practice this analysis as a number of quizzes. For the first quiz, we're going to start off with two simple lines of code and using these three rules up here, I want you to tell me the number of time steps that the RAM will need to execute these 2-lines of code.

The answer is that the RAM is just going to take a single time step, one time step, to execute these 2-lines of code because for this line up here--this is just a memory access and we get memory access for free. That's 0 steps and down here, that is a simple operation, which takes one time step. So a total of one time steps.

So now let's try a little more challenging example. It's not really challenging, but it's a bit more difficult than the first one. So this is a 3-line code and then I want you to tell me the number of time steps that this code will need on the run. For this, I should mention that we're going to count this operation here--the while and the comparison of s if it's greater than 0 as a simple operation.

While we're recording these, actually we thought it wasn't a very challenging example and then we got it wrong about 4 times, but the correct answer here is that these three lines take 11 time steps to execute. The first line is free as in the first quiz and the second line is actually why we had to count a few times until we all got it right. This line here is executed 6 times--once for s=5 and then s is decreased by 1 each time this line down here is executed. So, s starts out as 5, 4, 3, 2, 1 and 0, which means this line here is executed 6 times whereas this line down here is only executed 5 times because once s is equal to 0 this line here is not executed anymore, which makes for a total of 11 time steps.

As you can see, exactly counting the number of time steps even though we have a very simple model of just three rules and a code that doesn't even have a variable input is already quite tedious. We are going to introduce a number of additional simplifications that will give us a little more levy here so that we do not have to go through this exact counting process but still learns something about the algorithm. In general, the capabilities of the RAM closely matched what you would expect from your own computer but of course it is a simplification but nevertheless it is a rather solid model. It's difficult to design an algorithm that when you analyze it it will give you a very different idea about its performance that it would get on the RAM. Nevertheless, I think it's important to think about the differences between a RAM model and a normal computer, and we will do this as a quiz. Here are four main simplifications that I think the RAM is making. Here are four properties of the RAM. The first one is simple operations take only one time step. The second one is we assume that we have as much memory as we need. The third one is that memory access is considered to be free in terms of time. And the fourth one is that a unit of memory cannot hold an arbitrarily large number. And of course this is going to be subjective, but I would like you to tell me which of these four properties you think is realistic in the sense that it comes pretty close to a real computer and which of these you would consider unrealistic meaning of you were to run your algorithm on a real machine then there would be considerable differences and again the answers to these are subjective. If you get stuck or if you disagree with me just take next and see where our opinions differ.

In my opinion, I would say that the assumption that simple operation take only one-time step is rather unrealistic because in real computer you have lots of differences between simple operations and also loops such as ifs and whys it can take very different amounts of time depending on where and when they are executed. The second one we have as much memory as we need that might be debatable for some cases given that memory is actually not that expensive anymore, but there's still lots of problems where you can run out of memory and so that is still a real issue. I would also say this is rather unrealistic. Memory access being free in terms of times that is very unrealistic because in the real computer, you really have to watch out what kind of memory you're using. For example, if you're using register and a processor that is memory that almost come for free that's very fast, but when you have to read and write to your hard disk that is going to take very long. Memory access being free is really unrealistic. Finally, a unit of memory not being able to hold an arbitrarily large number that is very realistic because your computer depending on how many bits each unit of memory can hold. If its 32 or 64 and there is always the limit of how much you can store in a single unit of memory and then you have to go to the next one. Given that there's lots of unrealistic aspects for the RAM, why are we using it in this course? Well, there's basically two reasons. The first reason is that its a very simple model to use. So, if we have to consider all of those aspect as well, our analysis would get even more complicated than in the simple example. And the second thing is that when we are running or analyzing algorithms on the RAM, the general behavior of the algorithm, how it behaves on various inputs, and how the running time changes with various types of inputs still is rather realistic even though we're not really taking into account these aspects. When you have to implement an algorithm, which is something that we're not doing in this course then of course, you have to take care of these things and see for example if the types of operation you're using is making your algorithm run faster or slower or if you need to take care of memory.

As we've already seen for the algorithm that Alice was using, the running time of an algorithm can often very dramatically vary with the size of the input that the algorithm has given, but the running time can also change with the content or the structure of the input. And here's the simple example to show you this. So the algorithm takes as input a string s(0) to s(n-1), which means it's a string of length n, so n characters in the string and here's the algorithm. So the algorithm does something very simple given that string. It counts the number of times that the character a appears in that string. So it sets the counter to zero and then goes through all the characters in the string one by one. And if that character is equal to a then it will increase the counter. So as in the previous examples, we're going to take this line here as a simple operation meaning to take one time step each time it's executed. And we're also going to consider this one here as simple operation meaning also this whole line here is going to take one time step each time it's executed. Now, what I would like you to do as our next quiz is tell me the number of time steps this algorithm takes for a given string s. And to give you that answer, there are two things you need to know or two variables you have to take into account. One is n, the length of the string, and the other one as you're going to find out is a, and with a, we're just going to denote the number of times that the character a actually appears in that string. So your answer is going to be some formula that includes n and includes a, and I would like you to give me the running time by entering the coefficients in the following formula so it's going to be some number multiply by n plus some number multiply by a plus a constant. Please enter those two numbers. So not the result of the formula. It's the running time of this algorithm when it encounters a string of length n where the letter a occurs exactly a times.

There's actually two correct answers here depending on how you think about it.
Both answers in common that it's always 2*n+1 a, and depending on how you count this line here,*
it's going to be either a 0 or a 1 and the reason for that is the following--
the first line again takes 0

I would like to do a little quiz with you here and have you tell me if I give this algorithm here the best possible input, what it's running time will be and again I would like you to state that the function of n, a and the constant and the same thing for the pessimistic view. If I give the algorithm the worst possible input that it can receive, what will be its running time. And I should also note that I haven't told you yet what the best and worst possible input for the algorithm will be but I'll have you figure that out.

Let's assume for now that the running time of this algorithm is 2n+a+1, so even for this simple algorithm, the running time depends on both the size of the inputs to the length of the string and the structure of the input, which in this case is the number of times the letter a occurs. And this is of course very problematic because on the one hand when we get more complicated algorithms, the formula here will get very, very complicated. And the second thing is that most of the time we don't even know what kinds of strings the algorithm will encounter, so we cannot get rid of this variable without making any assumptions. We want to avoid these complications and there's actually three different ways you could do that. The first one would be to have a very optimistic view and state the running time for the best possible input that this algorithm could receive. Basically saying this is the minimum running time of the algorithm and state that as its overall running time. You could, of course, also take the opposite view and say--we're going to state the running time as a worst-case view, so we're going to be very pessimistic almost like there was an adversary who is giving us the worst possible inputs and then state that as the running time. And then finally we can take an in between view and say--well, the usual input for the algorithm is not going to be your best case. It's also not going to be the worst case, so let's state some kind of average.

What would be the best possible input for the algorithm.
The best possible input for the algorithm would be if we give it a string that does not contain
the letter a at all because this rates at a to 0, so the overall running time will be 2*n+0 a+1,*
which is this constant here.
Now, in the worst case, the string will just consist of a's and this will set a equal to n
because each of the letters in the string will be added, and so if a=n,
then the overall running time is 3

As you just saw on the quiz, there's three kinds of view we can take with regard to running time. We can take a best-case view and assume that all the inputs that we're getting are the ones that make our algorithms run the fastest or we can take the very opposite view and say that the running time of our algorithm is going to be determined by the worst possible input that it can receive or we can define running time as the average time that our algorithm will take over a number of inputs. Which one of the three are we going to choose in this course? Best-case running time as you've seen in the previous quiz is often rather trivial or meaningless. So for example, if we use best-case running time for our algorithm that counts the number of As, it would only be valid for strings that contain no A at all so we're not going to take this. For the average-case view, actually that could be a very interesting view and practice because when we run the algorithm a couple of times we might not care about how much that algorithm runs on a single run but over many inputs. But as you've just seen in the quiz, it's actually quite hard to define what an average input looks like. And also when we do the analysis of an algorithm sometimes we might not even know what kinds of input the algorithm receives. Average-case analysis is very interesting sometimes. But here, it's actually not that suitable. Now, worst-case analysis. Well we always assume that the algorithm receives an input that makes it run as long as possible might seem a bit pessimistic to you. It's almost like we had a mean adversary who was trying to give us the worst possible inputs. But on the other hand, the advantage of worst-case analysis is that it offers guarantees. What I mean by that is when we take a worst-case view we know that our algorithm will not run longer than the worst-case analysis suggests no matter what happens. And this is actually what we're interested in in this course so we are going to use worst-case analysis. Meaning, we're always going to state the time of our algorithm for the worst possible input.

Worst-case running time gives us guarantees and also it sounds like it's a very big simplification, but the thing is as long as we're still counting the number of time steps of the algorithm exactly even worst-case running time can get pretty tricky and I'll give you one example for this. Again, we're going to consider an algorithm that takes as input a string of length n. What this algorithm does is given the string of length n, it counts the number of times that the sequence ab appears in that string. So it will iterate over the length of the string and if it finds an a, it will look if the next character is a b and if that is the case, it will increase the counter here. What I would like you to consider for our next quiz is what a worst case and a bust case input for that algorithm would look like. Here we have the number of potential inputs and it doesn't really matter how long those inputs are. It's more about their structure and if the structure would cause the algorithm to behave as it would in the worst case or in the best case or something else, and what I would like you to do is for each of those strings, tell me if that string will cause the algorithm to go into a worst-case running time, a best-case running time, or something else. For each of those four strings, I would like you to tell me if those strings caused the algorithm to have the best possible running time or the worst possible running time or something in between, and it doesn't really matter how long those strings are. It's the structure that I want you to look at.

To see how any of those strings make the algorithm behave, now let's have a closer look at it. The first three lines here are independent of the structure of the input. If you look at them, the counter is set to 0, we go through a range, and then we look if the letter that we're currently at is an 'a'. Those are independent of what kind of string we're looking at. We'll always be executing these parts of the code. But for those two parts here, that's kind of different. This line here, which is the fourth line, so this line here will only be executed if we have encountered an 'a'. And this line here will only be executed if we have encountered an 'a', then the next character is a 'b'. How often these two lines here are executed is dependent on the structure of the input. Now, in the worst case input, we would want these two lines to get executed as often as possible and in a best case scenario we would want them to get executed the least possible number of times. What we can already say is that a best case input will cause these two lines here to never be called and that only happens if the string does not contain the letter 'a' at all, which is the one down here. For the other strings, let's just go through the algorithm and count how many times this line here is executed and how many times this line down here is executed. If the string looks like ababab and so on, then every time that the algorithm encounters an 'a' it will execute this line down here and it will also execute this line down here because the next letter is a 'b'. Now, what if it encounters 'ab'? It will not execute this line, and it will not execute this line. And then it encounters an 'a' again, so this line will be executed and this line will be executed. And then again those two won't be. Then we have them both again. Then zero times and so on. Basically, for every two letters that it encounters, it will execute these two lines. So two lines per two letters makes one extra line per letter. Now for the second string, what happens is this. The algorithm encounters an 'a' so it will execute this line but the next letter is not a 'b' so it will not execute that line down here. And then it goes on to the next letter and again it encounters an 'a' so this line here will be executed but not this one down here because the next letter again is not an 'a'. So as the algorithm progresses, it executes one extra line per letter just as the string above. Now, finally, if the algorithm encounters acacac, what will happen is this. First, the algorithm encounters an 'a' so it executes this line down here. But then it does not encounter a 'b' so it will not go into this line. Next letter, the algorithm encounters a 'c' so it will not execute this line down here and so on. I think you get the picture. So this is not one extra line or letter but it will only be 0.5. It already tells us that the string here is not a worst case string but it's something in between. Now those two strings because they both require the same amount of time are either both worst case or they're both something in between. Now, this is something where you just have to look closely at the algorithm to see that a worst case input is among others one that contains as many times the letters 'a' 'b' as possible which is exactly this string. So there's no worse strings to encounter for this algorithm. So this one is a worst-case input. But surprisingly also this one down here although it doesn't contain the sequence ab at all it's also a worst-case input. Even now that we have introduced a number of simplifications. We have introduced the RAM as a simplified computer model to count the number if time steps and we've also said that we're just going to look at worst case running time you see that the analysis of algorithms can still be quite tedious. It's sometimes hard to identify what exactly a worst-case input will be. And even if we know the worst-case input, finding the exact formula for the running time is very difficult, which is why we're going to introduce another simplification to state running time and that simplification is known as big O notation.