Discrete Math

Key Takeaways

discrete math will help us build trauma hello world it's Suraj and if you're interested in coding not just machine learning but any kind of coding you need to understand discrete mathematics it's become a really important subject in the past few years because of how useful it is in computer science in fact pretty much every single computer science degree program contains at least one course on discrete mathematics sometimes to liberal arts majors it's okay breathe I'm here now in this video I'm gonna give you an overview of the foundational topics in discrete math to help you understand how it all works learn about each of them by necessity since we'll play the role of a cybersecurity agent working for mi6 our task is to crack a password-protected database of international criminals that's stored on a USB Drive discrete math isn't actually the name of a traditional branch of mathematics like calculus or linear algebra is its instead a description of a set of branches of math that all have in common one feature they're discrete rather than continuous discrete stands for individually separate and distinct while continuous stands for forming an unbroken whole without interruption discrete math deals in objects in discrete bundles like one or two kendrick lamar albums at least three if you're a real fan especially down in contrast continuous math deals with objects that vary continuously like three point four centimeters from a wall a good analogy would be digital watches versus analog watches the ones where the second hand loops around continuously without stopping basically discrete data is able to take on only integer values but continuous data can take on any value discrete math was created several decades ago as the mathematical language of computer science colleges learned that traditional math subjects did not cover the type of math needed by computer scientists so they put a bunch of math topics together and called it discrete math discrete math helps us design high speed networks and message routing paths perform web searches analyzed algorithms for efficiency and design cryptographic protocols that can do things like automatically block any image of Wilson as a genie beyond cringy before we can start cracking the password to get the data on the USB drive we've got to get to the lab and there are a lot of different paths we can take they drive there but we're on a deadline so we want to get to the lab as fast as possible meaning we want to take the shortest path to compute this we'll need to represent the collection of streets and intersections as a graph so that we can design an algorithm that will calculate the fastest way to get there since each street is two-way this is an undirected graph so there's no distinction between the two vertices associated with each edge this is graph theory the study of graphs and an important part of discrete math graphs are mathematical structures used to model relations between objects in our case intersections in graph theory the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized would be ideal the weights in our case would be the time it takes to drive from one vertex to the other here we can use one of the most famous algorithms in computer science Dijkstra's shortest path algorithm which is a five step procedure luckily we're not in LA even Dijkstra is no match for its traffic we start by marking our initial node which is our current location with the current distance of zero and the rest with infinity then we set the non visited node with the smallest current distance as the current node for each neighbor of our current node we add the current distance of the current node with the weight of the edge connecting it to the neighbor if it's smaller than the current distance of n we set it as a new current distance of n we then mark the current node as visited and if there are any non visited nodes left we repeat the process starting at the second step until we visited all the nodes thanks to a little Python script we can easily find the shortest path to the lab saving us a lot of time now that we've arrived at the lab let's plug this USB into the computer to see what we've got here in order to access the database we need a password and we have the password here but it's encrypted we need to figure out how to decrypt it into the actual password the only thing we know is that the length of the password is 6 characters long and it can contain either numbers alphab characters or both no emojis thankfully our first strategy here will be to see if we can write a script that will brute-force all possible combinations of every character a through Z and 1 through 9 but when we start running the script it starts taking quite a while in the meantime let's try and calculate how many combinations are possible here since there are 26 letters and 10 digits we have a total of 36 characters to choose from for each position if we start from the left we can fill in the first position 36 possible ways for each of the 36 possibilities for the first character there are 36 possibilities for the second character that means our 36 squared waste fill in the first two characters for each of the 36 squared ways to fill in the first two characters there are an additional 36 ways to fill in the third character so there are 36 cubed ways to fill in the first three characters notice the pattern here and know that number 69 is not involved here the total number of possible combinations is 36 to the n where n is the length of the character field which is 6 in our case making it over 2 billion possible combinations way too much to brute-force so we can go ahead and pause our script this is an example of common atour x the study of counting both has a means and an end in obtaining results and it's a part of discrete math we need to think of a smarter way to decode this password what if each of the characters in the string what's equivalent to a number and the actual password was solely numerical what could the mapping from characters and numbers be here maybe if we converted each character to its numerical position in the alphabet it would represent a prime number one that's X counts away from zero but if we try that out it doesn't work never may be the numerical version of it correlate to some sort of sequence here notice how I'm trying to categorize these integers into different numbered types based on their relationships the study of relationships between numbers is called number theory a part of discrete math there are odd numbers and even numbers square numbers Pythagorean triples the Fibonacci sequence number theory involves analyzing the mathematical relationships between numbers right now I'm trying to figure out the theory behind these numbers in particular maybe each letter of this text can actually be replaced by a letter some fixed number of positions down the alphabet the question then becomes how many positions let's write out a function for this one where we can call the function inside of itself for each character in the string we'll apply a shift operation and recursively call our function until we're done shifting the entire phrase recursion a part of discrete math is a way to solve a problem where the solution depends on solutions to smaller instances of the same problem if we google search the word recursion it recursively asks did you mean recursion which is a fun little easter egg from the programmers at Google in fact the internet is riddled with these a popular reddit threads top answer for the question what is recursion is a link to that very same post an example of recursion a recursive function is a function that calls itself until some base condition is true and the execution stops when we write out our recursive function we can try out different lengths of the possible shifts until we get one that works and it turns out that it's three shifts that was the password we just needed to shift the characters it turns out that this password was encrypted using what's called the Caesar cipher one of the simplest methods of encryption each letter of a given text is replaced by a letter some fixed number of positions down the alphabet for example with the shift of one a would be replaced by B B would become C and so on it's named after Julius Caesar who apparently use it to communicate with his officials is this ambition this is Bridgeland we now have the database of known criminals this is a sequel database and we'll want to compile a report for mi6 now that we've cracked it and that lists the top 10 most wealthy criminals by amount of money they donated to underground organizations in order to do that we'll write some sequel queries which will select the top 10 highest spenders from a certain section of the database relational databases like sequel are based almost entirely upon set theory a part of discrete math as is nothing more than an unordered collection of elements with absolutely no duplicates even the most complicated sequel statements are nothing more than operations on sets a sequel inner join is the intersection of two sets for example a Venn diagram is an easy way to explain the concept of sets two different sets have distinct values and where they intersect they have similar values unions disjunctions there are all sorts of terminologies related to sets and this is what set theory is all about we can write down the top ten criminals for our report but we have one more step here we need to create a proof for our report to show mi6 how we crack the code the rules of logic a part of discrete math specify the meaning of mathematical statements they help us understand and reason with statements like there exists an integer that is not the sum of two squares it's the basis of all mathematical reasoning and has practical applications in all of computer science one of the basic building blocks of logic are propositions a declarative sentence that is either true or false but not both like DC is the capital of the USA is true while DC is the capital of Mexico is false negations truth tables combinations conjunctions we can build off of the basic rules of logic to create all sorts of proofs so logically speaking we can define the proof of our algorithm with the following equation where the decrypted version of the text is equal to each character shifting n degrees out of 26 possible characters mi6 is going to be very pleased with this we'll probably get a double ho status now license code so those are some of the major concepts in discrete math I've listed them all in the video description as well as a free open-source textbook I found on the topic of discrete math study it there are three things to remember from this video discrete math is a set of branches of math that all have in common the feature that they are discrete rather than continuous discrete data can only take on integer values whereas continuous data can take on any value and discrete math topics like recursion logic and community oryx help define the basis of compute signs what's your favorite topic and Matt let me know in the comments section and please subscribe for more programming videos for now I've got to check my logic so thanks for watching