The Math Needed for Computer Science

we're gonna start this video off with a puzzle for those who don't know this is a numeric 8 puzzle it scrambles the tiles and you have to move everything one tile at a time until you have a back in numerical order the question for us is if you were to switch these last two tiles is this still possible to get back to the correctly ordered configuration can you logically prove whether it is or isn't now we'll get to the question of why would anyone need to know this but for now just focus on the mathematical reasoning here people have just gone through high school math might be looking at this with no clue how to start you might be waiting for a formula like you're being asked to solve for the volume of something but that's not the case here there's no formula it's just logic and reasoning as a different kind of math compared to what we see throughout high school again we're trying to get the tiles in numerical order from left to right and going down as if we're reading a book so what we can do is lay the tiles out sideways with the blank spot being at the end and just look at them with a different perspective but we're curious whether this is possible to solve when the last two numbers are switched now let's analyze what happens when we move a time if we do a sideways move on our game it's which is the location of the number and the blank spot notice that the relative order of the numbers does not change though a sideways move actually preserves the order of the numbers then if we do a vertical move and bring the five down it's now ahead of the six and the eight in the linear model the five moves to places backwards bumping the six and eight forward in fact whenever we move a tile up or down it will move two places forward or backward respectively and this is the only way to change the relative order of our numbers remember this vertical moves can only move a piece to places forward or backward now let's go back to our initial set up real quick with a seven and eight out of order and look at how many pairs of numbers are out of order the one in the two are in order because one comes before two as it should one and three are good even one and eight are good because one comes before eight numerically as it does here in fact every pair of numbers is in relative order except 7 and 8 thus we have one pair out of order the goal is to have zero so now let's do another vertical move and move the six down on our linear number line we know the six moves two places to the right but before I move it look closely originally the six and the eight are in order because six is supposed to come before eight once I move it they are out of order and our out of order pairs changes from one to two but of course we're moving at two spots it was in order with the seven but that changes as well leaving us with three pairs out of order so we did a vertical move the number moved two places backward which changed our out of order pairs by two one for each move in fact no matter what the order every time a tile makes a single move along our number line that out of order pairs will leave their increased by one or decrease by one if the two numbers are out of order after a move they will be in order thus however many out of wear parents we have will decrease by one and if they're initially in order after the move they will be out of order doesn't increase in one each single move makes the out of order pairs either increase or decrease by one but remember when we move vertically is the only way to change the order of everything tiles move two places over that's our only option if each move either increases or decreases that out of order pairs by one then after two moves you can either have a change of two a change of zero however it may happen or a decrease in two this is all that a vertical move can do if our puzzle starts with one out of order pair and these are the only options no matter how many moves we do adding to subtracting two are staying the same there's no way to reach zero out of order pairs which was our goal thus this puzzle is impossible hopefully this wasn't too confusing but I really like this example this is a famous problem in discrete math and is even taught at MIT in their mathematics for computer science class I like this example because there's virtually no mathematical background needed but it did involve mathematical reasoning and I'm sure most people just can't look at it and understand it immediately computer scientists and mathematicians have to do proofs like this all the time to understand a system or model from the ground up and I hope you'd realize that it's very different than what you see in most high school math classes this videos really on the mathematics that computer science and math majors see as well as a few others but I really want the focus to be on computer science because especially research this is the kind of math you will need a foundation in in this video and the next I will show applications but the proofs won't be anything that a mathematician would approve of due to time now let's go into another proof that's much easier and again needs no real mathematical background just logical reasoning let's say you have an 8x8 checkerboard with the N corners missing the question is can you fill up every space with 31 Domino pieces well an 8x8 checkerboard has 64 squares minus 2 from the ends missing is 62 and 31 dominoes that cover two spaces each would cover a total of 62 spaces but how can we show that it definitely is or it is not possible to cover the entire board see if you can get it but the answer is fairly simple whether you orient the Domino vertically or horizontally it will cover one black space and one red space therefore 31 dominoes would have to cover 31 red spaces and 31 black spaces if you notice those missing end pieces are both red which means there are 32 black squares and 30 red squares like we said we would have to have 31 of each and since we don't there's no way to cover the entire checkerboard with these and our proof is done these proofs are often the beginning of a discrete math class you will learn proof techniques like proof by induction or contradiction that I won't go over so no it's not just all puzzles like these well these were more general examples that might not have a direct obvious application you have to learn these proofs so you can then apply them to the more applicable problems which I'm going to go into now starting with graph theory this is a huge field in math and computer science in graph theory graphs are not like x squared or sine of X graphs have a bunch of dots or nodes and lines that connect them or edges the applications for this are endless maybe these nodes represent people and the edges are compatibility according to their dating profile you might need to figure out an algorithm to best match every one because lots of pairs of people will be compatible on these sites nodes could represent computers and the edges are cables that connect them where data needs to travel the shortest path to reach its destination or nodes could represent destinations like cities and edges or highways or roads that connect them many of these problems are not very easy but here's a simple question you can use graph theory to solve in a room of twenty seven people can everyone shake hands with nine others well since this is graph theory we'd have twenty seven nodes which represent the people I won't show all 27 dots but here some to illustrate the solution now if a pair of people shake hands we can represent that with an edge so right now this person took one person's hand and to us this other person the question is can everyone shake hands with nine others to solve this really need one piece of background information look at this graph I just randomly found and count how many edges or lines leave this dot or note of course there's only one this is the degree of the note now what about note 4 what we see there are 4 edges leaving it which is its degree if we do this for every node these are the amount of edges leaving each one or the degrees add all these degrees up and we get 10 now that we have that count the amount of edges or lines that you see you'll find there are five which is half the sum of the degrees if we look closer we'll see this is always true every edge connects two nodes so that one edge makes both nodes have a degree of 1 for a total of 2 so we have something very important here the sum of the degrees adding every single line that leaves each dot is always twice the amount of lines or edges that you see now we can go back to our problem if everyone must shake hands with 9 others then every node or dot needs 9 lines coming from it meaning they gave 9 handshakes therefore every node would have a degree of 9 if 27 nodes all have a degree of 9 then the sum of those degrees is 243 and we said the sum of the degrees is always twice the amount of edges that means there are 121.5 edges which is not possible the amount of edges or lines has to be an integer like 1 to 103 etc so the answer is no in a room of 27 people everyone cannot shake hands with exactly 9 others if you did not get that try this next one if we have a bunch of nodes that represent locations maybe cities and edges which represent roads between them can you find a path that travels every Road exactly one time and ends exactly where you began so you can pick where you start and once you use a road you can never use it again I'll just tell you the answer is yes you can go to each city and use every road only once there is more than one way to trace his path out but this is one way to go for every edge only once and end up exactly where you started this type of path is called an Euler tour where no lines are repeated and you end where you started now real quick there's a sort of a side tangent and I don't know why I remember this but when I was in high school one day my friend challenged me in class to draw this shape but with two conditions I could not take my pencil off the paper and I could not go over the same line twice this was just randomly brought up by the way my friend probably heard it from another friend but no matter how many times I tried I could not do it I was always like one or two lines off but I could not complete it because it would require me to go over the same line twice I think I remember this because I tried so many times that was bugging me neither of us knew whether it was impossible or we just couldn't find a way to do it but years later while learning graph theory I read over this one theorem then almost immediately took out a pencil and paper and drew the shape which I still had in memory I took a single look and realized finally not only is it impossible to do but I do exactly why and I want to explain that here so why can we find a path here that goes to every city once without reusing a road but we cannot draw this shape without retracing a line well on this graph that we can find a path for we have to start somewhere we then have to go to some node via some line or edge then we have to leave that node and go to a second via a different line or edge every time we take one line to get to a node and another line to leave it and if we ever return to that same node it must be via a new line and we must leave via another new line notice all these come in pairs so in order for an Euler tour to exist such that we never repeat and edge every node must have an even degree for every line that comes into a node a different one needs to leave just like you see here if you look at the degree for every node they're all even now going back to the drawing given the two conditions if we just represent these points as nodes we can say that if an Euler tour exists then it is possible to draw the shape I mean just take the last graph you can think of the red dot as a pencil drawing it out we know it won't go over any line twice and it never will leave the page therefore you could draw this graph but in the drawing we have here the degree of these nodes is five because five edges leave them all and five is an odd number so when Oyler tour does not exist because all the nodes need an even degree but we aren't in the clear yet neither conditions said that we had to end where we started we can end wherever we want we just can't go over the same edge twice now this is called an Euler walk it's the same as an Euler tour but you can end wherever you want for example this graph has an Euler walk we can go over every edge just once and we don't end up where we started but that's totally fine I won't show why but you can prove fairly easily that even though an Euler tour needs every node to have an even degree and oil or walk will exist if and only if every node has an even degree or two nodes have an odd degree like here this node has an even degree but these two have odd degrees and since it's exactly two that have odd degrees the criteria for an Euler walk is met and now look back at our graph above remember four of these nodes have an odd degree therefore an Euler walk does not exist this means if you think of the red dot as a pencil we cannot go over every edge just once without repeating therefore we of course cannot draw the shape without going back over a line and that means this condition that is basically saying an Euler walk must exist cannot be met and that's why it's impossible to draw this shape given these two criteria then one more a quick graph theory example has to do with cycles and trees this graph right here has a cycle in fact it has multiple there's a way to start somewhere and trace some path where you end at the same place without repeating any nodes or edges this graph here has no cycles which means it's called a tree here's something you'll prove in class as a computer scientist or mathematician no matter what connected graph you have or how many cycles it has like this one above there's a way to remove certain edges such that you have a tree but don't lose any nodes they're all still there and everything is still connected this is called a spanning tree so imagine we have this graph where the nodes represent computers and the edges are long cables that connect them maybe for some reason there's an issue where this network is too expensive with maintaining all the cables maybe you want some way to keep all the computers connected but have the minimum amount of cables well now you know no matter how chaotic this looks like it could be every network in the world there's always a way to remove just the cables while keeping all the computers included and connected so if that information can still make it from one to another and you'll even get into weighted graphs where the edges come with weights maybe representing how expensive the cables are and you'll figure out how to find the minimum weight spanning tree so that the weights are the lowest hopefully you're seeing how big graph theory is and why it's so crucial the next topic I'll cover is number three which I will go over in part two

Channel: Zach Star

Views: 1,819,672

Keywords: majorprep, major prep, computer science, math, mathematics, math for computer science, how much math do computer scientists use, how much math is needed for computer science, math major, computer science major, graph theory, number theory, proofs, computer science math, college math, discrete math, how much math is in computer science

Id: eSFA1Fp8jcU

Length: 14min 53sec (893 seconds)

Published: Sat Apr 21 2018