Video 1-1: §1.1 Algorithm analysis

0:00 Intro

0:04 so welcome to machines and models that's unit one of com526 we will talk about the basic mathematical abstractions that we'll use for our algorithms the learning outcomes are stated here um just to Briefly summarize this we'll we'll talk about analyzing algorithms so when the last unit was a bit about proving to ourselves and others that an algorithm does the correct thing then this unit is more about does it do it fast because there are many problems where uh getting the answer uh in some unspecified time is as useless as never getting it uh we'll talk about the the random access Machine model um and the Big O classes uh and uh we'll check on a few examples uh how we apply this there will be more more examples um in the later units for specific topics and algorithms

0:15 Learning Outcomes

1:08 What is an algorithm?

1:12 algorithms class but I haven't really defined algorithms so far so at least in week two we should do that uh I'll go but basically by just a simple intuitive explanation algorithm is a sequence of instructions and you can think of that as similar to a cooking recipe but there's a few points where the analogy is a little uh breaking down or needs a bit uh more of clarification uh first of all uh as anyone might have noticed if you get passed down some recipes from your mom it's my sometimes not clear what one step really means and we don't want that for algorithms everything has to be so clearly defined that a stupid computer can execute it

2:05 we also insist that the program that's make making up an algorithm is finite so you can't have oh now let's distinguish all possible cases and I'll just list them all if there's infinitely many of them that doesn't count as an algorithm because you could never finish writing it down you could never feed such a program to a computer now what I've said so far is basically just telling you what a program is an algorithm on top of that should be a solution to a general problem so instead of just Computing some specific example it should work for a whole class of of problem instances and if you want think of it as not adding two specific numbers 17 and 4 but uh being given to numbers without knowing in advance what that number will be you can add them up with your algorithm that's the that's the distinction it's a little wow if you look at it too closely it's maybe not so clear what this means you can formalize this further but I don't think it has benefits for us the algorithms in in our module will always have this input output abstraction so you get certain things as an input then your algorithm does things with them and produces an output at the

3:18 end if you want a more typical example uh apart from just adding two numbers you can take a sorting algorithm for example bubble sword is maybe a the simplest and most well-known because it has a funny name and at least it's easy to specify another thing here that I want to make clear um the distinction between an algorithm and a program can sometimes be a bit fuzzy but what what we think of as an algorithm is usually an a core idea that makes up how the thing works like in bubble sword this bubble operation means you look at two consecutive things and if they're out of order you swap them and then you basically say cook until then repeat this until nothing more happens or you can say it a little more precisely go from left to right and continue doing that until nothing ever changes anymore and there's twists to that all of which we would say that's still bubble sort but there could be five different programs that all look slightly differently in the details uh but we want algorithms to mean something slightly more abstract again this is an idea that's hard to grasp because it would it would mean to Define what what is abstract enough I think in the examples that we talk

4:42 about you will usually have no problem distinguishing a concrete program from the algorithm from the algorithmic idea we'll mostly talk about algorithms but we'll also talk about data structures so what's the data structure question

4:54 What is a data structure?

5:03 pardon it's nice speak up uh okay there I will put them uh up after after class yeah apologies I think I promised to put the slides up in advance uh I think I just forgot for this I didn't make any last minute changes could have just uploaded them yep

5:32 yes you can you can always look at last iteration there's a few changes here and there but uh many bits are stay are the same so what's the data structure uh this is a bit more than an algorithm we also have a notion of state and we have a notion of of some things that are kept over time so in an abstract sense it's a rule for encoding data and the data structure specification will have to tell you what data means so it's a way to encode something in computer memory in binary at the end of the day plus it's a set of algorithms to to work with the data either query it ask questions about it or modify it update operations uh if you've seen a data structures class or algorithms class undergrad then you would have seen a binary search tree I hope that's uh one standard example and we'll we'll cover more so the unit 2 will be a basic recap of some of these data structures that that many of you will have seen but we'll recap them quickly so that everyone's on the same page

6:43 okay now that we've set the term straight we can start with the the real bit of this of this unit in the next subsection we'll talk about algorithm analysis so again getting at how fast is an algorithm as opposed to just does it get the right answer at some eventual point in time

7:05 Good algorithms

7:10 so why why do we do this uh often when we have some some algorithmic problem uh there are different ways to approach it and would like to find a good algorithm for it and if there are several we want to compare them now uh what good means depends on the application but most of the time it's being fast so finishing the job earlier is usually our main criteria and sometimes space is a concern as well space often has this weird Behavior if you have enough it doesn't matter but if you're out of space you're completely screwed and so it's a bit of a threshold thing if you can expect an algorithm to take too much space you have to worry about it if you expect it to be fine then time is the main criteria

8:03 I already said we want to compare different algorithms uh there's a second goal of algorithm analysis and that's if you think from an engineering perspective to predict how long something takes in a concrete application we'd like to be able to do that so that you can estimate if some approach that you have in mind is viable or not it's a very basic thing that Engineers do all the time I in I guess in programming and computer science it's a little less needed than elsewhere because we can iterate faster often it's enough to just build it and check it but there are there are cases where this is not good enough if you plan a big enough system or plan an entire architecture uh you have to know roughly how long will things take or is this is the resource consumption within the boundaries of what's doable it can also become a Cost question everything's moving to the cloud so computation often means uh dollars at the end of the month on your your AWS build so it's it's definitely relevant to make a a proper prediction of that

9:15 one obvious way to do a comparison of algorithms is implemented in run it as I just said already there has a few shortcomings that um in varies ways can can be a problem you have to know relatively well what you're going to do at the end with your algorithm or with your implementation otherwise you can't get proper test data that could be a real problem if you're if you're building a service that gets data from a client you don't necessarily know what's coming so all the results you find with running time experiments running time studies are valid for the machine you tested it on are valid for the concrete implementation you tested for the inputs you tested and all of that might not be what you eventually have also that's back to the university uh lecture and the the university course this is not really Universal truths if you run it on your laptop and you get one result and your your colleague runs it on on their laptop and gets a different result it's not ideal and also this doesn't sound like you can predict very well uh so what we'll Instead try um is through mathematical analysis where we have provable statements but they hold in a certain abstract model and we'll we'll come to that

10:42 that's uh the main main content for this unit and hopefully from this we can derive some hypotheses which we can then test in an implementation whether they are satisfied because often these models make some assumptions they simplified reality to a certain bit and you can try to design experiments to test whether those simplifications are Justified as I said many times the hope is that this is a way to get beyond the current iteration of technology in Hardware software stack all these things keep changing and so doing something that's only valid today is is not as valuable

11:26 what this means is we need precise models for all the things that are involved namely the machine that things are run on already you have lots of machines with you and they're quite different uh phones usually have an arm processor and then laptops have some multi-cores they have different architecture different instruction sets different operating systems of course as well so they they vary a bit we have to bring all that down to a unified model that hopefully captures the main aspects and we'll also have to model the input data remember algorithms is input to Output mappings and lastly what are algorithms that's part of the model as well

12:21 Data Models

12:23 let's start with the easiest uh because we'll usually stick to the the most basic one here that's the models for what input data looks like the traditional ones in algorithm analysis are these three either you're pessimistic and you look for the worst possible input for your algorithm or you're optimistic you hope for the best or you're you're the random guy and uh you look for the average uh over some some distribution over the inputs the average performance might be most realistic it's harder to compute though best case performance is a little dangerous um unless you can justify that this is to be expected so in in theoretical computer science people study mostly worst case assumptions and the simple reason is if you can prove that your algorithm is good in the worst case you're fine because that's the worst that can happen it sometimes leads to overly pessimistic predictions so sometimes you want to go away from that but in a way think of worst case as our default and if we have reason to believe that this is unrealistic that is this overly pessimistic we'll try something else uh we'll see we'll see a few examples of of each of this

13:52 now if you think about algorithms um they're supposed to solve a whole class of instances of a problem and usually these instances have a natural notion of size if you think about um a sorting algorithm it's clear that if you make the list much much longer it's kind of obvious it has to take longer to sort it whereas if the list is 10 elements you can probably do it manually so there needs to be some way of of saying the analysis takes this into account it can't make sense to say oh the algorithm always takes X seconds that's a lie almost surely because if the input grows the algorithm will take more time just to to read the input so what we'll do is uh assume some notion of input size and we always call that n pretty much always so little n is is a measure for the size of the input and part of the data model is that you have to specify what the input size is but is usually quite clear so for for arrays it's the number of elements it's a natural thing for Strings the length of the string can be natural uh for I don't know for a matrix it could be the total number of entries for graph it could be the number of

15:07 vertices or the number of edges it's usually quite clear what makes makes a reasonable estimate for the size and then we'll apply each of these data models for inputs of a fixed size so if we fix the size and then we take the worst possible input for all of inputs of that size that's the standard model what this means is all the statements we're making how fast is an algorithm you can't really say fast or slow you have to have a function that depends on the input size and most algorithms will get slower as the input gets bigger so the question is how much do they get slower as the input gets bigger that's why we'll study asymptotics at the end of this unit