Video 1-1: §1.1 Algorithm analysis

0:00 <Untitled Chapter 1>

0:03 so welcome to unit 1 of com5 to 6. this will be about machines and models the mathematical background a little bit of how can we make formal statements about algorithms data structures and their performance and we will also touch on on the big o notation which is the ubiquitous language in computer science to express performance and you will just need to understand what it means and be fluent in using it uh to be successful in this field so let's get cracking i will cover

0:41 Outline

0:44 knight forwards we'll have these three topics we'll first talk a little bit about what it means to analyze algorithms um what that is about and then i'll i'll present you the dominant model in algorithms and algorithms and data structures these days uh again this is more for your background information but you will you will find it useful if you dig deeper to know about this and lastly we'll talk about the big annotation that i just advertised for

1:26 so first what is an algorithm to get started with uh i don't want to dwell into two formula definition at this early point um but for me an algorithm is a sequence of instructions like a cooking recipe

1:34 What is an algorithm

1:41 and so the way to think about this is you tell the computer what to do and then it does it that's a sequence of instructions in modern times algorithm has to come [Music] it has to become has become a meaning for for all sorts of more complex systems usually involving some machine learning and artificial intelligence they kind of grabbed this term from us the true algorithms people and uh it also got a a weird negative connotation like the uh the a level algorithm from last summer which is essentially just a little formula that someone decided nothing malicious or wicked in it it's a bit unfortunate but i would i would very much like you to follow my definition definitely for this class an algorithm is a sequence of instructions and it does what you tell it uh what what you tell the computer to do um an algorithm is a little bit more than just an arbitrary list of instructions we usually restrict it in the following sense first of all it has to be computer readable at least at the end we sometimes do the pseudo code algorithms in this class and they're intended to be an at an intermediate level so a good programmer can easily implement it but there should usually not be common

3:12 sense needed in the human in the human understanding of it you shouldn't require a human to execute this that's for sure also the sequence of instructions has to be finite it's not an algorithm if you need to go through an infinite number of case distinctions and sometimes these come in disguise so that's why it's important to stress it and lastly it should solve a problem by which mathematicians and computer scientists understand a class of instances that are a problem is a challenge uh and in in this in this meaning it's yourself a more generic version instead of simply computing the sum of these two numbers you have an algorithm to compute the sum of any two numbers no matter what those numbers are so the typical way to think about algorithms is that

4:10 there are a box like this and then there's some input fed into the algorithm and then it spits out an output that's the way of of thinking about it as a mathematical function that doesn't capture all algorithms very nicely but it's a it's a good first approximation again a typical example might make this uh clearer than the abstract description um an algorithm i would say bubble sort is an algorithm but it's not it's not about how x-lac exactly you bring this in the form of code it's not the java code that you produce that implements bubble sort the algorithm is more the conceptual idea of how bubble sort sorts it's a bit awake i agree but it's it's again something that from examples it often makes makes sense

5:05 What is a data structure

5:07 we have a second a second topic that we'll talk about in this class apart from algorithms we also have data structures they often go hand in hand my definition for this class is the data structure is two things i have to say how i'm storing data it's about representing a certain type of data and i have to store this in computer memory so i usually have to say how it encodes in binary at the end of the day and the second part is a data structure has certain up certain queries certain operations that it can support on the data and you have to tell you have to tell me algorithms that execute these these operations so an example that you might have seen before in some undergraduate algorithms class is a binary search tree it tells you how to represent data there's a certain way to store the nodes and they have pointers etc and then there's algorithms to insert new things etc if you haven't seen binary search trees before i'll give a quick recap in the next unit either tomorrow or next next tuesday

6:19 as always if you have any questions just fire them up just shoot them in the q a the that concludes the first little introduction with just the definitions now the first real part of this unit one is about algorithm analysis

6:44 so in this section we will talk about what it means to analyze an algorithm and what we can hope to get out of this for many problems we have not just one algorithm but there's many many possible ones and we want to find a good one or maybe even the best one for a certain task that we want to solve and by good we usually mean it should be fast and it should use little space maybe just one of them there might be other ways there might be other measures depending on the application maybe you want an algorithm to have certain additional properties depending on the on on the problem it might have to be fair and that what it does um satisfies the certain fairness conditions etc etc but for this module we'll mostly focus on how fast it is and a little bit on how much space it uses and that's for the for the basic toolbox of algorithms that's usually the core interest that you have an algorithm analysis is a way to uh find good algorithms according to these measures it's a way to compare algorithms and also to predict their performance in a given application what you often have to do if you design a computer system is make a back of the envelope computation

7:25 Good algorithms

8:07 if this is at all feasible if it's at all possible to use a certain approach that you came up with and for that you will need um algorithm analysis to make these predictions if it's if it's feasible to use a certain proposed method for this or not

8:30 um a simple thing you can do is you just implement your algorithm and time it and run it and time it that's fine and it's useful to do but it has restrictions it has limitations what you get is a result for a single machine you can compute it you can compare it on many different machines but then often the results are inclusive or they're different depending on the machine is also restricted to the actual inputs that you used which might sometimes give a very skewed picture and again it's restricted to a specific implementation the one that you produced and tried out and maybe there's maybe you made a stupid mistake in implementing something unnecessarily inefficiently and someone else has a better idea you wouldn't see this from doing experiments and if you think back uh what i mentioned on the last slide of the of the organizational unit i want this course to be focused on the universal truths of algorithmics uh the the statements that survive time and survive uh changing machines like statements that survive the pentium 4 if that still exists at all it's probably all i don't know laptops have the the um the new generation but how about desktops well uh i lost track of that a bit because the universal troops are just so much

10:02 more um satisfying to to work with so what we want is we want to analyze an algorithm on a slightly more abstract model so we want to go a little bit away from an actual machine just as much as necessary to prove mathematical statements in this model that sounds that sounds more mathematical than it actually is in most cases you will see examples again and what also comes out of this is hypothesis that allow you to test you can validate whether the model you made is too abstract to be useful for that you would again do experiments but those would rather focus on the model and not on comparing different algorithms so what that means is we need models for the different parts of of an algorithm and that's what we'll look at next first of all we need to somehow say what are the inputs of an algorithm like if you run experiments you have to supply certain inputs and that limits what you can get as a statement in algorithm analysis you typically have three different models for inputs you can either be very pessimistic you always expect the worst possible input will come as a guarantee that's great if you have a worst case performance that is sufficient for your application you can be

11:32 sure that nothing bad happens even if the worst of all input comes it's still good enough best case performance is the opposite you hope for the best and just pray it's not used a lot but it's sometimes helpful to show how far worst and best case are away from each other and more useful but more challenging to get is an average case performance where you assume that inputs come somehow randomly in a certain sense and you will have to specify this but you might as as you might for example assume that every input is equally likely and then you can look at what's the the random cost so for example the expected cost of an algorithm under this distribution and we'll see examples where the average case is very good whereas the worst case can be bad but seeing this worst case in in any application is astronomically unlikely so you might just go ahead and use the average case result

12:40 why do we do these models which are a fairly strong assumptions in each cases in each case um the goal is to have performance as just a function of one parameter and that's the the input size n what input size means depends a little bit on the problem again for a concrete problem it's often natural what to pick and we'll see examples in the loop invariant example the length of the array that would be a natural measure for the input size sometimes we need we need others