Video 0-2: §0.1 Random shuffle motivation, logical statements

0:00 Introduction to proof logic

0:02 welcome back to com526 efficient algorithms we're starting with the second part of unit zero and look at some proof techniques these are some prerequisites that we need to digest some of the statements we make about algorithm and data structures later although this unit will not really con contain much algorithms and data structures we take one further step away from that so this is just about logic and Mathematics but you'll see where it comes back to programming towards the end foreign a few learning outcomes you're supposed to know some proof strategies and will become clear uh what these are is a it's a given list of of things um there's certain types of statements and each comes with a strategy how to prove it that's just the scaffold for a logical argument you still have to fill in the gaps specifically one that's particularly important in computer science is called induction we'll talk briefly about this later and we'll apply proof techniques very briefly to give you a glimpse of how you can prove a program correct and what that means we'll only touch on this very very briefly but I think it's it's useful to know roughly what um what the limitations and possibilities are there

1:33 Array shuffling algorithm

1:35 before we start with the actual proof techniques I want to take a slight digression and actually do look at one algorithm um and you'll see also the type of of code I'm using on the slides mostly and this is just as kind of a backdrop for what's to follow so without much um introduction let me say we have a goal to shuffle an array of numbers so there's a few things I should maybe point out this is my notation for arrays haha so what is an array uh an array is a contiguous piece of memory filled with data and all these individual data items have the same size we also usually think of them to have the same type but some languages don't pass about that so strictly but here I'm specifically saying it's it's numbers so if you if you have programming background think of a c type int array that's fine for this purpose although the algorithm doesn't care too much uh the second bit of the notation is this convention for indices a race started zero in this module it's just the computer science way of thinking it's a pointer in an offset uh that's where this comes from so if we have an array of n numbers it starts with a0 and

2:59 then it goes up to a n minus one and to not always have to write the -1 I'm using this round parenthesis to say that's exclusive the end part endpoint and the zero is inclusive if you come from C plus plus and have worked with uh with with iterators and pointers there it's quite natural um to work start Point inclusive endpoint exclusive if not it's a bit of uh weirdness to get used to various um it's consistent in this module so it's worth getting used to it right so that's an array that's an array of numbers um and one first thing to note n is just any variable I want this to work for any size of an array and the goal is to randomly reorder the array so Shuffle here means you have you're given an array of numbers and afterwards it should be impossible to know what the original order was because it just completely randomly rearranged all the numbers implicitly what this says is it should still contain the same numbers the same multi-set of numbers just in some different order so we expect algorithms to basically swap two elements that's the that's the key thing that an algorithm can do to rearrange elements take two indices take the element here out take the element

4:24 there out put them back in the opposite order okay I mean this was uh this was maybe baby steps for some of you but bear with me a bit um now that's that's a task that arises uh various applications uh in data science applications you may often want this to kind of avoid any bias from the initial uh the initial order of the list say you're writing some survey software and you want the answers to appear in random order for each participant uh all sorts of things fairly natural to come up with um more examples and here's some code that might achieve this and before we dive into what the code does let me try to briefly explain what this kind of pseudo code uh looks like is not real code in any programming language I don't know any compiler that would eat this and spit out a computer executable but it's fairly close to many languages with slight superficial changes so I'll write procedure to say this is definition of a function it's maybe a bit closer to Old languages like Pascal python would just be deaf right then there's the name of a function and it takes some parameters and not usually strict with typing so uh that's maybe pythonic then uh close to what python does they don't

5:52 care about types as much so there's one parameter of this Shuffle function namely our array not a big surprise I hope then we can write different things in pseudo code so for example for Loops right they just go through what is indented further uh for every value of I in the given range we have other function calls and in this case I'm calling a function random in that I'm just assuming postulating that this function exists and the comment here in in English just tells you what I'm hoping this does most programs have some assumptions like this and it's super tedious to always have everything on this light and you couldn't read it so we'll usually work with something like this there's some things we just assume given and then we work based on that and here's the swap operation that I explained before we expect an algorithm to use this here and here it's it's just writing take the position I and take the position R these are two variables they have some some integer index in the array take the elements and swap them right I hope that's fairly intuitive to follow I also hope that at least by the end of the term all of you would be would be able to do

7:11 take this pseudocode and code it up in Python hopefully a bit earlier than by the end of the term for this simple thing um or take another programming language uh this is this is my approach to be a little agnostic to what language you come from good so that's about the pseudo code um how we write algorithms now what does it actually do well it looks at each position in the array that's basically the I and then it finds a random position for that element to go to and it swaps it there sounds good that should put it in in some random order

7:27 Analyzing shuffle correctness

7:57 now okay let's let's just do this um see what you could come up with foreign 64 people saying they got the attendance code so maybe we can crack that up and that number in the in the corner maybe we can get that at least to 65 60 64.

9:36 there's probably a few more in here okay let's um let's see find 65 is my goal uh and let's briefly just see what you came up with uh so a lot of you have seen something like this before that's great so you can deal with the code um not so many are sure about this it seems right um more people are confident about the last part that's the longest statement right if it's convoluted in the formulation It's usually the right answer

10:12 so let me lock the results for now [Music] um and switch back you mean the last two parts DNA depends how picky you are yeah okay okay I get your confusion so the point was it sounds like e is a subset of D and you're right I mean this I've slightly reformulated this to make it sound a little confusing but it's you're you're very very right uh and so it's it's kind of surprising that more people ticked e than D to you is that what you're saying well it's a it's a subset in the sense of the statement so it could be that e is true and D is false in principle that's possible um in our specific case d and e really is the same because I'm assuming that this random end does the right thing that's not the trick of this question uh the the trick of this thing is something else and let's have a look at this so how would we take a step back forget about the question for a minute I'll come back to it but how would you even approach saying that this code does the right thing so what is the right thing yeah

11:43 Identifying algorithm flaws

12:18 sure yeah you gentlemen swap with a random position probability right one over n equal s a in a sequence the probability of them occupying each getting associated with each hour which number is the same thing except like the first element in the description map to any number of potential energy same one of our own probability let me try to summarize this for the live stream so are you saying uh this random end gives a uniform number in this range that's that's exactly uh the assumption and so it seems that every element should be at a random position and the overall thing is uniform now let's look at what happens so if you if you take two different elements it's the easiest kind of thing that is at least doing something there's two possible outcomes and these are listed here and what these bars show is the relative probability of them becoming the result of this function and it doesn't matter how you start so you could start with a sorted list if you want uh now if you do this for three elements something weird happens so this is starting from the sorted list and then uh calling this algorithm many many times and looking how often you've seen the different outcomes and it gets worse and worse

14:03 and then I ran out of space on the slides but you can you can continue this um you can even analyze this and show that in a way the the relative error so if this this red line um one sec so the red line is basically the uniform that you would want to see and so the the difference between the Peaks and this line become even worse yeah

14:36 no it's not converging to uniform it's not a problem of small n um and it's even worse it's kind of diverging from uniforms this there's some some things some orderings that relatively speaking the probability of them coming out compared to what we want the uniform one over n factorial that relative difference grows within is completely broken it's startling right it looked so well and I mean those of you who know this they might have seen they might have immediately seen the argument so that I don't want to spend much more time proving to you that this algorithm is wrong a simple way to do it is to count the number of possible outcomes that's a nice rigorous way to show it so here we're taking n random numbers and each has a range of n that's n to the N different things but what we want is uniform Over N factorial just by um pitch and hole principle arguments this cannot work out but this is not what I'm what I want you to take from this the thing is for showing that the algorithm is broken all that's on the slide is enough it doesn't work for three elements what the right I mean that's not good even if it's fine for larger inputs

15:55 this is surprising and we don't like an algorithm to be wrong uh and so even if an algorithm looks really intuitively correct it might be broken in fundamental ways and so we really want some Machinery to be sure that's what this modu what this unit is about uh and well to make that point really clear never use this I'll show you the correct one in a second and so in terms of this this question uh you can see how you did I mean this is true for me so uh the first two are not relevant but it's true that the algorithm can produce every possible ordering with some probability it does but neither of the other two statements are correct

16:46 Formal proofs and systems

16:51 the fix for this is super simple it's a single symbol you have to change instead of zero you put an i here and then it works um intuitively why that is so different think about how an a single element can travel in the original algorithm it could be swapped several times around if it got selected again whereas here we go through every element and then for each position I we now decide which original element is going there and then once it's there it's never touched again because I goes up and we don't have R below I so after we made this this swap so for each element we have one one point in time where we decide this is your final value Chuck and then it stays there for good that's why this algorithm is good that's why this Bears the name of three famous uh people it's usually called the the Fisher Yates Shuffle uh knuth popularized it um they all deserve uh credit for many things this is a fairly simple algorithm so maybe it's uh it's all right but then that's the name it goes by uh so if you ever need to shuffle look for for this one um don't use the other one so both of these algorithms look intuitively fine but they lead to

18:15 different outcomes so we really want some some way to tell them apart the way to tell them apart relies on on formal proofs and there the first step is um formal statements logical statements and then how to arrive at the validity of such statements so if you want to go all the way back this is the very question that mathematicians answered in the 20th century only in the 20th century somewhat remarkable um what does it mean to have a proof prior to that a proof was if it was convincing to your your fellows the other mathematicians in your guild that it was good and if it wasn't convincing them it was not good but this was relied on people to be diligent enough or apply enough scrutiny to these arguments and in the 20th century some of the uh the big successes are putting maps on a formal Foundation and discovering the holes in there there's some fun fun story around impossibility results but what we do have is a clear understanding of what formal proofs are and if you can't prove it in that system it's bulletproof that's why I have this little Iron Man for the uh for the unit as well

19:48 it is impossible to do something that are not reliable is it possible to prove things that aren't true that would be really bad for a formal system there's many examples of things that look true and look like provable

20:32 okay so you're getting at um consistent and complete systems let's take this offline we can we can chat about this afterwards because I think it's um for most people doesn't doesn't help much at this stage before we talk about other things and it's uh it's it's beyond the module but there's um there's some really cool math theory behind this it's a lot of fun uh you don't need to worry about it for this module but uh it's definitely worth knowing I can talk about this at the end of the of the slot um so what we need a formal proof is written in a formal system and that tells you what kind of statements you can write to make proofs of and so formal proof is a sequence of such statements and each statement can either be an axiom that's something that everyone decides we believe in that because we decide to believe in that there's no justification beyond that but they're usually so clear and and primitive that they're they're fine and this is not usually a problem um but the experts Axiom of choice there's there's some that are debated but this is on the philosophical and esoterical end of of mathematics uh I'd say uh there's a a set of axioms that people

21:51 rely on uh and there's no doubt about them and we can we can restrict ourselves to those for this module entirely so and the statement is either an axiom something that is true because everyone decided let's rely on this or it is something that follows from previous statements using a set of rules and we'll see some of these um in some of the example proofs but these these two things together imply if if you start from valid axioms and you apply valid rules everything you'll ever be able to write down is valid by definition and so there's no interpretation needed or no human scrutiny needed some of these systems are probably incomplete so they they're true things that they cannot show that's a bit annoying but if you have a proof it's not a problem the proof is valid and the proof is rigorous It's just sometimes you need to go outside of a specific system so that becomes relevant if you want to prove things automatically by your computer but that's not not our topic for this module uh we'll usually actually go back to convincing humans because going to this level of detail is very very tedious I want to convince you in this unit of that fact um and also try to

23:16 show you how you can uh live on a slightly more abstract level but keep the keep the possibility of going all the way down if you have to for example to check in in cases like for this Shuffle algorithm where it seemed to work fine but uh if you look close enough you notice it one does and the other does it good okay let's let's dive into um some of the statements that we can make

23:39 Logical statements and terms

23:50 um and I'll use English language examples here first just because it's a little uh easier to talk about we'll mostly have mathematical statements here later so we can have statements what's the statement a statement is something you say that can be true or false we'll usually not allow anything between it's either true or or not true which is the same as false okay there's no no gray areas uh and so a great example is it rains which is already debatable if that's always either true or false but let's pretend right you formalize that in some way if there is any drops reaching the ground or I'm sure this gets hairy if you define it properly but let's uh ignore this humans are usually good at having a sort of some weakness we could tolerate well a second statement can be the street is wet similar problem but let's pretend this is very clear and always true or not true if we have a statement we can negate it then instead of the statement we have not the statement so not a is not it rains we use we usually say it doesn't rain logically the same thing we can put and or or between two statements A and B it rains and the street is wet both have to be true for

25:11 the whole thing to be true and or means well either of them can be true it's okay if they are both true so this is not an exclusive or uh sometimes so

25:28 um sometimes it's useful to have the statement it's either a or b but not both in one thing as you notice English doesn't really have this we often use or in the sense of exclusive not both but not always and if you want to be very clear you have to wiggle your way around and say it explicitly either A or B and not both

25:54 and sometimes convenient to have a annotation an operator for that and Export is is the thing that people use for that I don't know if we'll ever use this I've seen this notation many times uh for for Boolean logic reasons but well so this this this statement is true a X or B is true if either a is true or B is true but not both and also not both false please clear

26:22 okay the more interesting ones are implications and equivalence that builds on it implication is written as this a arrow B A implies B in English we would say if a holds then B also holds something like that if a then B and this is really equivalent to Not A or B in case of Doubt uh we'll we'll come to that but here if I insert what a and b means it becomes relatively intuitive so if if it rains then the street is wet sounds good equivalence is one step further it says a and P are really either both true or both false uh so a equivalent to b means a holds if and only if B holds and because this is something we use so often mathematicians have invented this if with a double F to mean if and only if

27:25 just the if is implication the only if a only holds if B is true is kind of the reverse implication so that's why you can also Define this a equivalent to B by having both implications a implies B and B implies a yep question

28:02 then if a is B implies a yeah okay so these these are two useful terms uh necessary and sufficient conditions yep and vice versa and if yeah that's like I find it an easier we think of education and um yeah yeah that's that's right so this this alternative um names for these if you want uh a implies B we sometimes say a is a sufficient condition for B if a holds then B already holds um and the other way around uh B is a necessary condition for a if a is supposed to hold then B better also hold uh it's another way to phrase it I mean yeah it's it's more intuitive for some people uh and others others like the implications more um or you think in terms of Venn diagrams you have to find your way um it's something that this book gives you all the different variations of and you can pick whatever you find more intuitive

29:21 Logical implications exercise

29:23 now let's do a little exercise on this one huh where's the question sorry now he's showing it's annoyingly slow I don't know slider has a problem today I hope we don't have too many flat eartheries in here

30:54 all right uh let's show it again okay well because I give patches Vision marks I shouldn't lock the questions too early uh so it's roughly two-thirds one-third maybe a bit more for yes but a few for neither as well uh

31:18 so this is this is a true statement in The Logical sense and the good thing is it doesn't depend on whether you believe the Earth is flat it's simply implications are always true if already the premise is false um and that becomes obvious if you say let's decompose this into our statements that's statement a if a then statement B

31:42 now maybe we can agree that b is not true but doesn't matter a implies B is the same as maybe I'll write it down this um Not A or B

31:59 that's just the definition of implication for us that's why I'm I'm bringing this question so if if a is false and we believe a is false it doesn't matter what B is if B is true or false we don't don't need to care