Video 0-1: §0.1 Random shuffle motivation

0:00 Introduction

0:04 then welcome back to comp 5 to six in the rest of unit zero still kind of before the actual topics I want to discuss a few proof techniques so these are um some mathematical preliminaries that we'll we'll use in the background in the following uh it's more a bit of about framing framing the language we try to use if we want to be very precise and I think it's important that you're able to understand such kind of proofs and read them we won't usually go to all the level of detail that I'll show you today but I think it's it's important to know what that level of detail looks like so that you can recognize it and you can rep reproduce it if if you have to where uh things need to be extremely

0:46 Goals

0:50 precise and so the the goals for for this unit is uh to learn some templates for for proofs how they are uh structured to follow the logic of the statements uh specifically the the useful tool of mathematical induction because much in computer science is about discrete mathematics uh induction is a is a key tool that's often used and we'll briefly look at the case where computer science often uses formal proofs that's for for proving the correctness of programs that last part is not the key key topic for this module uh but I want to give you a glimpse of it either way

1:30 Motivation

1:34 I'll start with a little digression that um some of you have picked up already on campus wire I'll come back to that and then we'll go through these these things the the general proof templates and induction in a bit more detail and then how to prove programs

1:56 correct I want to start by um by motivating this a little bit um hold on I'm on the on the wrong deck of slides let's try again with the this year's state

2:33 the rest so far wouldn't have been wouldn't have been different I want to motivate a little bit apart from just me telling you it's important that you are able to read proofs I want to motivate a little bit why it's why it's useful to make very formal statements about

2:56 algorithms and uh I want to give you a small example of an algorithm that looks innocent and looks correct and even if you try it maybe it looks fine because it has to do with Randomness and Randomness is is tricky to uh to to pin down with tests because they come out different each time right so a toy problem you're given an array of numbers and you want to put them in completely random order you want to shuffle them it's a function that most standard libraries already have so maybe you don't have to implement one the point is this is a simple example that fits on a slide to illustrate the point so um how how would you do that well you could say um I pick a random position for each number and then I swap each position in the array gets swapped to a random other position and by random I mean a uniformly distributed random number in that range so that's all all good um once you've done that pretty much no element is where it was before and they're all kind of at a random position so it looks looks like a sensible way to do and then maybe um before I dive deeper I'll ask you bit about this I I'll Swip

4:08 back to the code in a question I've opened the question on slider now yeah but I go back to the code so you can take a quick look at

5:27 so we had something like 130 140 people on the previous slide of PS so I would hope to see a similar number for this uh while we're waiting there's there's two questions on on slider that I might answer so the the lecture today stops before 1 um the slot goes until 1 but we started 10 minutes late so we should we should be done by 221 the latest and the password for campus wire is on the announcement on canvas again four ditches I can't can't be bothered to remember them

6:45 so as you can see we have uh various statements um got votes now um around a third or so have trouble reading the pseudo code so um maybe it's it's worth going um over that part just briefly so is this this is this is a a kind of sud sudo code that is a little similar to many languages and has similarity to python but is uh I tried to use the syntax that is more unambiguous as opposed to more pythonic for example I use this colon equal for assignments because equal always is a bit ambiguous is that an equality comparison or is it an assignment so I'll try to use this for assignment and the double equals for equality comparisons and never the normal equal so I try to make it a little less ambiguous and then sometimes there's just things like swap the two positions in an array uh where it's it's just an English language sentence that um if you have some some programming language you probably can translate to how that looks in a concrete language and uh okay here I was just lazy you could of course assign a of I to some temporary variable then assign to a of I a of R and then a of R becomes uh the temporary

8:09 variable uh that's just a short hand and this is a function called where I didn't I didn't show you how this is implemented but let's suppose this is part of the programming library that we're using and indeed python has a library for doing that in the random library and all languages I know have uh a way to choose a uniformly random

8:43 um Let me show what I marked as the well correct for me the second one is of course uh depending on who answers um and so same for this one it's also true okay I mean so remember you can change your answer now and you can make make the green bars go all the way to the right but there's no real point you don't get extra marks for being correct on those and it's more interesting to see that a lot of people thought for example this answer is correct now if you keep changing the numbers or more people add it they kind of skew the picture a bit um but the point of these of these polls is to give you a feeling what the room thinks and uh also give me a feeling of what the room

9:30 thinks uh but if that bar goes up I'm happy uh it can generate all possible orderings of the array that's true but all the others um are not in particular it's not really solving the problem we are trying to solve I'll I'll just demonstrate you briefly why um if you take an array with just two elements and you call this function and analyze How likely is it to go each way so uh what I'm showing you here is the probability that the outcome is one two the same order you put things in or 21 that's the only two possibilities with two elements and they're equally likely great so we're on track but if you start adding more elements for three elements there's already two uh three permutations that are a bit more likely and the other three are a bit less likely now how did I arrive at those numbers and that relates to the campus wi question um and I want I want to give a shout out to the campus wi question it's great that uh some people experimented with the code implemented it and tested it uh it's good for two reasons uh it means you engage with the material and the second one it is nice for me to make the point that Randomness

10:42 is tricky to nail down with tests um because they they implemented the corrected version that I'll show in a second uh but if you if you run the method several times the outcome is random and so it's it's hard to gauge if it's correct or not just from looking at tests what I did to produce These Bars is uh I basically analyzed the function theoretically and looked at what are all the possible outcomes for the calls to this random method and this is discrete here right it only has n different choices in this case but you have to do it for every Loop iteration if you go through that and go through all possible options each has the same probability but the outcomes are not equally distributed

11:34 and uh things get worse if you go to uh larger lists and then I stop because it got it spiraled a bit out of control uh you have many many things to try but I want to point out here um this this green bar is the average or is where uniform should be one over n factorial for n elements and you see some elements are almost twice as likely some of the specific orders so it's it's not even it's not just wrong in that it's not perfectly uniform it seems to get worse with larger inputs and that's a bit well it's a problem if you want it

12:14 uniform now uh so don't don't ever use that code um we discuss that this is a simple way to fix this and I'm sure some of you will know this it's a well-known algorithm um I would call it the can Fisher Yates Shuffle because all three were involved in is maybe basic enough to have been reinvented independently a few times the only change you really need is restrict the range of this random position and then it works fine I don't want to go into detail why it works that's not really my point in this unit and it's also not about this this lecture is not so much about random generation and yeah there's good Wikipedia articles about this algorithm if you repeat my experiment then you see it it comes out perfectly un form to give you a quick intuition why the previous method cannot possibly have worked is if you just analyze the number of possible things it can do it had n iterations and Drew one out of n choices each time so that's n to the N different things but the number of permutations is n factorial and these two numbers are not equal and there are even uh they're uh co-prime so there's just no way this could have worked in hindsight maybe

12:18 Random Shuffle

13:28 this is obvious is or depending on who looks at it maybe but uh that's that's a quick way to prove the previous code cannot be correct doesn't tell you how to fix it though but yeah in this case uh it's already been invented and so uh we don't have to worry about it but what's the point of this my point is the previous code looks quite reasonable if you read this in a code review maybe you'd say yeah it looks like a good random shuffle uh and it looks very similar to this code so how can you tell them apart with certainty H and again who guarantees me that I've done this for up to five elements maybe something wonky happens with six seven or eight elements there's too many options for me to try at the very latest so maybe 11 factorial is still doable but 20 factorial is out of the question it's just too many different things so there's no way a test will get you to the right answer so the only thing that's left is a as a formal proof or a theoretical analysis of the algorithm that can tell you with certainty this one's going to shuffle correctly right and that's that's why um why we're stressing this in algorithms

14:44 so much many algorithms look reasonable and are just wrong it's very very tricky to find the difference to see the difference