Video 1-1: §1.1 Algorithm analysis

0:04 welcome back to comp 526 we'll start a new unit today on uh machines and models which will be about um representing mathematically what we mean when we talk about algorithms and data structures and their

0:22 performance my goal for you from this unit is uh to take some some fundamental understanding that goes a bit beyond just what you do for uh for programming I want you to understand what the difference is between an analysis and running time uh then the important Notions that we have for modeling different different parts of what we do in algorithms uh we have models for the input we have models for the machines and uh we have models for the for the cost of an algorithm for an execution and we'll touch on the main notion that that people use in computer science for expressing running time statements the ASM totic

1:06 notation uh again some of these things you will have seen in in previous modules if you've done an undergrad in computer science and some are also maybe uh used even outside of computer science now but we'll we'll go from first principles uh at a faster Pace than you would do this in an undergrad course but everything you need to know for this module is in there it's just uh coming at a relatively quick succession

1:35 so this this module is about algorithms so we should have a little conversation what an algorithm is what I'll give you is a a definition that still has some veness in it so for us an algorithm is basically a sequence of instructions and you can say the metaphor is a cooking recipe so it should tell you at each point in time what to do now the difference to a recipe is as you may know if you're a hobby cook sometimes the instructions are not so clear at least if you're not an expert cook there may be some steps that are not self-explanatory that's something we'll have to avoid for algorithms algorithms have to be explained in a simple language that's understandable even for stupid computers that have no common sense and no experience so they will be expressed in some formal formal language so what we mean by this is uh it has to be mechanically executable and for example that can be a Python program or any other programming language and we would distinguish this probably from a natural language description that maybe some large language model can translate translate to some code but in this case we don't have any any guarantees that it does the right thing we just hope it it does

2:54 something sensible uh for an algorithm we want precise instructions I'm most subtle point is it should be a finite description you have to be able to write it down it's maybe obvious to state but if you uh if you explain an algorithm on an abstract level it sometimes uh is natural to to specify things that if you spell them out for a computer it would need an infinite number of cases and that's not not allowed and then the last bit is to distinguish an algorithm from a concrete program not every program is an algorithm and that's the vake bit we we want algorithms to solve an entire problem or entire class of problems as opposed to just Computing a specific thing so maybe in in terms of this example if you're just Computing the sum of two numbers that would be just some program if you have a a method that computes the sum of any two numbers that's an algorithm of course that's a very simple program and we'll look at a few more more interesting problems but but that's that's the gist of it we'll usually abstract it like this uh as you will have seen so there's some input going into the algorithm then it does something and it produces some output that's usually our our model for

4:14 thinking of these of course output could mean it modifies a piece of memory that you provided provided it with that's also fine and to illustrate this an example of an algorithm could be the famous sort that we all know is not such a great sorting algorithm uh it's not so fast but it is an algorithm and it describes an idea that roughly tells you how to sort but it's not a specific program when you say bubble swort there's many different ways how you can implement it it depends on the programming language how it looks in detail and uh there's slight variations in bubble sword I don't want to get too much into this if you haven't seen it in detail but but if you do bubble sword you continuously exchange two neighboring elements if they're out of order and you do this from left to right until you're one pass through the data and then you do it over again now one version of bubble sword just cook until done do this until you've never made any exchanges so you do one more Passover the data where you don't do any exchange and then you know you're done another option is to say ah I don't want to do anything with checking I'll just do end passes and I

5:28 know end passes are enough if n is the input that's two slightly different variations but both would be would be called Bubble sword it's just the difference is too small so you would you would call it both uh bubble sword but of course the programs look slightly different so an algorithm for us often is a bit more abstract it's the the key essence of a of a recipe for computation um and I I understand this is a bit of a vague point but hopefully you will see many examples in the course course and then we'll recognize which ones are are coherent abstractions that might deserve a name so much for algorithms

6:22 slido the second part we'll be concerned with in this in this module are data structures they're often called hand inand algorithms data structures and uh that's for the for the following reason that they're very related a data structure is two things first of all it's some way of uh representing a piece of data in computer memory and what is data that depends and we'll see more examples in the next unit so I'll leave it I'll leave it a bit abstract here but it it's one it tells you exactly a data structure tells you exactly how to represent the data data you're storing in computer memory in bits and bytes and the second part is it has algorithms that tell you how to do something with the data in the representation that you have it and usually we distinguish it's either something queries just ask a question about the data and updates change it but you can have various mixtures and an example you may have seen if you've done that you must have seen if you've done in CS undergrad is a binary search tree um but we'll see other example

7:38 so much for the broad introduction uh in the next section we want to look a little bit about um the specific analysis so that's that's where the mathematical modeling comes in again so far it's been a bit wishy-washy in wake and the terms algorithms and data structures need to be a bit vague uh but what's come what's coming here is is trying to make things very precise

8:04 the whole motivation why we do this comes from the fact that if you have a certain algorithmic problem there are usually many ways to solve it and the question is which which algorithm or which data structure is is best suited so you need a way to tell good algorithms or data structures from others not so good ones I claim bubble sword is not good so I should have some some way to quantify that usually we mean fast but we might also mean space usage depending on uh the circumstances one or the other is more important um we'll briefly look into parallel algorithms where time is again a bit more complicated but we'll come back to that later so what is algorithm analysis uh it's is a a methodology that allows you to compare algorithms by measuring how how well they work and also to predict how fast they are and uh how accurate that is possible depends a bit on on what you define next as the model but that's the goal we want a way to compare different algorithms so that we can quantify their cost and find the one that has the better trade-off for us and if we if we pick a specific algorithm it's useful to be able to do at least the back of the envelope

9:26 calculation how fast it will be or how much memory it will take that's the feasibility check now one option uh to analyze algorithms would be Implement them and just run them and see what happens and sometimes that's uh the only option you have or uh it's the fastest way to go that can can be possible the problem with that is that it is a bit Limited in what you can what you can make as statements you can run things on a on a concrete computer and you will get numbers for that concrete computer but it's not clear if you can do uh if you can make predictions for other machines uh also you have to run it on some concrete input some data and it's not clear if the gener if you what what you find generalizes to other kinds of uh scenarios and lastly you have to implement it so if you think back when I said an algorithm is more of a the essential idea of some computational recipe if you decide you implement bubble sword one way and that turns out to be bad you never quite know if there's maybe a a slightly better way to implement it that would do much better and that's uh not so satisfying so in

10:45 particular remember I had this this comic about uh the philosophy of the module we we're after the universal truths of algorithmics and all of this sounds like not so Universal

11:05 so instead what we like to do is have some way of comparing algorithms that survives the current current Hardware so that we can make statements that are a bit more a bit more eternal

11:18 Universal we'll still have a model of reality that we might need to validate okay is that okay still works I feel I was a bit too loud earlier is that is it okay now okay I'm

11:58 okay ahuh right so I hope I hope the pluck is in in now again interesting is the volume okay so or like this or too loud too low you can hear fine in the first row but the guys in the back have to tell me looks good all right okay sorry for that so uh what this is all about is that we need a precise model to be able to do that if we just rely on the current computers that we have we'll only be able to say something about those and so we need to abstract from the rete machines we have if we want a statement that transpires beyond the current machines is maybe self-evident uh and we'll we'll come to uh how to model machines what we'll also need is a is a model for the data we work on because uh again we can try to run it on concrete inputs but we often want something that is more generic and there are three different models that people have used in in algorithm analysis a lot uh and you'll you'll be familiar with those or it's it's very intuitive the worst case performance means take the worst possible input and uh that's a bit pessimistic but if you have a guarantee that your

13:12 algorithm in the worst case is good enough it'll be good enough in any case best case means take a an optimistic point of view take the best that's usually just useful to rule out algorithms if already the best case is is poor then maybe it's not worthwhile exploring that algorithm an average case tries to ex to interpolate between the extremes and we'll come back to that in the context of sorting uh so here you're just assuming there's some random distribution over inputs and you're Computing an expected an expected value of the cost now these sound like you take all possible inputs and take the worst of them usually that's not well defined because we allow an infinite number of inputs if if the algorithm is for an abstract problem like add two numbers the two numbers could be arbitrarily big and it's unreasonable to expect that the cost of an algorithm does not depend on how big the input is so instead we'll group inputs by the same size all inputs of size n are one group and then all these measures above pick from just a fixed size so worst case would be the worst possible input with a given size or the worst the best possible input of a given size so for each of these three

14:33 different data models we would get a function of n for the performance it's not just a single number it's a function that tells you for each input size how long would the algorithm