Algorithms in Python – Full Course for Beginners

Accumulated each row to end with six three one we then reassign our original row as the final row and return the very first element which will be six our answer to the number of paths now this isn't super necessary but it will give you an idea of the path traversal within a three by three matrix and will give us a good launch point to moving up to a matrix consisting of letters we'll keep it in the realm of just two letters a and b and we'll write a very quick little program to see how many palindromes of a and b there are let's import intertools to help us and then create our rows and columns of letters a neat little feature of inter tools is product with an asterisk on our matrix this will print out every combination of letters in our matrix totaling 27. yes there will be duplicates here but it's nothing that python's set can't handle let's create an empty list called p1 and then iterate over our list of 27 tuples join them together to make it easy on the eyes and append them to our empty list then all that's left to do is check which ones are palindromes by making a new function plugging in our p1 create another empty list p2 and then iterating over a non-duplicate set of p1 incorporate an if statement is it a palindrome yes put it in our empty list then return it okay so far we've traversed a matrix in order to count the number of paths in it we created a three by three matrix of just two letters found every possible combination and created a function to pull the palindromes from it we are doing fabulously

If you know how to count the paths of a matrix and find the palindromes in a matrix you're totally equipped to take on the palindromic paths problem let's get cracking so before we start i have to tell you there's going to be a little bit of a difference here for this program it's the order of traversal we're going to go from the top and right to the bottom not the bottom up and left to the top so keep that in mind as we march forward we're going to throw in our little palindrome checker up here first before we print them out at the end of our function hopefully by now you're familiar with that next we're going to create our main function with several parameters a string that will be empty but we're just going to call it string here a for our array our pointers that we'll call i and j our row and column that we'll call m and n now our conditional if statements are going to traverse the paths of our array we minus one from m and n because as you know this is python and we only need to iterate from indices starting at zero then one then two for our total size of rows and columns three by three see the i plus one and the j plus one within our recursive callbacks look at these slides to see the paths you could also print i and j within the conditional statements on your own to see it as well but when we add one to our pointers we're moving to the next element then once the traversal is completed it hits our else statement and that hits up our palindrome checker if it's true it'll print then it moves on to do the next reversal over and over until it's done and there you have it four palindrome strings in our matrix yay so what did we learn on our final lesson we learned about dynamic programming which is finding the optimal solution to sub problems that can be used to find the optimal solutions to the overall problem we saw this in our lesson with ugly numbers the traveling salesman problem and palindromic matrix paths in the easy lesson we learned about ugly numbers what they are and how to write a program to find the nth ugly number in the sequence avoiding brute force and recursion we were able to implement dynamic programming to optimize the solution from over one thousand iterations down to just a little over one we looked at the very famous traveling salesman problem with its main focus in optimizing a solution to finding the most efficient route a solution used across the board for so many companies in order to keep operational costs low and lastly we broke down the mind breaker lesson by studying unique paths in a matrix string palindromes within a matrix and combining those two problems together to find all the palindromic paths within a matrix are you excited i know that i am we covered so much ground in this course it's crazy hopefully you took lots of notes so you can practice later you should be coding something every day even if it's just for a couple minutes 10 to 15. since every little bit helps now listen to your mother thank you so much for joining me today and if you made it all the way here kudos to you i wish you all the best in your programming journey bye

"WEBVTTKind: captionsLanguage: enin this python algorithms course you will learn to work with recursion data structures greedy algorithms dynamic programming and more you don't need any previous experience and algorithms to follow along algorithms help us solve problems efficiently and employers pay good money for good problem solvers your instructor for this course is joy brock she has an amazing talent for breaking down complex topics using humor and visualizations hi can i ask you a question raise your hand if you love being bossed around i'm not seeing any hands i know that i don't like to be bossed around now you might be wondering why i would ask a question like that and what does that have to do with computer algorithms but that's just it computers love to be lost around in fact a computer can't do anything on its own without being told what to do and that my friends is what an algorithm is an algorithm is a specific set of instructions that we write to the computer to tell it what to do after all that's why you're here right to learn how to tell that old ball and chain who's boss you know the one that keeps us perpetually locked in a prison of screen time so without further ado welcome to the introduction to algorithms course i am so glad you're here we are going to have an insane amount of fun so grab your beverage of choice grab a notepad for notes and be prepared to learn the five basic algorithms that every programmer should know by official definition an algorithm can be defined as being the current term of choice for a problem solving procedure it is commonly used nowadays for the set of rules a machine especially a computer follows to achieve a particular goal it does not always apply to computer mediated activity however the term may is accurately be used for the steps followed in making a pizza or solving a rubik's cube as for computer powered data analysis algorithms are often paired with words specifying the activity for which a set of rules have been designed a search algorithm for example is a procedure that determines what kind of information is retrieved from a large mass of data an encryption algorithm is a set of rules by which information or messages are encoded so that unauthorized persons cannot read them this comes from the merriam-webster dictionary what does algorithm mean mathematically speaking algorithms have been around for nearly 900 years pretty amazing isn't it in fact algorithms are all around us every day and have been our whole lives in this course we're going to dive into algorithms that are finite or determine sequences of explicit instructions that are used to solve problems and or perform computations these computations are generally to perform calculations or to manipulate data using natural language processing natural language processing or nlp for short is what tells the computer how to comprehend and interpret written text it's important to distinguish the difference between using well-defined formal languages to calculate functions versus algorithms used in artificial intelligence or machine learning those algorithms are where automated deductions are made using mathematical and logical tests or where predictions are made based on patterns learned from experience for example the other day when i was looking at the front page of google on their news i thought you know this algorithm better be so good that i can read about the news before it even happens those types of algorithms are for another video on another day the objective here in this course is to give you the tools you'll need to undertake the journey of using a well-defined formal language in this case python to calculate functions within a defined amount of space and time that may be asked of you for interviews or tests in other words the goal is for you to be able to find differences in algorithmic approaches based on computational efficiency this means that how we write our program is very important in regards to how much space it can use up on our computer or how quickly it can run and it all begins with the foundational principles that every algorithm has in input well-defined instructions execution of those instructions step by step leading to an output that ends in termination of the program now there are many different algorithms that accomplish these basics when it comes to programming and as much as i love spending time with you all it would be so difficult to cover every single one so for the sake of brevity we'll be covering the following simple recursive algorithms algorithms within data structures divide and conquer greedy algorithms and last but certainly not least dynamic programming for this course you'll need some understanding of the python language like writing functions variables conditionals for loops and basic syntax an ide or integrated development environment an ide is the virtual place to write our programs now if you don't have a downloaded platform like pycharm jupiter notebook or visual studio code you can just use any online python ide through a google search if you would like to download your own personal ide such as pycharm vsc or jupiter you can definitely do that as each one of those platforms are free to install go ahead and pause the video now if you need to get situated otherwise let's get this party started enroll into our very first lesson on simple recursive algorithms in our first lesson we're going to learn what is recursion and we're going to examine three different problems ranging from easy to mind-breaking we're going to look at the differences in computational efficiency and see which approach is best is implementing recursion the best way let's find out if the easiest way to define recursion is to say it's where a function calls itself then what's the hard way to define it in all truth it's easy to throw a statement out hand on hip that goes oh it's a function that calls itself sure okay good for you but what does that really mean i think oftentimes when it comes to programming it's easy to take for granted this idea that we should automatically know what it all means i don't know about you but i wasn't born with the ability to comprehend various methods to solve problems let alone be able to decipher which which method is better in the first place you know we all need to learn these concepts layer upon layer step by step so let's start at the very first layer and build up from there now when we write our program recursively it's important to understand that this is in contrast to writing it iteratively or through iteration when we do that we're generally using for loops to iterate over an object instead of making a function call back within the program you'll see what i mean when we get into our ides and and start to write the code recursion is it originates from a latin verb that means to run back and this is what the program we're going to write together is going to do it will run back to itself over and over as many times as it needs until the program terminates so does this mean that we can't use for loops with recursion no of course you can use them in fact they will be needed and you'll see how that all works in just a moment in order to get started with our very first lesson involving factorials and the algorithmic method that we are going to use for better efficiency we will calculate the factorial of a number using the leaf method or last in first out and it all begins with a mental picture of a bookshelf that doesn't have any books on it yet to perform a lethal operation on your hypothetical bookshelf you will grab some books and begin placing them on the shelf let's say you ordered some britannica encyclopedias wait why would you do that why did any of us do that oh right it was our grandparents that saw to it to make sure that we had our own modern day google machine thanks grandma your legacy lives on at the donation center okay that was a wonderful trip down memory lane wasn't it okay so back to lefo or lifo if that's what you call it so you put your encyclopedias on the shelf a to z in a last in first out scenario what was the last book you you sat on the shelf z what's the first book that's going to come off z so last in first out and this would be important to remember in our number oriented recursive function coming up that the last number that goes in will be the first number that gets called out or computed now if you're a little bit confused it's okay you won't be for long we're going to see this in action right now and talk about the computationally efficient way to solve as we write our first recursive program to calculate the factorial of a number for a quick recap on factorials say you take the number 5 and multiply it by itself minus 1 all the way down until you hit one your answer will equal 120. remember factorials only involve positive integers so once you hit one the program terminates now let's get to work we're going to look at two ways that we can write a program that will calculate the factorial of a number this is going to be a wonderful foray into differences regarding complexity and program efficiency in our first method we're going to tackle this iteratively or like i mentioned before through iteration this means that our program will cycle through or iterate each and every step we tell it to first we define our function with one parameter the number we want to calculate in this case we'll just call it n then we're going to create a variable and start it at one positive numbers remember no zeros here next we construct a for loop to iterate over that variable or object if you like and do something to it in this case we're going to multiply it by every number in a range starting at 2 and adding in our ending at our number plus one this gives us a range of four numbers two three four five now why not six since n or five plus one equals six remember we're using python so if we loop to a range of two comma 6 in parenthesis our indices will always be minus 1 because python starts at 0. so an index position of 6 will give us our last number for our calculation 5. then we take our object called fact and multiply it by every number in our range because we can use the asterisk and equal sign to condense our code a little fact equals fact time asterisk i that assignment operator is reassigning our variable each time it cycles through our loop when the cycling or iteration is finished we simply return our finished fact variable if you want to see the results of each iteration you can just place a print statement within the for loop and run the program for a recursive method it's going to be already typed out while i talk this is where our last in first out comes into play remember when we talked about that this is in contrast to our iterative method that starts at the top are fact variables starting at 1 and then iterates through our range going up until our number is reached in the algorithmic method of recursion when we go to call the function if our number isn't 1 it moves to our else statement where in our else statement we have a temp variable that runs back to our function call and creates a pocket of space if you will for each number minus one it will run back all the way down until it hits one our last n if you will once that happens the return statement and our else statement starts working its magic and then we start heading back up our last in which was one becomes our first out our first number to get computed ta-da now you might be tempted to think that the recursive method is top dog here but alas you'd be wrong our iterative method is twice as fast for what we're trying to accomplish which is just a basic calculation of a factorial what's important what's important to be able to understand is a how recursion works by using a simple program such as momentous did and b how how and why one approach can be better than another in this case recursion is taking up more space and time by running back to the function call to create those pockets for our numbers versus iteration where it's simply multiplying each number in place and not creating anything new it's simply iterating over each number reassigning our variable each time and producing a final output the objective for our basic exercise is to just understand and see recursive algorithms in action so that as you gain experience you'll be able to exercise different modes of expression or expressivity in your writing and in some cases use your readability check out this example on the upside being able to write code in three lines instead of seven or eight can be a huge deal depending on the circumstance however on the flip side may decrease the performance of the code let's like this example that we just coded together it's just not as efficient as iteration in this case so if you're ready let's move up to a more advanced recursive algorithm involving permutations a permutation is when you take a set of elements and find all the different variations that can be made with it for instance if we take a b and c we can get six variations out of these three letters mathematically speaking we can find the number of variations by calculating the factorial of the elements just like we did a few minutes ago for a hands-on approach to understanding a level up on recursion let's take a peek under the hood and see how this will work in a program shelby the underlying basis of how most functions for permutations work is to take off the first element and then create two subsets of numbers that get swapped like this then the original first element gets put back onto the front of each subset then we do this all over again this time instead of popping out the first element we pop out the second one and create two new subsets and so on and so forth the algorithm behind permutations can really make your head spin so take a deep breath find your center and jump in to a puddle let's not jump into the ocean just yet it's good to start small and by small let's recursively swap just two letters of a string this is a little bit harder to do than a list because strings are immutable but this is a good launch point for us to build up from here also we'll start with recursion this time and then afterwards we'll look at a different method for comparison to write a recursive function that will swap just two letters we will need to create a pocket for where our strings need to go remember again strings are immutable and if this were a list we could simply slice it and create a variable swap but that's a no go for strings we're moving into a little bit steeper territory here but stay with me okay you can do this let's create our function and call it permute with two parameters one called string and for the string of two letters that we want to swap and an empty pocket to put our new string in this is our parameter default defaulted to an empty string then we create an if statement for an edge case in the event that the string is empty and if it's empty we just return our empty pocket now we'll start with looping through the range of the length of our string and within our loop we'll start with creating three variables that will contain one each letter on our string two we'll need to take off the front of the string that we're going to call front and then three a variable called back that will slice off the back of our string if you study this algorithm you'll see some programmers call it head and tail current and the rust first next or front and back i like the terms front and back as it gives me a better mental picture but you can use whatever terms you're more comfortable with now those first three variables are fairly obvious but this is where it might get a little hazy we need to create a fourth variable that will put our front and back together and we'll need this variable of combined elements to plug into our function call this is what creates spaces to in our pocket to be able to move our letters around i know this may sound a little complicated at the moment but you'll see shortly that we're going to need each and every letter of our string even however many that will eventually come to be to have the space it needs to go into the right place in our pocket now whether that's going to lead up to eventually being three letters or four keep in mind our strengths can't be too long because of two things the rate of exponential growth and the fact that recursion can get exhaustive very fast the more letters you have recursively that's a lot of running back okay we have all the variables we need right now our letter a front which is just an empty string right now our back which is the last set of our string b and are together that combines our front and back now for our algorithm this is where the magic happens this is the true ham in our sandwich we call our function premium and then incorporate two parameters are together and our letter added to our pocket hence the addition operator this is the heartbeat of our algorithm it needs to run back and put our letters into our pocket once in reverse and then the second time in a copy of its original form because it's still considered a permutation watch how this works in the visualizer i think that if you get really get a really good handle on this concept and you have a solid foundation it becomes so much easier to see how this works with additional letters if you can see it mentally this makes all the difference in the world it's a neat little program that only has 11 lines of code which is really nice however this program isn't as efficient as a program that uses iteration and swapping again that program has nearly double the lines of code i'll spare you the direction of watching me type it all out and just show you here this would be the code that executes just like the beginning that you saw on the earlier slides where it pops off the first letter and then swaps the it pops out the first letter swaps the last two and then pops the first letter back on then it rotates to the second letter swaps those two and then puts it back on check the output here and you'll see what i mean now if you needed to know all the permutations of a string and don't really have time to write the code or the patience you could use the inner tools permutations module it's really easy but that would be primarily for you just to know for yourself or for a quick look up when it comes to interviews or testing companies would generally prefer that you know the mechanics behind the method for solving whether that's using recursion or swapping as with any program the caveat must always be made can this program be written differently as always yes however you will see very little difference when it comes to recursion of most programs like this very generally speaking they will call the function in a very similar way as it is written here by taking the front and back together and incorporating it in some way within the function call along with the letter hopefully you were able to distinctly see how recursion works in this program even just for two letters it can work great on small strings but it will get computationally expensive the longer the string now if you're not too overwhelmed hopefully not we've only done two we're going to move into the mind breaker section like it should be the mind blowing section the end cleans problem this computational problem is about placing eight chess queens on an eight by eight board so that no two queens are able to attack each other according to wikipedia the problem finding all solutions to the eight queens problem can be quite computationally expensive there are 4 billion possible arrangements of the 8 queens on an 8x8 board but only 92 solutions wikipedia also goes on to say that the use of shortcuts and various rules of thumb that avoid brute force techniques can greatly reduce the number of possible combinations which i'm sure is always a good thing but what is brute force though well that's would be brute force would be looking at every single possible arrangement 4 billion of them to find the 92 solutions how long do you think that would take probably take decades for our computers to run a program like that but guess what the use of permutations can reduce the possibilities from 4 billion down to just 40 000. that's a big reduction now we're not are we going to use permutations on the end queen's problem today no way jose but it's good to know that this problem is often used in examples for various programming techniques such as solving it by using recursive algorithms it's also used as an example in constraint programming which is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence computer science and operations research to get a better idea of what that would be we can use a real world example like employee scheduling say for instance a company operates continuously like a factory they need to create weekly schedules for their employees and if that company runs three eight hour shifts per day in a science three of its four employees different shifts each day while giving a fourth one's a day off even in such a small case like that the number of possible schedules is huge each day there are factorially 24 possible employee assignments for four people so the number of possible weekly schedules is 247 which calculates over 4.5 billion constraint programming methods keep track of which solutions remain feasible and makes it a powerful tool for solving real world scheduling problems who knew queens on a chessboard combined with computer programming could help solve real world problems like that so what did we learn in our very first lesson in our algorithms course we learned simple recursion and saw it in action that when a function calls itself it creates new spaces to store information and sometimes this may not be an efficient solution to a problem it's definitely more elegant with fewer lines of code that can come in handy depending on the problem but it's not always cost effective but it is important to see and understand the difference factorials and permutations are used in a lot of computational mathematical and real world applications learning how to write programs rather recursively or iteratively to find the best method in this area can go a long way and may lead to unknown opportunities for you down the road as a programmer we learned about constraint programming where recursion plays a role for solving mind-bending problems not only within board games such as chess but real life issues that companies can face as a programmer that works to gain the tools needed to understand these types of methods to solve problems can make them a valuable asset to any company welcome to level two working with data that is structured i like to think of data structures like something that holds money say for instance you have on your person a big wad of cash consisting of a lot of different bills what could you do with it well you could store it sort it search it add it spend it delete it count it so with data structures they're simply containers or collections of data they provide a means of managing small or large amounts of values for uses and such things like databases web traffic monitoring user registrations and or indexing within a contiguous memory location like an array they can range from as simple as lists to linked lists stacks cues hash tables trees and heaps these are all examples of data structures and since algorithms are steps to solving problems what kind of problem-solving techniques are common with data structures well just like watts of cache data often needs storage sorting counting retrieving searching spending all those fun things now arrays can be a really basic container for information but don't let that fool you many different algorithms can be used on one-dimensional arrays but what about two-dimensional arrays what about 32 dimensions since that's the maximum amount can you imagine arrays are among the oldest and most important data structures and are used for almost every program for a basic level of algorithms with data structures we'll go easy and stick to a linear or one-dimensional array a one-dimensional array is just an array stored in an unbroken block of memory to access the next value in an array we just move sequentially to the next memory address it's best to see this visually so check these slides out for a better idea in our basic section we're going to cover linear search binary search bubble sort and insertion sort we'll be covering a little bit more for the basic level on data structures because it's a really big topic actually entire books are written about them let alone design techniques and algorithms i'll do my best not to put you to sleep hopefully it'll be enough to watch your appetite where array is our concern as this is a huge topic as well and as much as python is a wonderful program with tons of features like built-ins and libraries and modules that can help programmers code faster it's still really important to understand how these features work algorithmically and the concepts underneath it all let's get started a linear search could be equated to pulling that a lot of cash out of your wallet wait does anyone carry cash anymore no okay well let's pretend that you have a wallet full of really big bills i mean go big or go home right and you need a 500 bill from your stack why well you're at the mall of course and you want to buy that really cool pair of socks that you saw in the window and you might be thinking 500 for a pair of socks and i would say yup that's inflation for you but this is a fantasy remember besides inflation slomation you got a wallet full of big bills and in this fantasy let's go for a big ticket item well maybe not sucks but maybe a t-shirt in a linear or sequential search we could technically transpose transposo those terms you would have to go through each bill to find that 500 same with an array of say six random integers if we were wanting to find the eight we we would have to manually check each element in order to return the position of the eight algorithmically it would look like this and can you imagine if we had an array containing a large amount of numbers it would be very very time consuming and inefficient to use a linear search because it would be comparing each integer one by one now can it be used for searching sure but it's only when the numbers are relatively few and relatively sorted but hey let's code this out anyway we'll define our function with two parameters our array and the element that we're searching for then we'll write a for loop to iterate over the length of our array and if there is an element there that's the same as our element then just return where it is in the array when we print it out we get index position 4 as that is where our 10 is a more efficient way to search is to move up to a binary search and the clue is in the name binary as in by meaning something that has two parts in this search algorithm we would create two pointers and repeatedly divide the search interval by half naturally this would reduce our search space so that we're not searching the whole array but only the divided parts the catches at the binary search is that it is usually mostly generally done on sorted arrays that looks like this and this way the algorithm checks whether the middle element is equal to the target that we're searching for in every iteration if the target value matches the element then its position in the array is returned if the if the target value is less than the element the search continues in the lower half of the array the target value is greater than it searches in the upper half of the array ultimately the algorithm doesn't need to search the half our target isn't in with each iteration now let's look at some code because our program is only searching half the array it makes it a much better search let's look at the iterative method first in our function we can create four parameters our array a start point an endpoint and the target that we're searching for we'll create a while loop to iterate over our array from start to end and then create our midpoint our variable called mid is the magic in the sauce we only want to traverse the half that contains our element feel free to print out the mid when you run the whole program for yourself to get a good idea of this next we can implement our if statements we'll only need three check if our target is in the upper half then reassign our start to begin moving to the right of the array if our target is lower than our mid we reassign our end to begin moving to the left of the array if our target matches our mid then just return it easy peasy then we just return our start or we can return something like negative one to print out some strings to make it a little fancy but either way you prefer to have your results printed we have to be sure to declare our start and end in the function call our start is zero from the beginning of the array and our end is the last element our length of array minus one for our recursive function i won't spend a lot of time here because the difference between our iterative program and the recursive program is very minimal runtime and memory space is very very close meaning they're both really efficient either way it's good to see both programs basically all we're doing is just calling back to the original function within our else statements feel free to pause the video for a moment and take a closer look okay now that we have some super basic searches under our belt let's move into a deeper section of sorting because well sorting is fun who doesn't like to sort money piles of 50s here piles of honey is there holy crap i sound like mr krabs all right all right let's mix the money references let's get to sorting our boring old elements as for sorting there are a vast array of techniques that are available and here's a little quick list actually it's not that quick as there are many to choose from bubble sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order for instance the largest integer bubbles up to the top or iterates its way to the end of the array through a comparison of each element although this isn't a very efficient algorithm perhaps the worst it's still an important concept to understand the only real perk the bubble sort has compared to other algorithms is its built-in ability to detect whether or not an array is sorted in the first place in a best case scenario the list is already sorted or nearly sorted and this is in contrast to other algorithms even those with better than average performance whose entire sorting process caused more causes more inversions reversals reversals or swaps to happen an optimized algorithm for the bubble sort is to find the nth largest element and put it at the end of the array there is an unoptimized version that you can check out for comparison purposes if you want to look that up on your own you're more than welcome to do that but the optimized version is done so that the inner loop can avoid having to look all the way at the end when it's running the last iteration it's just saving time and energy by not having to do that although bubble sort is one of the simplest sorting algorithms to understand and implement its performance means that it's that its efficiency decreases dramatically on arrays of larger amounts of elements and it's even been argued that it shouldn't even be taught anymore as it's outdated and is even hazardous to some cpus yikes i bet you didn't realize that you'd be entering dangerous territory here i mean who knew conan could be fraught with such tenuous escapades such as this how sexy let's code it our function will take just one parameter our array and then i implemented an iteration count just for informational purposes next we create a for loop to iterate over our indices in the array going to the right combined with a nested loop inside that iterates over our indices going left or reverse that we're going to call j i strongly encourage you to write this program for yourself and within our nested loop print out j just to see it in action we have our iteration counter when this prints you'll see why i added this now we just tell it to swap elements if they are lower than the one to the left in our if statement if our element to the left is greater then swap it then we just return our newly sorted array so let's print this so you can see our iteration count with 36 iterations that's pretty efficient check this out now i know i said that it wasn't going to look at the unoptimized but guys check this out double the iterations for two functions and it's double the code i liked our first program simple shorter faster unstable oh that was dangerous i kind of like it but hey if dangerous not your thing you thrive in a more stable and secure environment that's fine too we can totally move on to the insertion sort algorithm insertion sort is another simple sorting algorithm that builds the final array one item at a time it's still inefficient on large lists like the bubble sore but it can have some advantages such as simple implementation meaning a reduced amount of code and performs well in small data sets and relatively sorted arrays and it doesn't require much space meaning that it can be done in place therefore not using much computer memory in order to perform well the concept of the insertion sort is to split the array into two sections in order to compare its elements we can consider one side sorted and the other side unsorted our algorithm takes one element at a time from the unsorted side and compares it to our elements on the sorted side if our element is larger or smaller it places it where it needs to be on our sorted side each generation takes an element from the unsorted side and places it into our sorted side all the way till there are no more elements to compare to and in the end we are left with a sorted array for our program our parameter in our function call will be our array starting with a for loop that will iterate starting at our second element we don't need to start at our first integer because that's our sorted side we leave that alone for now we create two variables our key which is our current element and a pointer to the left of our key we'll implement a while loop to iterate as long as our index is greater or equal to zero and our index is greater than our key we then program it to reassign the larger one to the right position and then move down and put our small element to the left we do this all in place without creating extra space it's fairly simple and straight to the point working with arrays can last for days you like that no but seriously what we've touched on is only the tip of the iceberg as a personal challenge to yourself try searching and sorting a two-dimensional array are you up to the challenge for our advanced level algorithm section we're going to dive into linked lists a linked list is a linear data structure in which the elements are are not stored at contiguous memory locations remember this picture also remember that arrays are stored at contiguous memory locations a wikipedia definition states a linked list is a linear collection of data elements whose order is not given by their physical placement in memory instead each element points to the next it's a data structure consisting of a collection of nodes which together represent a sequence in its most basic form each node contains data and a reference in other words a link to the next node in the sequence this structure allows for efficient insertion or removal of elements from any position in the sequence during iteration more complex variants and additional links allowing more efficient insertion or removal of nodes at arbitrary positions a drawback of linked lists is that access time is linear and difficult to pipeline some say that linked lists are among the simplest and most common data structures are they though as an example think of a photo storage website if you click on the website landing page this would be considered your header then when you click on the first image this would become a node the arrow next to it that you can click to see the next picture would be your pointer now if you get to the third or fourth picture and want to go back to the first picture and look at that again those back arrows would mean that you're on a doubly linked list a doubly linked list means that you can traverse the list forward and backward however for this lesson we're only going to cover a list that we can go forward on the singly linked list now the upside of a linked list over a conventional array is that the list elements can be easily inserted or removed without re allocation or reorganization of the entire structure because the data items do not need to be stored contiguously linked lists allow insertion and removal of nodes at any point in the list and they keep up with a constant number of operations by storing the link previous to any link being added or removed during a list traversal so let's talk about our four basic algorithms or common problem solving operations for singly linked lists every programmer needs to be able to do the following traverse a linked list or be able to travel along the nodes and pointers search a list for the header a node or tail a tail is the last and final node insert a new header note or tail and to delete a note or tail a link to list generally always needs a header let's create a simple linked list representing a small family member group we want to be able to do all the operations mentioned above this will require a little bit of object oriented programming so hopefully you are somewhat familiar with that but if not that's okay we'll stay simple and make it easy peasy we need our pretty standard class node and class linked list to start our nodes will be our family members and our linked list will represent our whole family this can be considered a little backwards but i like to instantiate our objects first so it's easier to see what we're dealing with being able to visualize what we're doing is an important skill in programming and design because it helps us think about the big picture throughout the solution let's picture our knowns as a family of mom dad and two kids we'll create our family head as bob his wife amy our header will point to amy as the next node and then our two little nodes max and jenny they all need to point to each other as they will be linked together in our list so we will make sure our pointers are created which is object.next everything looks good and we have all our members individually as nodes but to really see our algorithm in action we need to link all our members together in our linked list where we can operate on that list and design them to be really complex or really simple linked list problems are often used as interview and exam questions so knowing how to create linked lists how to traverse them how to add and take away elements is very important once you get really familiar with those concepts you can move into learn learning how to traverse how to reverse a list swap elements maybe even go on to doubly linked lists or circular it's a really big topic to explore and fun too and if you're not having fun why are why are you here like why so back to our family let's get them created and then set it up to where we can traverse this family list once we have established our class we just need to implement our functions that tell our linked list class what to do this is where we implement all the things we need done with our nodes and the first thing we're going to do is make our nodes by creating the data and a pointer let's create our objects then create pointers that go to each family member now that we have our nodes we can now link them in a list by creating our linked list class this is where we create a function to traverse our nodes in a list and be able to print them all out we only need one argument self because it doesn't need any other value or input to be to be able to do what we need which is starting at our header and printing them all out next by next by nuts then we just call family.traversal and out pops our family members now if you want to shoot these out in a particular way such as in a list or fancy strings that would have to be done within another function in the linked list class which unfortunately is not within the scope of this course that's more in tune with object oriented programming a whole other separate topic the goal here is to focus on being able to operate or solve problems to creating simple function calls on linked lists now our family member list is looking pretty good but word on the street is that bob isn't treating amy too well and he's been running around on her from the looks of it bob might be packing his bags and leaving the family but it's not all bad because dave has been hanging around a bit and although he's bob's brother he's a really good guy i know i know it sounds really back once but seriously dave is going to step up to the plate and he's looking forward to being a dunkle to the kids you know you know a dunkle like when your uncle becomes your dad and it's not weird at all so for our list we need to put dave as the new header position and because this is a computer and it can't do anything that we don't tell it to do we need to implement some functions let's call it insert new header and this is going to fall under our insertion algorithm we need to know how to insert elements into the list and not only that we have to tell it where to insert for davis the new head we are going to put him at the front of the list so for our function apart from self we need new data or information to be added to the parameter since we are adding a new name our new name is our new node so we will need our node class remember the nodes are our family members then all we need to do is assign him as the next new node to the self.head and then assign yourself.head to the new node let's traverse the list now oh boy bob is still in the picture and you know what amy can't have her new hubby under the same roof as her ex that is just not gonna work this is a little two backwoods so bob needs to go go creating our new header simply pushed all our nodes down so we need to get bob out of there let's create a function that deletes a node however we can't just delete some rando node we have to tell our computer where bob the node is in the first place this means we have to search our family list so let's create a search search function with one parameter x see what i did there pretty clever we need to know if bob is even in there to delete so in order to search we need to start at the beginning of the list let's create a temp variable assigned to the self.head and make a while loop that will traverse as long as that list or header isn't empty if any node or temp node isn't equal to x or whatever it is we're searching for we want to return true or else return false then we need to assign our temp to the next node because in a while loop it will need to continue until the node is not is none then it will return our pool great let's find out if bob is in there by printing our search function uh oh it's true bob's still there and he's giving amy a hard time about leaving let's help her out and create a delete function this is going to be similar to our other functions where we need to put our data in the parameter and begin at the head of our list we need our if else statements and we will and we will say bob isn't there then tell us and if he is let's kick him out we do this by changing the pointers from the previous node and pointing it to the node after bob so in essence we're skipping over bob but watch what happens when we try to try to delete amy bob will come back why does this happen because our list has four nodes as created here and those nodes will always be there unless we go in and manually delete the object itself so far we've traversed our list searched our list inserted a new header deleted a node and last but not least we're going to delete our tail yep that would be poor jenny she's had enough of these adult shenanigans and she's out of here heading to new york to become the greatest fashion editor that vogue has ever known she's ambitious okay we started the head and as long as the temp dot next next is not none our pointer is two nodes ahead we make our temp the next node and set it to none voila best of luck jenny so there you have it some very basic foundational algorithms for linked lists which in itself is a complicated subject but if you get these classical concepts down solid it becomes easier and easier to build up from on your own once you're more comfortable with singly linked lists try to challenge yourself with doubly linked lists with pointers that point back who knows maybe bob will shape up and amy will go or point get it back to bob for our mind breakers section in data structures we're going to be looking at hash tables right off the rib i'm going to tell you the key phrases or terms you need to be familiar with when it comes to hash tables associative arrays hash functions key value pairs collision and chaining a hash table consists of an array of pockets or buckets where each stores a key value pair in order to locate the pocket where a key value pair should be stored the key is passed through a hashing function this function returns an integer which is used as the pairs index in the array of buckets when we want to retrieve a key value pair we supply the key to the same hashing function receive its index and use the index to find it in the array associative arrays can be implemented with many different underlying data structures and it refers to an array with strings as an index rather than storing element values in a strict linear index order this stores them in combination with key values multiple indices are used to access values in a multi-dimensional array which contains one or more arrays a non-performant one can be implemented by simply storing items in an array and iterating through the array when searching remember the wallet with lots of cash associative arrays and hash tables are often confused because associative arrays are so often implemented as hash tables according to wikipedia a hash table uses a hash function to compute an index also called a hash code into arrays of buckets or slots from which the desired value can be found during lookup the key is hashed and the resulting hash indicates where the corresponding value is stored in many situations hash tables turn out to be on average more efficient than search trees or any other table lookup structure for this reason they are widely used in many kinds of computer software particularly for associative arrays database indexes caches and sets to summarize we can use hash tables to store retrieve and delete data uniquely based on their unique key the most valuable aspect of a hash table over other abstract data structures is its speed to perform insertion deletion and search operations hash tables can do all of them in constant time for those unfamiliar with time complexity big o notation constant time is the fastest possible time complexity hash tables can perform nearly all methods except list very fast in o b o one time hash tables have to support three functions insert for key value get key or delete a key collision happens when there could possibly be two or more pieces of data in data set x that will hash to the same integer and data set y this means that whenever two keys have the same hash value it's considered a collision what should our hash table do if it just wrote the data into the location anyway we would be losing the object that is already stored under a different key ideally we want our hash values to be evenly distributed among our buckets as possible to take full advantage of each bucket and avoid collisions but generally speaking this is unlikely so this is where two common methods to solve are employed separate chaining using linked lists or binary search trees for example and local addressing using linear probing with some basic concepts of hash tables under your belt a fun exercise or challenge that you can try would be pattern matching on strings using the robin carp algorithm yes it's fairly advanced and yes this is our mind breaker problem but shoot for the stars people who knows you might just surprise yourself what have we learned what have we learned from lesson two okay we touched on a one-dimensional raise as our data structure of choice at our basic level we looked at contiguous versus non-contiguous different ways to search linear binary and we sort bubble insert and even talked about an array with more than one dimension we learned about dunkles no no no no we learned about link list by creating a family of sorts to demonstrate how to traverse search add and delete headers nodes tails on linked lists some of the most common operations used that every programmer should be familiar with we broke our heads on hash tables and hashing functions by going over what they are and what can happen when problems arise from colliding data within a bucket ultimately hash tables are for storing retrieving and deleting data based on key value pairs and on average are more efficient than search trees or any other table lookup structure i learned about the divide and conquer concept from a very early age it was traumatizing actually you see my brother and i used to fight all the time when we'd swim in the pool and finally one day our mom came and said to us just divide it in half and you stand once and you stay on another side my brother picked the top half so yeah divide and conquer i drowned but only momentarily in programming when we cross paths with programs that are too complicated to be solved all at once we can implement methods to break them down into smaller pieces and if we solve all the smaller pieces we are in essence dividing out the big solving the small and in the end this makes our lives so much easier a divide and conquer algorithm paradigm can solve a large problem by recursively breaking it down into smaller sub-problems until they become simple enough to be solved directly it could be compared to the age-old problem of swallowing an elephant can't do that so we devour it one bite at a time actually it's more of a solution of three bytes dividing solving and then merging it all back together unfortunately since divide and conquer algorithms are usually implemented recursively this means they require additional memory allocation and without sufficient memory a stack overflow error can or will occur this is due to the overhead of the repeated subroutine calls along with storing the call stack the state of each point in the recursion and that can outweigh advantages of any approach on the flip side if the dnc solutions are implemented by a non-recursive algorithm that stores the partial sub problems in some explicit data structure like a stack queue or priority queue it can allow more freedom in the choice of the sub-problem that is to be solved next a feature that is important in some applications including breath first recursion and the branch and brown branch and bound method for function optimization second even if a solution to the full problem is already known like sorting a brute force comparison of all elements with one another divide and conquer can substantially reduce computational cost lower cost means higher efficiency third explicitly recursive subdivision can have benefits to the temporary memory of the computer not the main hard drive which is called a cache using divide and conquer one can even design an algorithm to use all levels of the cache hierarchy in such a way as to have an algorithm that is optimally cached oblivious which means operating independently from its temporary memory storage this approach has been successfully applied to many problems including matrix multiplication which we're going to get into in just a few minutes so let's get into it and start at the base level algorithm for divide and conquer the merge sort conceptually merge sort works as follows divide the unsorted list into two sub lists about half the size sort each of the two sub lists merge the two sorted sublists back into one sorted list invented by john von neumann in 1945 the merger sort is an efficient general all-purpose and comparison-based sorting algorithm an example of merge sort would be to first divide the list into the smallest unit one element this becomes a list itself then compare each element which is a list itself remember with the adjacent list to sort and merge them done repetitively the end results in the elements sorted and merged i understand that can be a little bit confusing but let's think of it in this way say we have two different lists of numbers list a and list b and then we'll have an empty list we'll call c lists a and b are ordered from least to greatest and what we would do is repeatedly compare least value min of a to the least value min of b and remove the lesser value and then append that value into c when one list is exhausted we append the the remaining items into c they're already started so we're good there then we just return list c which is sorted we're systematically merging a and b together and appending it into c but for this lesson and although you can append or extend on an empty list to see we're going to swap our elements i just wanted to share a very simplistic explanation for that hoping that would give you an idea of the concept typically creating more space for an empty list or temporary list for storage isn't always the best approach we want we want to do our best to optimize our program if we can let's head into our ides and write our programs the best way to see the different methods of the merge store and their efficiencies is to compare four programs that i have here some things i wrote myself some things i borrowed we're going to look at a single array of 10 integers and just sort it by brute force this means that the program takes the first number in index position 0 and compares it to each and every number in the array if it's the lowest it gets reassigned at the first position then it moves to the next number and does the same thing it gets compared to each and every integer and the lowest number gets reassigned at index position one and so on and so forth for this little iterative program it's 168 iterations or cycles to get an output and that's just for 10 elements keep that in mind as we look at the differences within the merge sort our first real program for the merge sort is about as simple as we can get it we're starting with an array that is already split in half and sorted the program we're looking at right now won't work properly if our two halves are not already sorted why because ultimately this is our divide and conquer algorithm we are dividing our array into two parts and conquering both halves separately by sorting them and then merging them back together remember just a few minutes ago when we talked about list a list b and empty list c this program is comparing each number at each index position determining which is lower and then popping it out and then appending it into our empty list c and then just in case either list is longer than the other that leftover portion just gets added to c and since it's already sorted we'll have no problems there this is a neat little non-recursive merge sort for an array that has a small amount of elements and is already divided in half however since this isn't a perfect world and you'll be more than likely asked to write a program for an array that isn't divided and sorted beforehand we're going to have to rewrite this so here's our big dilemma do we sort our halves recursively or do we sort them iteratively or do we sort our halves using python's built-in feature called sort or sorted let's shoot for sorting our halves recursively this is what is called the top-down method what it does is repeatedly produce sub-lists half by half by half until there's only one sub-list or one element remaining which becomes a list all in itself a list of one element how many of you are willing to but it's the optimal or optimized method well it's not once we have our have sorted we continue on very much like before we compare each element and append it into our empty list now if recursion isn't the optimal method then it must be iteration right well yes mostly this is the bottom up method think of the top down just in reverse it starts at one element then two elements then four remember that very first brute force method of sorting a list we can do that after we divide the array into two parts and then merge it all back together hmm let's see what happens when we run it in something like leeco that'll really put it to the test okay well that didn't go as planned but it does work it's just bad on really big arrays so what is the bust using python's awesome sort or sorted feature of course well splitter array have python sorted for us and the rest is good to go with our 10 element array it's only 34 steps to completion compare that to our brute force program no dividing no conquering with almost 170 iterations our bottom up iterative method is smoking check it in leak code talk about optimization now let's move out into deeper waters with some matrix multiplication matrix multiplication is wild y'all but it is a fundamental concept to understanding computing among the most common tools in electrical engineering and computer science are rectangular grids of numbers known as matrices the numbers in a matrix can represent data and they can also represent mathematical equations in many time sensitive engineering applications multiplying matrices can give a quick but good approximations of much more complicated calculations did you know that one of the areas of computer science in which matrix multiplication is particularly useful is graphics it's crazy to think that a digital image is basically a matrix with rows and columns of another matrix corresponding to rows and columns of pixels and the numerical entries correspond to a pixel color value decoding digital video for instance requires matrix multiplication and did you know that mit researchers were able to build one of the first tips to implement a high efficiency video coding standard for ultra high definition tvs partly because of patterns they discerned in the matrices pretty cool huh so the dimensions are listed as rows and columns or in many equations n times m where n represents the number of rows and n represents the number of columns be careful that you that you know the difference between rows and columns and don't mix them up rows go across columns go up and down to see how matrices are multiplied check out this graphic that shows how it all works we multiply each element in the row by each element in the column and then we add them together in order to code this we'll start with the naive method it's not too bad to learn however just know that it can get very expensive as we increase the size of our matrices for larger matrix operations we wouldn't want to use too many nested loops because it could really start bogging down ideally we would want to use optimized software packages like numpy numpy should be the go-to which is insanely faster and easy too but before we start cheating we really need to examine what's going on underneath the hood like how a program is created that multiplies matrices in python because if we can get a really good handle on this we'll get a better handle on the mind breaker okay so what we're doing is basically creating a calculator in python that multiplies matrices and you might be wondering hey what's the deal here how is this part of dividing and conquering algorithms we're definitely going to get into that but this is all preparation for the mind breaker lesson you'll need this under your belt first plus it's a really good foray into matrices which is one of the most well studied problems in numerical computing today so yeah let's dig in we'll create two matrices x and y and to store the results of our products we'll create an empty matrix we'll call result the most popular method in my humble opinion is to use nested loops to iterate over the rows and columns and implement the results into our matrix of zeros using an addition operator that adds our product of the rows and the columns of x and y we could do this recursively sure but it wouldn't really be advantageous the goal is to help you understand the logic behind matrix multiplication so we can move on to our mind breaker lesson strassen's algorithm for matrix multiplication volker strassen is a german mathematician who made important contributions to the analysis of algorithms and has received many awards over his lifetime he's still alive by the way he began his research as a probabilist his 1964 paper an invariance principle for the law of the iterated logarithm defined a functional form of the law of the iterated logarithm showing a form of scale scale and variance in random walks this result now known as strassen's environments principle or strassen's law of the iterated logarithm has been highly cited and led to the 1966 presentation at the international congress of mathematicians now if you know what an iterative logarithm is that shows a form of scale and variance in random walks or in variance principles in general well then please by all means invite us to your latest book site but if you're a mere mortal like the rest of us hold on to your hats because that was only the beginning for strassen three years later strassen shifted his research efforts toward the analysis of algorithms with a paper on the gaussian elimination come on everybody knows what the gaussian elimination is and there in that paper he introduced the first algorithm for performing matrix matrix multiplication faster than the o and three time bound that would result from the naive method this means that his algorithm is like the best of the best when it comes to computing the product of two two by two matrices there is no formula that uses fewer than seven multiplications how he did it he doesn't say maybe somebody flew into german can call him up and ask him like what kind of person do you have to be to discover some great mathematical algorithm like what are your hobbies can we talk what do you do on the weekends i mean at this point at the time of recording this he's 85 so i don't know he probably just relaxes his brain muscles for the most part i mean i know i would they're probably still smoking anyway not to knock on this awesome person and as great as the algorithm is and the contribution it's made to matrix multiplication unfortunately it's too numerically unstable for some applications in practice fast matrix multiplication implementation for dense matrices use strawson's algorithm for matrix sizes above a breaking point then they switch to a simpler method once the subproblem size reduces to below the breakover see divide and conquer in any event the publication of its algorithm did result in much more research about multi matrix multiplication that led to faster approaches it opened the door to bigger and greater things which is pretty neat okay now that we've got that all under our belt let's take a deep dive into what the algorithm really does just a few minutes ago we saw the naive method so you should be somewhat familiar with it in two two by two matrices we have eight multiplications with stress since we can get this down to seven with basic mathematical formulas and i've gotten it all written out so you can see it all work in a program let's take a peek we're still going to keep our 2x2 matrices for simplicity yay but we're going to look at our famous or infamous methods of optimization iteration and recursion for strassen's algorithm we're dividing our matrices not by halves but by quarters and then we'll solve or conquer each sub-matrix to solve the entire problem in our iterative method we're breaking down the two matrices all the way down to each individual square or quadrant we'll name our passes p and simply plug in our mathematical formula used to compute our multiplication and addition on the quadrants now although we called numpy cheating we're going to implement it here just for a little bit of ease by instead creating a result matrix of zeros we're going to make a new matrix called c and number each quadrant of c as c1 c2 c3 and c4 for each quadrant we plug in our equations for our passes these equations are our conquered solutions to the quadrants lastly we use numpy to implement a new matrix by using the np dot array feature and input our four c quadrants pretty cool the recursive solution is very similar only we're recursively splitting the matrices into our quadrants and recursively computing our seven passes what did we learn what did we learn we learned that the merge store is an efficient general purpose sort that can be implemented in several ways including the top-down and bottom-up approach we learned that matrix multiplication is used in simple graphics all the way up to hd tvs and we wrote our own python program to calculate two matrices we looked at strassen's algorithm for matrix multiplication and learned that he discovered how to get the lowest amount of calculations possible for multiplying two matrices to this day computational efficiency of matrix multiplication is still a hot topic in theoretical computer science apparently if you google greediest person a real live person does pop up can you imagine like googling the worst person in the world and your face gets blasted on the screen now i'm not going to show who this person is because i don't know who he is and it's not really important just kind of funny but it does tie in with our algorithm what is greed to you like what is a greedy approach say your beautiful old granny baked a pie for your family and uncle bob shows up you know amy's ex-husband and he takes the biggest piece of pie for himself that'd be pretty greedy wouldn't it by him eating the largest portion that sure would make the pie easier to finish wouldn't it it wouldn't be great for everyone else or their rumbling tummies but by taking the biggest portion and leaving just little portions to take care of that's sort of the concept behind the algorithm the paradigm behind the green concept is that it builds up a solution piece by piece always choosing the next piece that offers the mo the obvious and most immediate benefit by using several iterations and by obtaining the best result at a certain iteration the results should be computed in other words it follows the problem-solving method of making the locally optimum choice at each stage with the hope of finding the global optimum something to keep in mind though is that they do not consistently find the globally optimum solution because generally speaking they don't operate exhaustively on all the data nevertheless they are useful because they are quick and often give good approximations to the optimum if a greedy algorithm can be proven to yield the global optimum for a given problem class it typically becomes the method of choice a really fun problem that we can lead off with is called assign mice to holes what we need to do is put every mouse to its nearest hole to minimize the time how can we do that and what's the optimal approach what would you think about sorting the positions of the mice and holes first that would be pretty greedy of us wouldn't it this allows us to put a particular mouse closest to the corresponding hole in the holes list we can then find the maximum difference between the mice and the corresponding hole position to determine how much time it will take to get there now does being greedy always equate to maximum of something regarding problem solutions not necessarily don't let that word fool you for this problem we're finding the maximum difference hint subtraction to find the minimum amount of time it takes for our mice to travel as a quick side note another problem that i would encourage you to learn on your own a triple dog dare you is the kids with greatest candies problem using the greedy approach this is considered an easy problem so don't worry too much the problem is similar to this one by asking for the distribution of the minimum number of candies that can be given to a kid and then seeing which kid will contain the maximum number of candies so again the greedy approach can be tricky we have to carefully decipher word usages to make sure we're solving the problem accurately but with that being said the assigned mice to holes problem will help set you on some solid ground and make it a bit easier to work on other challenges now if you do decide to tackle the candy problem and i do highly encourage you to do that i'll give you a little hint the brute force method would be a one by one distribution of candies to each child until the condition satisfies and yet the greedy way would be to traverse the array just twice from beginning to end and back again by greedily determining the minimum number of candies required by each child as a personal challenge to yourself work out how that could be written it'll be fun let's head over to our ides and slam dunk some mice into holes okay we need to get our mice into holes and we have to do it quickly but first things first we have to make sure that there are an equal amount of holes to our mice this is our base now we initialize our greedy approach by sorting the mice first then we create a variable to store our maximum difference and loop through the length of our mice in our if statement we create the condition that if the position of the mouse subtracted from the position of the hole is greater than the maximum difference our max diff variable gets reassigned to hold that difference lastly we just return the largest difference our last mouse gets to the hole in x amount of time by sorting our two lists first this puts us at an advantage to finding the minimum time faster our code is concise short and along with python's sort feature we are really rocking it out next up is kind of a doozy the fractional knapsack a pretty well known problem for our greedy algorithm if you were a little bored with our mice and no holes you won't be with the knapsack for a step up on the greedy method let's take a peek into what's called the fractional knapsack now this is intense fractional knapsack freshness people okay so this problem on the surface seems really complicated but it's only as complicated as you want to make it you know what i mean so let's not make it complicated okay so just so what you can do is just envision me it's the apocalypse it's the end of the world wait maybe it's just a monday food is scarce people are bartering water is practically non-existent so i need to conserve every bit of energy i have to walk to the market and try to trade what i have to stay alive okay now i have five objects i can take our knapsack or bag is our container for holding our objects think of our array as a storage device and each object is worth something some are worth more than others and each object weighs something some objects way more than others the key to this problem is to make the right decision on which objects are going to bring me the most profit i mean i gotta know i have animals to feed that haven't become somebody else's dinner you know while at the same time they can't be too heavy that i can't carry in my container because this is crucial i might have to make a decision based on its object the weight of the object not necessarily its profit if i want to make it back alive from zombies r us now the real kick in the head on solving this lies in that little teeny tiny word fractional this means that my objects can be divided if they are divisible say one of my objects contains three chapsticks i can divide that object and bring only two chapsticks if it will make a difference who knows cat fat might be a real hot commodity remember in that book of eli movie where he killed that cat well it was for food but he also made chapstick out of it not saying my chapstick would be that it'd probably be made from beeswax or something don't forget i'm risking my brains to go to the market to feed my animals in the first place so no cancel be harmed here no siree bob okay wow that was a really long way off the beaten path if let's get back to the problem so the weight is divisible and it would help to best fit how many profitable objects in my backpack then we should do that why we need to fill to the brim in our fixed size knapsack the most valuable items that we are able to carry for the steps of our algorithm keep in mind we are given weights and values of n items and we need to put these items in a knapsack of capacity w to get the maximum total value in the knapsack by the way in the o1 knapsack problem a whole different problem is one where we're not allowed to break items down or divide them using fractions we either take the whole item or don't take it but in this problem fractions can be used a really efficient solution to this problem is to use the greedy approach as opposed to brute force remember brute force is calculating every possible solution and is typically computationally expensive meaning it takes a lot of runtime and memory space the basic idea is to calculate the ratio of value slash weight for each item and sort the item on the basis of this ratio then take the item with the highest ratio greedy remember and add them until we can't add the next item as a whole and at the end add the next item as much as we can this will generally always be the optimal solution to this problem you'll see what i mean when we get into our ides and start coding it so let's get to work okay we'll define our functions with three parameters we need our values our weights and the capacity of the bag now we have our created variables here but i implemented print calls to show you what's going on we have our items a range of zero to four equaling five items the ratios are values divided by weight using floor division to eliminate floats list comprehension is good to use when you can then we'll sort our ratios in decreasing order lastly the ratios index positions are printed here to show the to show you the order that it will be computed in i'm going to take out the third variable here it as it won't be needed i just wanted to show you how it matches up with its index position our ratios being sorted is taken care of in the items.sort line we need a counter to keep a running tally of our max value we will create a list that is the length of our values we'll call fractions that will contain all zeros i'll tell you why we're doing this at the end of the program now it's time to run our for loop we'll iterate over our items and if the weight of our item is less than capacity it will add a one to our fractions list of zeros at its index position then we'll add that value to our max value and subtract the weight from our capacity now when all those conditions satisfy and we hit our else we take the fractional difference of our last item and add it to our max value then we return our maximum value which is 500 now here's the key you might be wondering this we have an item that weighs a 10 and it's worth 90. at a capacity of 150 we could put 15 of these items into our bag for a value of 15 times 90 equaling 1350. why can't we just do that we can't do that because what we're looking at today is what is called the bounded knapsack problem or bkp for short the scenario i just painted a 15 15 of the same items would be allowing for copies of that item called the called the ukp type short for unbounded knapsack problem and that's a whole other ball of wax kids this is why we set up the fractions list containing nothing but zeros this is important because it's putting in our highest values first and then taking a fraction of the last item from maximum capacity in our bag each item counts as one in our fractions list until every zero is turned into a one but our very last item to change from zero to one is that special one that gets the remaining capacity divided by the weight that figure gets multiplied to our value and then added to our max value in the case of our program that ends up being 28 and a half percent and what's 28 and a half percent of 140 is the value of 40 that puts us up to 500. sorting our ratios in decreasing order gives us the optimal or best approach this is considered greedy as you are placing items with the largest ratios into our bag first now you can sort by price and you can sort by weight as those are considered methods and they will get you close to 500 but it's just not 500. and we should always strive for the best method algorithmically hopefully you now understand a pretty well-known problem not only in logistics but other fields as well like manufacturing and finance it's all about optimization what is the optimal way to get the items of highest value into a bag that you can reasonably carry and this greedy concept can be carried out in other reasonable scenarios as well with the goal of calculating solutions whether that be approximations or actual figures let's move on to our last section with good old fibonacci in our mind breaker episode we're going to talk about another well-known mathematician leonardo alpisa aka fibonacci considered to be the most talented western mathematician of the middle ages according to wikipedia he wrote the libre abachi the book of calculation and is it is a historic 13th century latin manuscript on arithmetic which includes the posing and solving of a problem involving the population growth of rabbits based on idealized assumptions the solution generate generation by generation of rabbit offspring was a sequence of numbers later known as the famous fibonacci numbers or fibonacci sequence in a little side compartment of mathematics however what we are going to talk about today is the greedy algorithm for egyptian fractions first described by fibonacci for transforming rational numbers into egyptian fractions an egyptian fraction is a representation of an irreducible fraction as a sum of distinct unit fractions and this means that every positive fraction can be represented as a sum of unique unit fractions a fraction is a unit fraction if the numerator is 1 and the denominator is a positive integer for example 1 3 is a unit fraction to take a closer look we'll reduce a fraction of 7 14 in a pizza example the egyptian way in order to generate egyptian fractions we will utilize the greedy algorithm because although possible to use brute force search algorithms to find it it would be extremely inefficient remember 3d algorithms are for optimizing our problems we always want to know and understand the optimal solution as a side note although fibonacci's greedy algorithm isn't the only way to efficiently solve our problem he's our focus for today let's look at a program so yeah i got this program here we're importing some tools scroll down some we got three functions going strong a main a validate a converting function we got some wrappers nestled functions we got some yields which means it's a generator not even gonna touch that this is a lot of code heading into nearly 50 lines is it good yes hard to write depends but if you're looking for kindergarten style programming you come to the right place i totally dumbed it down to show you the mechanics not that you're dumb i love simple make it plain am i right so we have this pie remember that bob took a big old chunk of let's change that to a pizza since it kind of goes with our theme of leonardo of pizza or fibonacci so to get this real simple we'll write a function that takes our numerator and our denominator we'll implement an empty list for our denominators we won't need one for our numerators because we already know that they're going to be ones then we write our while loop that as long as our numerator isn't zero we can create a variable that stores our quotient using the math dot seal that will round it up this is important for when we have a number that's a float lower than one next we reassign our numerator to be the product of the quotient and the difference of our denominator subtracted from our numerator then we reassign our denominator to be multiplied by our quotient or x for our fraction of 7 12 this is going to put a 2 and a 12 into our egypt list and those two numbers are our lowest common denominators or lcd for short all that's left to do now is put a 1 over those lcds as those are our egyptian fractions and that can be accomplished a few ways but basically i just implemented some good old-fashioned string formatting by iterating over our egypt list of denominators and adding them to an empty string once we do that we just return it the caveat to this really simple program is that it probably doesn't work for really complex fractions or when the numerator is larger than the denominator but this is a good exercise in understanding how to break down a fraction the egyptian way ultimately all of this runs more along the line of recreational mathematics however there are still open problems involving egyptian fractions that have yet to be solved or proved who knows maybe you can be the next mathematical genius to solve one of them so what did we learn about greedy algorithms we learned optimization of solutions to problems using the greedy algorithm provided in our example with the mice in the holes it's like a delicious big pie where you take the biggest slice out first this makes the pie easier to finish we learned that chapstick made from cats is a hot commodity in the apocalypse kidding we walk through the fractional nap stack problem where we find the largest value of an item in a way to maximize the total value within the knapsack we want to avoid brute force here because finding all the possible subsets would take too much time we learned that fibonacci was the first to describe an algorithm for transforming rational numbers into egyptian fractions and it is where we really take the largest unit fraction we can and then and then repeat that on the remainder although this is purely mathematics it's still a good representation of the greedy algorithm what do you think when you hear the word dynamic well if you're a programmer or an aspiring programmer you may not know what to think what does being dynamic really mean for once in my life it would be awesome to be described as dynamic because when we talk about a dynamic person it means energetic spirited active lively zestful vital vigorous maybe this is why when it comes to computer science students can become intimidated with the subject of dynamic programming ultimately the word dynamic means a process or system characterized by constant change activity or progress with its roots in greek to the word dynamous meaning power hint dynamite so it's no wonder we subconsciously shy away from it because it just sounds like a handful it dangerous pretty wild how words and their meanings really deep down can make us feel a certain way you know but i'm here to help you out and put you at ease and tell you a little secret they introduce dynamic programming to children okay maybe not children children but like upper elementary middle schoolers kids like that so if they can learn about it so can you but first we have to unplug our preconditioned mentality if you will to think and believe that anything in computer science is too hard it's not it's all just one big treasure hunt to find information and knowledge that best suits your intellectual filter not all people teach all things the same way not all people learn information or absorb knowledge the same way so let's take a deep breath and step back to look at the different dynamics that are out there that's a long list for us there should only be two that should really mean something that's dynamic programming languages and dynamic programming as a methodology you can have programming languages that are either dynamic or static python is dynamic by the way and then you have programming methodologies that are concerned with analyzing a problem by developing algorithms based on modern programming techniques in the world of dynamic programming dp is used when the solution to a problem can be viewed as a result of a sequence of decisions with the intended outcome of reducing run time and any implementation that can make a solution more efficient is considered optimizing it in an early lesson we saw several problems that can be viewed in this way i.e the knapsack problem essentially the difference between the greedy method and dp is that in the greedy method only one decision sequence is ever generated and in dp many decision sequences may be generated however sequences containing sub-optimal sub-sequences cannot be optimal and as far as possible will not be generated and this is the key that helps make a reduced run time optimal substructure means that optimal solutions of subproblems can be used to find the optimal solutions of the overall problem in dp this is called the principle of optimality the principle of optimality as relayed by richard bellman who introduced dynamic programming in 1953 states that an optimal policy has the property that whatever the initial state and initial decision are the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision so what does that mean in general we can solve a problem with optimal substructure by doing three things breaking the problem down into smaller sub problems solving the sub problems recursively and then using the optimal solutions to construct an optimal solution for the original problem but there's an issue with this that we need to be aware of and that is sometimes when we do this we can get overlapping subproblems we want to avoid that for instance in the fibonacci sequence f3 equals f1 plus f2 and f4 equals f2 plus f3 computing each number involves computing f2 because both f3 and f4 are needed to compute f5 a naive approach to computing f5 may end up computing f2 twice or more in order to avoid this we instead save or store the solutions to problems we have already solved in dynamic programming there are three basic methods we have recursion top down with memoization and bottom up with tabulation and although we could have chosen the well-worn path of the fibonacci sequence to do this oh no i'm encouraging you to step out and think bigger have confidence you are smart and you can do big things so let's get ugly with it in our first lesson what are ugly numbers and why do we call them ugly and what do we do with them to answer the first question i saw this and i think it will give you a big hint okay that's funny and i wish i could have been the one to think it up but alas i was too slow to the game darn i stumbled upon a pretty funny thread about ugly numbers and i stole that so shh don't tell on me but the long and short of it is this to check if a number is ugly in the first place we divide the number by the greatest divisible powers of two three and five and if the number becomes one then it's an ugly number otherwise it's not we're employing our power of prime factorization we learned that way back in the fifth grade so that tells me that you probably don't remember but it'll all come back to you today the sequence of one to six eight nine 10 12 15 shows the first 11 ugly numbers by convention one is included all right now that you got that under your belt let's tackle the problem of finding the nth ugly number can we find the hundredth ugly number would you believe that if we crafted a program using brute force it would be over a thousand iterations for the hundredth number i think i broke my visualizer trying to run it and we don't want to break things or make our computers smoke out the back or anything like that so it's time to incorporate our spirited energized vigorous programming that's like dinomite but not a lot of dynamite we'll start small and just find the 15th ugly number how does that sound since we're going big and not going home we're gonna shoot for the bottom up method for a dynamic approach if we use a pretty simple iterative with some recursion solution we're still looking at nearly 600 steps or iterations in the program to get our results as compared to just a little over a hundred steps for the bottom-up dynamic programming method talk about optimization if we use simple iteration and continuously loop through all the numbers to find whether each number is ugly or not it can really bog down when we get to larger numbers with dynamic programming instead of starting from the head we start from the bottom we're also using a table to help us store the values for easy access if we look at the ugly number sequence 1 to 6 8 9 10 12 15 we can see that it can be further divided into sub sequences of 2 3 and 5. and these subsequences themselves are ugly numbers therefore we take every ugly number from the above sequences and choose the smallest ugly number in every step to make sure that we don't miss any number in between let's head into our ides okay so if we're looking for the nth ugly number in a sequence we have to write a function that will tell us if our numbers can be evenly divided in the first place meaning no remainder x modulo y equaling 0 gives us what we need to prove that if there is a remainder we'll just write it to return our original number for our second step before we can find the nth ugly number position we have to check if it's an ugly number we can do this recursively by going back to our first function the successive division what this does is plug in the number we're checking and successively or successfully if you want to think of it that way dividing it by two three and five if our number is successfully divided by two three and five with no remainder we have an ugly number on our hands let's check a six it's true six is ugly okay so we have what we need to find our nth number six is fairly easy since every number before it is ugly so the sixth ugly number is six but what's the 15th number well let's write a program to find out essentially what we're doing is merely creating a counter coupled with recursively calling back our ugly check function we'll create two variables one for i to iterate up our sequence and one for our counter and then we just incorporate a while loop to say as long as our number is greater than our counter we'll add one to i heading up our number sequence and if that number within our while loop is ugly add a 1 to our counter then we just return i so what's our 15th ugly number it's 24. now if we run this program we have a lot of running back in our recursive calls for every number in our sequence and that's a lot of running back with 600 steps or iterations that's a lot considering with dp we can write a much more efficient program that cuts all those iterations by nearly 80 percent let's check out the difference the first major thing we can do is eliminate those three functions within our original program we won't need those remember when i said we were going to implement a table to store information well that's what we're doing then we'll start our first position in that table or in other words a dynamic programming array to store the ugly numbers next set pointers for our multiples of 2 3 and 5 and we can do this all in one line which is pretty cool you'll see how this works as we get deeper into the program here's our multiples of two three and five in their own variables after that we loop from one to n at each step and we find the minimum ugly number out of three multiples and store it in our dp array we're also increasing the pointer for the number whose multiple has been added and replace it by its next multiple so suppose a multiple of two has been added to the array we increase twos pointer by one and multiply the previous multiple to two to get the next multiple and so on and so forth for other numbers as well and this way starting from the base case we generate all the ugly numbers and then apply dynamic programming to store the numbers in the array until we get the nth ugly number this approach is way better than the previous one because instead of checking all the numbers for being ugly we just used the previous ugly numbers to generate new ones watch how this runs through the program this really is the better way very efficient now let's put this knowledge to good use on a very famous problem called the traveling salesman problem if you haven't heard of this yet you will best to get it in your brain bucket now rather than later the traveling salesman problem is one of the most intensely studied and famous problems in computational mathematics with its main main really main focus on optimization so much research has gone into this challenge of finding the cheapest shortest fastest route in the visitation of locations by this dashingly handsome or beautiful salesperson this person starts in their home city travels around and returns to their starting point most easily expressed in a graph the general form of the tsp traveling salesperson appears to have been first studied by mathematicians during the 1930s in vienna and at harvard notably by karl menger menger defines the problem considers the brute force algorithm and observes the non-optimality of the nearest neighbor heuristic using the mailman as an example now the order in which the person travels isn't cared about as long as he visits each one once during his trip and finishes where he was at the first in the most cost effective way but there's a catch maybe the salesman needs to take a plane to one of the cities and this will cost him a pretty penny maybe he can walk to one of his cities therefore making it a free trip the cost associated with the trip describes how difficult it is to to traverse the journey or graph for us computer scientists whether that's money or time or distance required to complete the traversal the salesman ideally wants to keep every cost as low as possible he wants the cheapest fastest shortest route wouldn't you the easiest and most expensive solution is to simply try all the permutations and then see which one is cheapest using brute force the problem with this though is that for n cities you have n minus 1 factorial possibilities this means that just for 10 cities there are over 180 000 combinations to try since the start city is defined there could be permutations on the remaining nine and at 20 cities this just becomes simply infeasible this is why four is often used in the majority of problems as you'll quite often see in the 4x4 matrices keeping it small makes it much more manageable and understandable which is good the awesome news for us is that the problem is solvable but keep in mind that there can also be solutions to the problems that are approximations or commonly called heuristic algorithms if that's what is being asked for according to wikipedia even though the problem is computationally difficult many heuristics and exact algorithms are known so that some instances with tens of thousands of cities can be solved and even problems with millions of cities can be approximated within a fraction of one percent wow so let's get to the nitty gritty and look at our steps number one consider city one as the starting and ending point number two generate all n one factorial permutations of cities three calculate cost of every permutation and keep track of minimum cost permutation four return the permutation with minimum cost it's not hard to see how this could get computationally expensive in a very short amount of time so we will move into the optimize method right away for our savings and our sanity the goal is to break this problem down into the smallest pieces possible and then solve solve solve let's get into it because permutations are a big part of the tsp problem we're going to import intertools permutations to make our lives a whole lot easier it's totally okay for this one we'll implement a variable that we'll call v short for vertices and vertices are the dots on our graph think of our sales person traveling to four cities on our graph a single dot is called a vertex on our graph and they link or connect to one another now we can move on to implementing our function call here with two parameters our graph that will be a four by four matrix and s is going to be our counter that will need to calculate the sum of our path i'll explain this a little bit deeper at the end of the program we'll create an empty list for our vertices to be stored in and we'll call this vertex just to make it plain this is going to tell us the best route for our rows in the graph again this is going to be come real clear at the end of the program so hold on to yourselves then we iterate over our range of v and if the index does not equal us which is zero we append it to our empty vertex list this is going to show us where our salesperson is traveling within the graph but here's a little catch that we need to be aware of check out our graph see those trails of zeros we have no need to calculate those so when we append our indices to our vertex list we're only producing three integers one two and three next we create another empty list that we'll call min path we need to know the best route so this will store our lowest combination of vertices within the graph then we create a variable that we'll call next permutation and we'll implement the inter tools permutations module here to give us all the combinations of the vertices for one two and three since we have three numbers we know that the amount of permutations will be six then we iterate over all those combinations and create a counter that we'll call current pathway we'll reassign our s to a variable we'll call k and k will represent the row in our graph and as we iterate over our indices within our permutations by using j this becomes our columns i know this sounds i know this all sounds really confusing but stay with me when we add the k and j of our graph to our current pathway look what prints out this is calculating all the paths within our graph and adding them together pretty cool isn't it next we reassign k to j and then use an addition operator to add the sums to our graph to the current pathway append them to our min pass hold them in a variable called x that's sorted and simply return the very first number in our sorted list which is our lowest number our shortest route on the graph to see how this travels on the graph watch this this is how it is adding up within our program hopefully you can see and understand how this is all working it sounds so much more complicated than it really is but it's only math we're simply calculating the paths of a matrix by pulling out all the combinations or permutations of the indices and returning the lowest number or lowest sum of the path it's not too bad my recommendation to you would be to create your own graph and then run it in the program once you do that map that course on paper or even whiteboard it to see it visually for our very last lesson today and not only for dp but all together i'm so sad to leave you so let's make this session a great one what we're doing for our mindbreaker sounds really intimidating but i can assure you that once we break this down you're gonna say wow that wasn't even that bad and then you can brag to all your friends and then they'll shun you for your genius but it'll be totally worth it i i mean because who needs friends am i right now your brain won't break too much if we take each word out and examine it first we have palindromic which is religious palindrome matrix we'll keep it low and slow with a 3x3 and then just paths which we're only going to go right and down only since we worked on a matrix in our last problem this should be old hat hopefully by now you have a decent handle on breaking down the problem into smaller ones called sub problems and solving them little by little in order to solve the whole tips for getting started on the palindromic matrix path problem would be to first know how to check whether a string is a palindrome or not in the first place you can use python's python has a little pip install program called palindrome that checks whether a string is pendulum or not but i do highly recommend you learn how to do this on your own because it will help with this problem the second tip would be knowing how to traverse a matrix going right and down only we're not going to get too crazy for our final lesson and just have some fun with it by printing our palindrome strings we're not going to return counts or find the longest because that might make some of us cry and there will be no crying today any tears that gets shed must be happy tears only whether that's joy at finishing this course or not seeing my face anymore tears of accomplishment are fine but no tears of sadness okay to keep it simple we'll start at ground zero and start with an empty three by three matrix and find all the unique paths what's really cool about this is that it's actually just a math problem what we'll do is create in our three by three by starting with a row of ones that we will build up from our bottom row and far right column will be ones and when we add their adjacent numbers together and build up we get a row of ones one one one at the bottom and then three two one in the middle and then six three one at the top if we return row zero that will give us six and that tells us that we have six unique paths in our matrix this will come in handy later when we implement this principle into our matrix of strings we can know that we will have six strings returned to us and all we need to do is check whether they're palindromes and print those out so we're not going to talk much if at all about the naive approach or brute force or whatever the difference is in optimization no let's part ways on a good note and have some fun with this i mean we walked through 14 other problems with multiple methods in a relatively short amount of time and here we are breaking our minds on palindromic matrix paths so yeah let's get straight to the optimum let's code the paths problem first shall we we'll start by creating our function with two parameters our row and our column we already know it's going to be a three by three then we create our dynamic programming array of all ones which you can envision as our bottom row of ones next we iterate over our rows in a for loop and then create another dp array which can be envisioned as an accumulative next row up in our matrix our original for loop is going to iterate three times 0 1 2 for each row in our matrix in a second for loop we now want to iterate from the bottom up and reassign our new row elements by adding one element to the one next to it going left we do this twice while in our final iteration it has accumulated each row to end with six three one we then reassign our original row as the final row and return the very first element which will be six our answer to the number of paths now this isn't super necessary but it will give you an idea of the path traversal within a three by three matrix and will give us a good launch point to moving up to a matrix consisting of letters we'll keep it in the realm of just two letters a and b and we'll write a very quick little program to see how many palindromes of a and b there are let's import intertools to help us and then create our rows and columns of letters a neat little feature of inter tools is product with an asterisk on our matrix this will print out every combination of letters in our matrix totaling 27. yes there will be duplicates here but it's nothing that python's set can't handle let's create an empty list called p1 and then iterate over our list of 27 tuples join them together to make it easy on the eyes and append them to our empty list then all that's left to do is check which ones are palindromes by making a new function plugging in our p1 create another empty list p2 and then iterating over a non-duplicate set of p1 incorporate an if statement is it a palindrome yes put it in our empty list then return it okay so far we've traversed a matrix in order to count the number of paths in it we created a three by three matrix of just two letters found every possible combination and created a function to pull the palindromes from it we are doing fabulously if you know how to count the paths of a matrix and find the palindromes in a matrix you're totally equipped to take on the palindromic paths problem let's get cracking so before we start i have to tell you there's going to be a little bit of a difference here for this program it's the order of traversal we're going to go from the top and right to the bottom not the bottom up and left to the top so keep that in mind as we march forward we're going to throw in our little palindrome checker up here first before we print them out at the end of our function hopefully by now you're familiar with that next we're going to create our main function with several parameters a string that will be empty but we're just going to call it string here a for our array our pointers that we'll call i and j our row and column that we'll call m and n now our conditional if statements are going to traverse the paths of our array we minus one from m and n because as you know this is python and we only need to iterate from indices starting at zero then one then two for our total size of rows and columns three by three see the i plus one and the j plus one within our recursive callbacks look at these slides to see the paths you could also print i and j within the conditional statements on your own to see it as well but when we add one to our pointers we're moving to the next element then once the traversal is completed it hits our else statement and that hits up our palindrome checker if it's true it'll print then it moves on to do the next reversal over and over until it's done and there you have it four palindrome strings in our matrix yay so what did we learn on our final lesson we learned about dynamic programming which is finding the optimal solution to sub problems that can be used to find the optimal solutions to the overall problem we saw this in our lesson with ugly numbers the traveling salesman problem and palindromic matrix paths in the easy lesson we learned about ugly numbers what they are and how to write a program to find the nth ugly number in the sequence avoiding brute force and recursion we were able to implement dynamic programming to optimize the solution from over one thousand iterations down to just a little over one we looked at the very famous traveling salesman problem with its main focus in optimizing a solution to finding the most efficient route a solution used across the board for so many companies in order to keep operational costs low and lastly we broke down the mind breaker lesson by studying unique paths in a matrix string palindromes within a matrix and combining those two problems together to find all the palindromic paths within a matrix are you excited i know that i am we covered so much ground in this course it's crazy hopefully you took lots of notes so you can practice later you should be coding something every day even if it's just for a couple minutes 10 to 15. since every little bit helps now listen to your mother thank you so much for joining me today and if you made it all the way here kudos to you i wish you all the best in your programming journey byein this python algorithms course you will learn to work with recursion data structures greedy algorithms dynamic programming and more you don't need any previous experience and algorithms to follow along algorithms help us solve problems efficiently and employers pay good money for good problem solvers your instructor for this course is joy brock she has an amazing talent for breaking down complex topics using humor and visualizations hi can i ask you a question raise your hand if you love being bossed around i'm not seeing any hands i know that i don't like to be bossed around now you might be wondering why i would ask a question like that and what does that have to do with computer algorithms but that's just it computers love to be lost around in fact a computer can't do anything on its own without being told what to do and that my friends is what an algorithm is an algorithm is a specific set of instructions that we write to the computer to tell it what to do after all that's why you're here right to learn how to tell that old ball and chain who's boss you know the one that keeps us perpetually locked in a prison of screen time so without further ado welcome to the introduction to algorithms course i am so glad you're here we are going to have an insane amount of fun so grab your beverage of choice grab a notepad for notes and be prepared to learn the five basic algorithms that every programmer should know by official definition an algorithm can be defined as being the current term of choice for a problem solving procedure it is commonly used nowadays for the set of rules a machine especially a computer follows to achieve a particular goal it does not always apply to computer mediated activity however the term may is accurately be used for the steps followed in making a pizza or solving a rubik's cube as for computer powered data analysis algorithms are often paired with words specifying the activity for which a set of rules have been designed a search algorithm for example is a procedure that determines what kind of information is retrieved from a large mass of data an encryption algorithm is a set of rules by which information or messages are encoded so that unauthorized persons cannot read them this comes from the merriam-webster dictionary what does algorithm mean mathematically speaking algorithms have been around for nearly 900 years pretty amazing isn't it in fact algorithms are all around us every day and have been our whole lives in this course we're going to dive into algorithms that are finite or determine sequences of explicit instructions that are used to solve problems and or perform computations these computations are generally to perform calculations or to manipulate data using natural language processing natural language processing or nlp for short is what tells the computer how to comprehend and interpret written text it's important to distinguish the difference between using well-defined formal languages to calculate functions versus algorithms used in artificial intelligence or machine learning those algorithms are where automated deductions are made using mathematical and logical tests or where predictions are made based on patterns learned from experience for example the other day when i was looking at the front page of google on their news i thought you know this algorithm better be so good that i can read about the news before it even happens those types of algorithms are for another video on another day the objective here in this course is to give you the tools you'll need to undertake the journey of using a well-defined formal language in this case python to calculate functions within a defined amount of space and time that may be asked of you for interviews or tests in other words the goal is for you to be able to find differences in algorithmic approaches based on computational efficiency this means that how we write our program is very important in regards to how much space it can use up on our computer or how quickly it can run and it all begins with the foundational principles that every algorithm has in input well-defined instructions execution of those instructions step by step leading to an output that ends in termination of the program now there are many different algorithms that accomplish these basics when it comes to programming and as much as i love spending time with you all it would be so difficult to cover every single one so for the sake of brevity we'll be covering the following simple recursive algorithms algorithms within data structures divide and conquer greedy algorithms and last but certainly not least dynamic programming for this course you'll need some understanding of the python language like writing functions variables conditionals for loops and basic syntax an ide or integrated development environment an ide is the virtual place to write our programs now if you don't have a downloaded platform like pycharm jupiter notebook or visual studio code you can just use any online python ide through a google search if you would like to download your own personal ide such as pycharm vsc or jupiter you can definitely do that as each one of those platforms are free to install go ahead and pause the video now if you need to get situated otherwise let's get this party started enroll into our very first lesson on simple recursive algorithms in our first lesson we're going to learn what is recursion and we're going to examine three different problems ranging from easy to mind-breaking we're going to look at the differences in computational efficiency and see which approach is best is implementing recursion the best way let's find out if the easiest way to define recursion is to say it's where a function calls itself then what's the hard way to define it in all truth it's easy to throw a statement out hand on hip that goes oh it's a function that calls itself sure okay good for you but what does that really mean i think oftentimes when it comes to programming it's easy to take for granted this idea that we should automatically know what it all means i don't know about you but i wasn't born with the ability to comprehend various methods to solve problems let alone be able to decipher which which method is better in the first place you know we all need to learn these concepts layer upon layer step by step so let's start at the very first layer and build up from there now when we write our program recursively it's important to understand that this is in contrast to writing it iteratively or through iteration when we do that we're generally using for loops to iterate over an object instead of making a function call back within the program you'll see what i mean when we get into our ides and and start to write the code recursion is it originates from a latin verb that means to run back and this is what the program we're going to write together is going to do it will run back to itself over and over as many times as it needs until the program terminates so does this mean that we can't use for loops with recursion no of course you can use them in fact they will be needed and you'll see how that all works in just a moment in order to get started with our very first lesson involving factorials and the algorithmic method that we are going to use for better efficiency we will calculate the factorial of a number using the leaf method or last in first out and it all begins with a mental picture of a bookshelf that doesn't have any books on it yet to perform a lethal operation on your hypothetical bookshelf you will grab some books and begin placing them on the shelf let's say you ordered some britannica encyclopedias wait why would you do that why did any of us do that oh right it was our grandparents that saw to it to make sure that we had our own modern day google machine thanks grandma your legacy lives on at the donation center okay that was a wonderful trip down memory lane wasn't it okay so back to lefo or lifo if that's what you call it so you put your encyclopedias on the shelf a to z in a last in first out scenario what was the last book you you sat on the shelf z what's the first book that's going to come off z so last in first out and this would be important to remember in our number oriented recursive function coming up that the last number that goes in will be the first number that gets called out or computed now if you're a little bit confused it's okay you won't be for long we're going to see this in action right now and talk about the computationally efficient way to solve as we write our first recursive program to calculate the factorial of a number for a quick recap on factorials say you take the number 5 and multiply it by itself minus 1 all the way down until you hit one your answer will equal 120. remember factorials only involve positive integers so once you hit one the program terminates now let's get to work we're going to look at two ways that we can write a program that will calculate the factorial of a number this is going to be a wonderful foray into differences regarding complexity and program efficiency in our first method we're going to tackle this iteratively or like i mentioned before through iteration this means that our program will cycle through or iterate each and every step we tell it to first we define our function with one parameter the number we want to calculate in this case we'll just call it n then we're going to create a variable and start it at one positive numbers remember no zeros here next we construct a for loop to iterate over that variable or object if you like and do something to it in this case we're going to multiply it by every number in a range starting at 2 and adding in our ending at our number plus one this gives us a range of four numbers two three four five now why not six since n or five plus one equals six remember we're using python so if we loop to a range of two comma 6 in parenthesis our indices will always be minus 1 because python starts at 0. so an index position of 6 will give us our last number for our calculation 5. then we take our object called fact and multiply it by every number in our range because we can use the asterisk and equal sign to condense our code a little fact equals fact time asterisk i that assignment operator is reassigning our variable each time it cycles through our loop when the cycling or iteration is finished we simply return our finished fact variable if you want to see the results of each iteration you can just place a print statement within the for loop and run the program for a recursive method it's going to be already typed out while i talk this is where our last in first out comes into play remember when we talked about that this is in contrast to our iterative method that starts at the top are fact variables starting at 1 and then iterates through our range going up until our number is reached in the algorithmic method of recursion when we go to call the function if our number isn't 1 it moves to our else statement where in our else statement we have a temp variable that runs back to our function call and creates a pocket of space if you will for each number minus one it will run back all the way down until it hits one our last n if you will once that happens the return statement and our else statement starts working its magic and then we start heading back up our last in which was one becomes our first out our first number to get computed ta-da now you might be tempted to think that the recursive method is top dog here but alas you'd be wrong our iterative method is twice as fast for what we're trying to accomplish which is just a basic calculation of a factorial what's important what's important to be able to understand is a how recursion works by using a simple program such as momentous did and b how how and why one approach can be better than another in this case recursion is taking up more space and time by running back to the function call to create those pockets for our numbers versus iteration where it's simply multiplying each number in place and not creating anything new it's simply iterating over each number reassigning our variable each time and producing a final output the objective for our basic exercise is to just understand and see recursive algorithms in action so that as you gain experience you'll be able to exercise different modes of expression or expressivity in your writing and in some cases use your readability check out this example on the upside being able to write code in three lines instead of seven or eight can be a huge deal depending on the circumstance however on the flip side may decrease the performance of the code let's like this example that we just coded together it's just not as efficient as iteration in this case so if you're ready let's move up to a more advanced recursive algorithm involving permutations a permutation is when you take a set of elements and find all the different variations that can be made with it for instance if we take a b and c we can get six variations out of these three letters mathematically speaking we can find the number of variations by calculating the factorial of the elements just like we did a few minutes ago for a hands-on approach to understanding a level up on recursion let's take a peek under the hood and see how this will work in a program shelby the underlying basis of how most functions for permutations work is to take off the first element and then create two subsets of numbers that get swapped like this then the original first element gets put back onto the front of each subset then we do this all over again this time instead of popping out the first element we pop out the second one and create two new subsets and so on and so forth the algorithm behind permutations can really make your head spin so take a deep breath find your center and jump in to a puddle let's not jump into the ocean just yet it's good to start small and by small let's recursively swap just two letters of a string this is a little bit harder to do than a list because strings are immutable but this is a good launch point for us to build up from here also we'll start with recursion this time and then afterwards we'll look at a different method for comparison to write a recursive function that will swap just two letters we will need to create a pocket for where our strings need to go remember again strings are immutable and if this were a list we could simply slice it and create a variable swap but that's a no go for strings we're moving into a little bit steeper territory here but stay with me okay you can do this let's create our function and call it permute with two parameters one called string and for the string of two letters that we want to swap and an empty pocket to put our new string in this is our parameter default defaulted to an empty string then we create an if statement for an edge case in the event that the string is empty and if it's empty we just return our empty pocket now we'll start with looping through the range of the length of our string and within our loop we'll start with creating three variables that will contain one each letter on our string two we'll need to take off the front of the string that we're going to call front and then three a variable called back that will slice off the back of our string if you study this algorithm you'll see some programmers call it head and tail current and the rust first next or front and back i like the terms front and back as it gives me a better mental picture but you can use whatever terms you're more comfortable with now those first three variables are fairly obvious but this is where it might get a little hazy we need to create a fourth variable that will put our front and back together and we'll need this variable of combined elements to plug into our function call this is what creates spaces to in our pocket to be able to move our letters around i know this may sound a little complicated at the moment but you'll see shortly that we're going to need each and every letter of our string even however many that will eventually come to be to have the space it needs to go into the right place in our pocket now whether that's going to lead up to eventually being three letters or four keep in mind our strengths can't be too long because of two things the rate of exponential growth and the fact that recursion can get exhaustive very fast the more letters you have recursively that's a lot of running back okay we have all the variables we need right now our letter a front which is just an empty string right now our back which is the last set of our string b and are together that combines our front and back now for our algorithm this is where the magic happens this is the true ham in our sandwich we call our function premium and then incorporate two parameters are together and our letter added to our pocket hence the addition operator this is the heartbeat of our algorithm it needs to run back and put our letters into our pocket once in reverse and then the second time in a copy of its original form because it's still considered a permutation watch how this works in the visualizer i think that if you get really get a really good handle on this concept and you have a solid foundation it becomes so much easier to see how this works with additional letters if you can see it mentally this makes all the difference in the world it's a neat little program that only has 11 lines of code which is really nice however this program isn't as efficient as a program that uses iteration and swapping again that program has nearly double the lines of code i'll spare you the direction of watching me type it all out and just show you here this would be the code that executes just like the beginning that you saw on the earlier slides where it pops off the first letter and then swaps the it pops out the first letter swaps the last two and then pops the first letter back on then it rotates to the second letter swaps those two and then puts it back on check the output here and you'll see what i mean now if you needed to know all the permutations of a string and don't really have time to write the code or the patience you could use the inner tools permutations module it's really easy but that would be primarily for you just to know for yourself or for a quick look up when it comes to interviews or testing companies would generally prefer that you know the mechanics behind the method for solving whether that's using recursion or swapping as with any program the caveat must always be made can this program be written differently as always yes however you will see very little difference when it comes to recursion of most programs like this very generally speaking they will call the function in a very similar way as it is written here by taking the front and back together and incorporating it in some way within the function call along with the letter hopefully you were able to distinctly see how recursion works in this program even just for two letters it can work great on small strings but it will get computationally expensive the longer the string now if you're not too overwhelmed hopefully not we've only done two we're going to move into the mind breaker section like it should be the mind blowing section the end cleans problem this computational problem is about placing eight chess queens on an eight by eight board so that no two queens are able to attack each other according to wikipedia the problem finding all solutions to the eight queens problem can be quite computationally expensive there are 4 billion possible arrangements of the 8 queens on an 8x8 board but only 92 solutions wikipedia also goes on to say that the use of shortcuts and various rules of thumb that avoid brute force techniques can greatly reduce the number of possible combinations which i'm sure is always a good thing but what is brute force though well that's would be brute force would be looking at every single possible arrangement 4 billion of them to find the 92 solutions how long do you think that would take probably take decades for our computers to run a program like that but guess what the use of permutations can reduce the possibilities from 4 billion down to just 40 000. that's a big reduction now we're not are we going to use permutations on the end queen's problem today no way jose but it's good to know that this problem is often used in examples for various programming techniques such as solving it by using recursive algorithms it's also used as an example in constraint programming which is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence computer science and operations research to get a better idea of what that would be we can use a real world example like employee scheduling say for instance a company operates continuously like a factory they need to create weekly schedules for their employees and if that company runs three eight hour shifts per day in a science three of its four employees different shifts each day while giving a fourth one's a day off even in such a small case like that the number of possible schedules is huge each day there are factorially 24 possible employee assignments for four people so the number of possible weekly schedules is 247 which calculates over 4.5 billion constraint programming methods keep track of which solutions remain feasible and makes it a powerful tool for solving real world scheduling problems who knew queens on a chessboard combined with computer programming could help solve real world problems like that so what did we learn in our very first lesson in our algorithms course we learned simple recursion and saw it in action that when a function calls itself it creates new spaces to store information and sometimes this may not be an efficient solution to a problem it's definitely more elegant with fewer lines of code that can come in handy depending on the problem but it's not always cost effective but it is important to see and understand the difference factorials and permutations are used in a lot of computational mathematical and real world applications learning how to write programs rather recursively or iteratively to find the best method in this area can go a long way and may lead to unknown opportunities for you down the road as a programmer we learned about constraint programming where recursion plays a role for solving mind-bending problems not only within board games such as chess but real life issues that companies can face as a programmer that works to gain the tools needed to understand these types of methods to solve problems can make them a valuable asset to any company welcome to level two working with data that is structured i like to think of data structures like something that holds money say for instance you have on your person a big wad of cash consisting of a lot of different bills what could you do with it well you could store it sort it search it add it spend it delete it count it so with data structures they're simply containers or collections of data they provide a means of managing small or large amounts of values for uses and such things like databases web traffic monitoring user registrations and or indexing within a contiguous memory location like an array they can range from as simple as lists to linked lists stacks cues hash tables trees and heaps these are all examples of data structures and since algorithms are steps to solving problems what kind of problem-solving techniques are common with data structures well just like watts of cache data often needs storage sorting counting retrieving searching spending all those fun things now arrays can be a really basic container for information but don't let that fool you many different algorithms can be used on one-dimensional arrays but what about two-dimensional arrays what about 32 dimensions since that's the maximum amount can you imagine arrays are among the oldest and most important data structures and are used for almost every program for a basic level of algorithms with data structures we'll go easy and stick to a linear or one-dimensional array a one-dimensional array is just an array stored in an unbroken block of memory to access the next value in an array we just move sequentially to the next memory address it's best to see this visually so check these slides out for a better idea in our basic section we're going to cover linear search binary search bubble sort and insertion sort we'll be covering a little bit more for the basic level on data structures because it's a really big topic actually entire books are written about them let alone design techniques and algorithms i'll do my best not to put you to sleep hopefully it'll be enough to watch your appetite where array is our concern as this is a huge topic as well and as much as python is a wonderful program with tons of features like built-ins and libraries and modules that can help programmers code faster it's still really important to understand how these features work algorithmically and the concepts underneath it all let's get started a linear search could be equated to pulling that a lot of cash out of your wallet wait does anyone carry cash anymore no okay well let's pretend that you have a wallet full of really big bills i mean go big or go home right and you need a 500 bill from your stack why well you're at the mall of course and you want to buy that really cool pair of socks that you saw in the window and you might be thinking 500 for a pair of socks and i would say yup that's inflation for you but this is a fantasy remember besides inflation slomation you got a wallet full of big bills and in this fantasy let's go for a big ticket item well maybe not sucks but maybe a t-shirt in a linear or sequential search we could technically transpose transposo those terms you would have to go through each bill to find that 500 same with an array of say six random integers if we were wanting to find the eight we we would have to manually check each element in order to return the position of the eight algorithmically it would look like this and can you imagine if we had an array containing a large amount of numbers it would be very very time consuming and inefficient to use a linear search because it would be comparing each integer one by one now can it be used for searching sure but it's only when the numbers are relatively few and relatively sorted but hey let's code this out anyway we'll define our function with two parameters our array and the element that we're searching for then we'll write a for loop to iterate over the length of our array and if there is an element there that's the same as our element then just return where it is in the array when we print it out we get index position 4 as that is where our 10 is a more efficient way to search is to move up to a binary search and the clue is in the name binary as in by meaning something that has two parts in this search algorithm we would create two pointers and repeatedly divide the search interval by half naturally this would reduce our search space so that we're not searching the whole array but only the divided parts the catches at the binary search is that it is usually mostly generally done on sorted arrays that looks like this and this way the algorithm checks whether the middle element is equal to the target that we're searching for in every iteration if the target value matches the element then its position in the array is returned if the if the target value is less than the element the search continues in the lower half of the array the target value is greater than it searches in the upper half of the array ultimately the algorithm doesn't need to search the half our target isn't in with each iteration now let's look at some code because our program is only searching half the array it makes it a much better search let's look at the iterative method first in our function we can create four parameters our array a start point an endpoint and the target that we're searching for we'll create a while loop to iterate over our array from start to end and then create our midpoint our variable called mid is the magic in the sauce we only want to traverse the half that contains our element feel free to print out the mid when you run the whole program for yourself to get a good idea of this next we can implement our if statements we'll only need three check if our target is in the upper half then reassign our start to begin moving to the right of the array if our target is lower than our mid we reassign our end to begin moving to the left of the array if our target matches our mid then just return it easy peasy then we just return our start or we can return something like negative one to print out some strings to make it a little fancy but either way you prefer to have your results printed we have to be sure to declare our start and end in the function call our start is zero from the beginning of the array and our end is the last element our length of array minus one for our recursive function i won't spend a lot of time here because the difference between our iterative program and the recursive program is very minimal runtime and memory space is very very close meaning they're both really efficient either way it's good to see both programs basically all we're doing is just calling back to the original function within our else statements feel free to pause the video for a moment and take a closer look okay now that we have some super basic searches under our belt let's move into a deeper section of sorting because well sorting is fun who doesn't like to sort money piles of 50s here piles of honey is there holy crap i sound like mr krabs all right all right let's mix the money references let's get to sorting our boring old elements as for sorting there are a vast array of techniques that are available and here's a little quick list actually it's not that quick as there are many to choose from bubble sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order for instance the largest integer bubbles up to the top or iterates its way to the end of the array through a comparison of each element although this isn't a very efficient algorithm perhaps the worst it's still an important concept to understand the only real perk the bubble sort has compared to other algorithms is its built-in ability to detect whether or not an array is sorted in the first place in a best case scenario the list is already sorted or nearly sorted and this is in contrast to other algorithms even those with better than average performance whose entire sorting process caused more causes more inversions reversals reversals or swaps to happen an optimized algorithm for the bubble sort is to find the nth largest element and put it at the end of the array there is an unoptimized version that you can check out for comparison purposes if you want to look that up on your own you're more than welcome to do that but the optimized version is done so that the inner loop can avoid having to look all the way at the end when it's running the last iteration it's just saving time and energy by not having to do that although bubble sort is one of the simplest sorting algorithms to understand and implement its performance means that it's that its efficiency decreases dramatically on arrays of larger amounts of elements and it's even been argued that it shouldn't even be taught anymore as it's outdated and is even hazardous to some cpus yikes i bet you didn't realize that you'd be entering dangerous territory here i mean who knew conan could be fraught with such tenuous escapades such as this how sexy let's code it our function will take just one parameter our array and then i implemented an iteration count just for informational purposes next we create a for loop to iterate over our indices in the array going to the right combined with a nested loop inside that iterates over our indices going left or reverse that we're going to call j i strongly encourage you to write this program for yourself and within our nested loop print out j just to see it in action we have our iteration counter when this prints you'll see why i added this now we just tell it to swap elements if they are lower than the one to the left in our if statement if our element to the left is greater then swap it then we just return our newly sorted array so let's print this so you can see our iteration count with 36 iterations that's pretty efficient check this out now i know i said that it wasn't going to look at the unoptimized but guys check this out double the iterations for two functions and it's double the code i liked our first program simple shorter faster unstable oh that was dangerous i kind of like it but hey if dangerous not your thing you thrive in a more stable and secure environment that's fine too we can totally move on to the insertion sort algorithm insertion sort is another simple sorting algorithm that builds the final array one item at a time it's still inefficient on large lists like the bubble sore but it can have some advantages such as simple implementation meaning a reduced amount of code and performs well in small data sets and relatively sorted arrays and it doesn't require much space meaning that it can be done in place therefore not using much computer memory in order to perform well the concept of the insertion sort is to split the array into two sections in order to compare its elements we can consider one side sorted and the other side unsorted our algorithm takes one element at a time from the unsorted side and compares it to our elements on the sorted side if our element is larger or smaller it places it where it needs to be on our sorted side each generation takes an element from the unsorted side and places it into our sorted side all the way till there are no more elements to compare to and in the end we are left with a sorted array for our program our parameter in our function call will be our array starting with a for loop that will iterate starting at our second element we don't need to start at our first integer because that's our sorted side we leave that alone for now we create two variables our key which is our current element and a pointer to the left of our key we'll implement a while loop to iterate as long as our index is greater or equal to zero and our index is greater than our key we then program it to reassign the larger one to the right position and then move down and put our small element to the left we do this all in place without creating extra space it's fairly simple and straight to the point working with arrays can last for days you like that no but seriously what we've touched on is only the tip of the iceberg as a personal challenge to yourself try searching and sorting a two-dimensional array are you up to the challenge for our advanced level algorithm section we're going to dive into linked lists a linked list is a linear data structure in which the elements are are not stored at contiguous memory locations remember this picture also remember that arrays are stored at contiguous memory locations a wikipedia definition states a linked list is a linear collection of data elements whose order is not given by their physical placement in memory instead each element points to the next it's a data structure consisting of a collection of nodes which together represent a sequence in its most basic form each node contains data and a reference in other words a link to the next node in the sequence this structure allows for efficient insertion or removal of elements from any position in the sequence during iteration more complex variants and additional links allowing more efficient insertion or removal of nodes at arbitrary positions a drawback of linked lists is that access time is linear and difficult to pipeline some say that linked lists are among the simplest and most common data structures are they though as an example think of a photo storage website if you click on the website landing page this would be considered your header then when you click on the first image this would become a node the arrow next to it that you can click to see the next picture would be your pointer now if you get to the third or fourth picture and want to go back to the first picture and look at that again those back arrows would mean that you're on a doubly linked list a doubly linked list means that you can traverse the list forward and backward however for this lesson we're only going to cover a list that we can go forward on the singly linked list now the upside of a linked list over a conventional array is that the list elements can be easily inserted or removed without re allocation or reorganization of the entire structure because the data items do not need to be stored contiguously linked lists allow insertion and removal of nodes at any point in the list and they keep up with a constant number of operations by storing the link previous to any link being added or removed during a list traversal so let's talk about our four basic algorithms or common problem solving operations for singly linked lists every programmer needs to be able to do the following traverse a linked list or be able to travel along the nodes and pointers search a list for the header a node or tail a tail is the last and final node insert a new header note or tail and to delete a note or tail a link to list generally always needs a header let's create a simple linked list representing a small family member group we want to be able to do all the operations mentioned above this will require a little bit of object oriented programming so hopefully you are somewhat familiar with that but if not that's okay we'll stay simple and make it easy peasy we need our pretty standard class node and class linked list to start our nodes will be our family members and our linked list will represent our whole family this can be considered a little backwards but i like to instantiate our objects first so it's easier to see what we're dealing with being able to visualize what we're doing is an important skill in programming and design because it helps us think about the big picture throughout the solution let's picture our knowns as a family of mom dad and two kids we'll create our family head as bob his wife amy our header will point to amy as the next node and then our two little nodes max and jenny they all need to point to each other as they will be linked together in our list so we will make sure our pointers are created which is object.next everything looks good and we have all our members individually as nodes but to really see our algorithm in action we need to link all our members together in our linked list where we can operate on that list and design them to be really complex or really simple linked list problems are often used as interview and exam questions so knowing how to create linked lists how to traverse them how to add and take away elements is very important once you get really familiar with those concepts you can move into learn learning how to traverse how to reverse a list swap elements maybe even go on to doubly linked lists or circular it's a really big topic to explore and fun too and if you're not having fun why are why are you here like why so back to our family let's get them created and then set it up to where we can traverse this family list once we have established our class we just need to implement our functions that tell our linked list class what to do this is where we implement all the things we need done with our nodes and the first thing we're going to do is make our nodes by creating the data and a pointer let's create our objects then create pointers that go to each family member now that we have our nodes we can now link them in a list by creating our linked list class this is where we create a function to traverse our nodes in a list and be able to print them all out we only need one argument self because it doesn't need any other value or input to be to be able to do what we need which is starting at our header and printing them all out next by next by nuts then we just call family.traversal and out pops our family members now if you want to shoot these out in a particular way such as in a list or fancy strings that would have to be done within another function in the linked list class which unfortunately is not within the scope of this course that's more in tune with object oriented programming a whole other separate topic the goal here is to focus on being able to operate or solve problems to creating simple function calls on linked lists now our family member list is looking pretty good but word on the street is that bob isn't treating amy too well and he's been running around on her from the looks of it bob might be packing his bags and leaving the family but it's not all bad because dave has been hanging around a bit and although he's bob's brother he's a really good guy i know i know it sounds really back once but seriously dave is going to step up to the plate and he's looking forward to being a dunkle to the kids you know you know a dunkle like when your uncle becomes your dad and it's not weird at all so for our list we need to put dave as the new header position and because this is a computer and it can't do anything that we don't tell it to do we need to implement some functions let's call it insert new header and this is going to fall under our insertion algorithm we need to know how to insert elements into the list and not only that we have to tell it where to insert for davis the new head we are going to put him at the front of the list so for our function apart from self we need new data or information to be added to the parameter since we are adding a new name our new name is our new node so we will need our node class remember the nodes are our family members then all we need to do is assign him as the next new node to the self.head and then assign yourself.head to the new node let's traverse the list now oh boy bob is still in the picture and you know what amy can't have her new hubby under the same roof as her ex that is just not gonna work this is a little two backwoods so bob needs to go go creating our new header simply pushed all our nodes down so we need to get bob out of there let's create a function that deletes a node however we can't just delete some rando node we have to tell our computer where bob the node is in the first place this means we have to search our family list so let's create a search search function with one parameter x see what i did there pretty clever we need to know if bob is even in there to delete so in order to search we need to start at the beginning of the list let's create a temp variable assigned to the self.head and make a while loop that will traverse as long as that list or header isn't empty if any node or temp node isn't equal to x or whatever it is we're searching for we want to return true or else return false then we need to assign our temp to the next node because in a while loop it will need to continue until the node is not is none then it will return our pool great let's find out if bob is in there by printing our search function uh oh it's true bob's still there and he's giving amy a hard time about leaving let's help her out and create a delete function this is going to be similar to our other functions where we need to put our data in the parameter and begin at the head of our list we need our if else statements and we will and we will say bob isn't there then tell us and if he is let's kick him out we do this by changing the pointers from the previous node and pointing it to the node after bob so in essence we're skipping over bob but watch what happens when we try to try to delete amy bob will come back why does this happen because our list has four nodes as created here and those nodes will always be there unless we go in and manually delete the object itself so far we've traversed our list searched our list inserted a new header deleted a node and last but not least we're going to delete our tail yep that would be poor jenny she's had enough of these adult shenanigans and she's out of here heading to new york to become the greatest fashion editor that vogue has ever known she's ambitious okay we started the head and as long as the temp dot next next is not none our pointer is two nodes ahead we make our temp the next node and set it to none voila best of luck jenny so there you have it some very basic foundational algorithms for linked lists which in itself is a complicated subject but if you get these classical concepts down solid it becomes easier and easier to build up from on your own once you're more comfortable with singly linked lists try to challenge yourself with doubly linked lists with pointers that point back who knows maybe bob will shape up and amy will go or point get it back to bob for our mind breakers section in data structures we're going to be looking at hash tables right off the rib i'm going to tell you the key phrases or terms you need to be familiar with when it comes to hash tables associative arrays hash functions key value pairs collision and chaining a hash table consists of an array of pockets or buckets where each stores a key value pair in order to locate the pocket where a key value pair should be stored the key is passed through a hashing function this function returns an integer which is used as the pairs index in the array of buckets when we want to retrieve a key value pair we supply the key to the same hashing function receive its index and use the index to find it in the array associative arrays can be implemented with many different underlying data structures and it refers to an array with strings as an index rather than storing element values in a strict linear index order this stores them in combination with key values multiple indices are used to access values in a multi-dimensional array which contains one or more arrays a non-performant one can be implemented by simply storing items in an array and iterating through the array when searching remember the wallet with lots of cash associative arrays and hash tables are often confused because associative arrays are so often implemented as hash tables according to wikipedia a hash table uses a hash function to compute an index also called a hash code into arrays of buckets or slots from which the desired value can be found during lookup the key is hashed and the resulting hash indicates where the corresponding value is stored in many situations hash tables turn out to be on average more efficient than search trees or any other table lookup structure for this reason they are widely used in many kinds of computer software particularly for associative arrays database indexes caches and sets to summarize we can use hash tables to store retrieve and delete data uniquely based on their unique key the most valuable aspect of a hash table over other abstract data structures is its speed to perform insertion deletion and search operations hash tables can do all of them in constant time for those unfamiliar with time complexity big o notation constant time is the fastest possible time complexity hash tables can perform nearly all methods except list very fast in o b o one time hash tables have to support three functions insert for key value get key or delete a key collision happens when there could possibly be two or more pieces of data in data set x that will hash to the same integer and data set y this means that whenever two keys have the same hash value it's considered a collision what should our hash table do if it just wrote the data into the location anyway we would be losing the object that is already stored under a different key ideally we want our hash values to be evenly distributed among our buckets as possible to take full advantage of each bucket and avoid collisions but generally speaking this is unlikely so this is where two common methods to solve are employed separate chaining using linked lists or binary search trees for example and local addressing using linear probing with some basic concepts of hash tables under your belt a fun exercise or challenge that you can try would be pattern matching on strings using the robin carp algorithm yes it's fairly advanced and yes this is our mind breaker problem but shoot for the stars people who knows you might just surprise yourself what have we learned what have we learned from lesson two okay we touched on a one-dimensional raise as our data structure of choice at our basic level we looked at contiguous versus non-contiguous different ways to search linear binary and we sort bubble insert and even talked about an array with more than one dimension we learned about dunkles no no no no we learned about link list by creating a family of sorts to demonstrate how to traverse search add and delete headers nodes tails on linked lists some of the most common operations used that every programmer should be familiar with we broke our heads on hash tables and hashing functions by going over what they are and what can happen when problems arise from colliding data within a bucket ultimately hash tables are for storing retrieving and deleting data based on key value pairs and on average are more efficient than search trees or any other table lookup structure i learned about the divide and conquer concept from a very early age it was traumatizing actually you see my brother and i used to fight all the time when we'd swim in the pool and finally one day our mom came and said to us just divide it in half and you stand once and you stay on another side my brother picked the top half so yeah divide and conquer i drowned but only momentarily in programming when we cross paths with programs that are too complicated to be solved all at once we can implement methods to break them down into smaller pieces and if we solve all the smaller pieces we are in essence dividing out the big solving the small and in the end this makes our lives so much easier a divide and conquer algorithm paradigm can solve a large problem by recursively breaking it down into smaller sub-problems until they become simple enough to be solved directly it could be compared to the age-old problem of swallowing an elephant can't do that so we devour it one bite at a time actually it's more of a solution of three bytes dividing solving and then merging it all back together unfortunately since divide and conquer algorithms are usually implemented recursively this means they require additional memory allocation and without sufficient memory a stack overflow error can or will occur this is due to the overhead of the repeated subroutine calls along with storing the call stack the state of each point in the recursion and that can outweigh advantages of any approach on the flip side if the dnc solutions are implemented by a non-recursive algorithm that stores the partial sub problems in some explicit data structure like a stack queue or priority queue it can allow more freedom in the choice of the sub-problem that is to be solved next a feature that is important in some applications including breath first recursion and the branch and brown branch and bound method for function optimization second even if a solution to the full problem is already known like sorting a brute force comparison of all elements with one another divide and conquer can substantially reduce computational cost lower cost means higher efficiency third explicitly recursive subdivision can have benefits to the temporary memory of the computer not the main hard drive which is called a cache using divide and conquer one can even design an algorithm to use all levels of the cache hierarchy in such a way as to have an algorithm that is optimally cached oblivious which means operating independently from its temporary memory storage this approach has been successfully applied to many problems including matrix multiplication which we're going to get into in just a few minutes so let's get into it and start at the base level algorithm for divide and conquer the merge sort conceptually merge sort works as follows divide the unsorted list into two sub lists about half the size sort each of the two sub lists merge the two sorted sublists back into one sorted list invented by john von neumann in 1945 the merger sort is an efficient general all-purpose and comparison-based sorting algorithm an example of merge sort would be to first divide the list into the smallest unit one element this becomes a list itself then compare each element which is a list itself remember with the adjacent list to sort and merge them done repetitively the end results in the elements sorted and merged i understand that can be a little bit confusing but let's think of it in this way say we have two different lists of numbers list a and list b and then we'll have an empty list we'll call c lists a and b are ordered from least to greatest and what we would do is repeatedly compare least value min of a to the least value min of b and remove the lesser value and then append that value into c when one list is exhausted we append the the remaining items into c they're already started so we're good there then we just return list c which is sorted we're systematically merging a and b together and appending it into c but for this lesson and although you can append or extend on an empty list to see we're going to swap our elements i just wanted to share a very simplistic explanation for that hoping that would give you an idea of the concept typically creating more space for an empty list or temporary list for storage isn't always the best approach we want we want to do our best to optimize our program if we can let's head into our ides and write our programs the best way to see the different methods of the merge store and their efficiencies is to compare four programs that i have here some things i wrote myself some things i borrowed we're going to look at a single array of 10 integers and just sort it by brute force this means that the program takes the first number in index position 0 and compares it to each and every number in the array if it's the lowest it gets reassigned at the first position then it moves to the next number and does the same thing it gets compared to each and every integer and the lowest number gets reassigned at index position one and so on and so forth for this little iterative program it's 168 iterations or cycles to get an output and that's just for 10 elements keep that in mind as we look at the differences within the merge sort our first real program for the merge sort is about as simple as we can get it we're starting with an array that is already split in half and sorted the program we're looking at right now won't work properly if our two halves are not already sorted why because ultimately this is our divide and conquer algorithm we are dividing our array into two parts and conquering both halves separately by sorting them and then merging them back together remember just a few minutes ago when we talked about list a list b and empty list c this program is comparing each number at each index position determining which is lower and then popping it out and then appending it into our empty list c and then just in case either list is longer than the other that leftover portion just gets added to c and since it's already sorted we'll have no problems there this is a neat little non-recursive merge sort for an array that has a small amount of elements and is already divided in half however since this isn't a perfect world and you'll be more than likely asked to write a program for an array that isn't divided and sorted beforehand we're going to have to rewrite this so here's our big dilemma do we sort our halves recursively or do we sort them iteratively or do we sort our halves using python's built-in feature called sort or sorted let's shoot for sorting our halves recursively this is what is called the top-down method what it does is repeatedly produce sub-lists half by half by half until there's only one sub-list or one element remaining which becomes a list all in itself a list of one element how many of you are willing to but it's the optimal or optimized method well it's not once we have our have sorted we continue on very much like before we compare each element and append it into our empty list now if recursion isn't the optimal method then it must be iteration right well yes mostly this is the bottom up method think of the top down just in reverse it starts at one element then two elements then four remember that very first brute force method of sorting a list we can do that after we divide the array into two parts and then merge it all back together hmm let's see what happens when we run it in something like leeco that'll really put it to the test okay well that didn't go as planned but it does work it's just bad on really big arrays so what is the bust using python's awesome sort or sorted feature of course well splitter array have python sorted for us and the rest is good to go with our 10 element array it's only 34 steps to completion compare that to our brute force program no dividing no conquering with almost 170 iterations our bottom up iterative method is smoking check it in leak code talk about optimization now let's move out into deeper waters with some matrix multiplication matrix multiplication is wild y'all but it is a fundamental concept to understanding computing among the most common tools in electrical engineering and computer science are rectangular grids of numbers known as matrices the numbers in a matrix can represent data and they can also represent mathematical equations in many time sensitive engineering applications multiplying matrices can give a quick but good approximations of much more complicated calculations did you know that one of the areas of computer science in which matrix multiplication is particularly useful is graphics it's crazy to think that a digital image is basically a matrix with rows and columns of another matrix corresponding to rows and columns of pixels and the numerical entries correspond to a pixel color value decoding digital video for instance requires matrix multiplication and did you know that mit researchers were able to build one of the first tips to implement a high efficiency video coding standard for ultra high definition tvs partly because of patterns they discerned in the matrices pretty cool huh so the dimensions are listed as rows and columns or in many equations n times m where n represents the number of rows and n represents the number of columns be careful that you that you know the difference between rows and columns and don't mix them up rows go across columns go up and down to see how matrices are multiplied check out this graphic that shows how it all works we multiply each element in the row by each element in the column and then we add them together in order to code this we'll start with the naive method it's not too bad to learn however just know that it can get very expensive as we increase the size of our matrices for larger matrix operations we wouldn't want to use too many nested loops because it could really start bogging down ideally we would want to use optimized software packages like numpy numpy should be the go-to which is insanely faster and easy too but before we start cheating we really need to examine what's going on underneath the hood like how a program is created that multiplies matrices in python because if we can get a really good handle on this we'll get a better handle on the mind breaker okay so what we're doing is basically creating a calculator in python that multiplies matrices and you might be wondering hey what's the deal here how is this part of dividing and conquering algorithms we're definitely going to get into that but this is all preparation for the mind breaker lesson you'll need this under your belt first plus it's a really good foray into matrices which is one of the most well studied problems in numerical computing today so yeah let's dig in we'll create two matrices x and y and to store the results of our products we'll create an empty matrix we'll call result the most popular method in my humble opinion is to use nested loops to iterate over the rows and columns and implement the results into our matrix of zeros using an addition operator that adds our product of the rows and the columns of x and y we could do this recursively sure but it wouldn't really be advantageous the goal is to help you understand the logic behind matrix multiplication so we can move on to our mind breaker lesson strassen's algorithm for matrix multiplication volker strassen is a german mathematician who made important contributions to the analysis of algorithms and has received many awards over his lifetime he's still alive by the way he began his research as a probabilist his 1964 paper an invariance principle for the law of the iterated logarithm defined a functional form of the law of the iterated logarithm showing a form of scale scale and variance in random walks this result now known as strassen's environments principle or strassen's law of the iterated logarithm has been highly cited and led to the 1966 presentation at the international congress of mathematicians now if you know what an iterative logarithm is that shows a form of scale and variance in random walks or in variance principles in general well then please by all means invite us to your latest book site but if you're a mere mortal like the rest of us hold on to your hats because that was only the beginning for strassen three years later strassen shifted his research efforts toward the analysis of algorithms with a paper on the gaussian elimination come on everybody knows what the gaussian elimination is and there in that paper he introduced the first algorithm for performing matrix matrix multiplication faster than the o and three time bound that would result from the naive method this means that his algorithm is like the best of the best when it comes to computing the product of two two by two matrices there is no formula that uses fewer than seven multiplications how he did it he doesn't say maybe somebody flew into german can call him up and ask him like what kind of person do you have to be to discover some great mathematical algorithm like what are your hobbies can we talk what do you do on the weekends i mean at this point at the time of recording this he's 85 so i don't know he probably just relaxes his brain muscles for the most part i mean i know i would they're probably still smoking anyway not to knock on this awesome person and as great as the algorithm is and the contribution it's made to matrix multiplication unfortunately it's too numerically unstable for some applications in practice fast matrix multiplication implementation for dense matrices use strawson's algorithm for matrix sizes above a breaking point then they switch to a simpler method once the subproblem size reduces to below the breakover see divide and conquer in any event the publication of its algorithm did result in much more research about multi matrix multiplication that led to faster approaches it opened the door to bigger and greater things which is pretty neat okay now that we've got that all under our belt let's take a deep dive into what the algorithm really does just a few minutes ago we saw the naive method so you should be somewhat familiar with it in two two by two matrices we have eight multiplications with stress since we can get this down to seven with basic mathematical formulas and i've gotten it all written out so you can see it all work in a program let's take a peek we're still going to keep our 2x2 matrices for simplicity yay but we're going to look at our famous or infamous methods of optimization iteration and recursion for strassen's algorithm we're dividing our matrices not by halves but by quarters and then we'll solve or conquer each sub-matrix to solve the entire problem in our iterative method we're breaking down the two matrices all the way down to each individual square or quadrant we'll name our passes p and simply plug in our mathematical formula used to compute our multiplication and addition on the quadrants now although we called numpy cheating we're going to implement it here just for a little bit of ease by instead creating a result matrix of zeros we're going to make a new matrix called c and number each quadrant of c as c1 c2 c3 and c4 for each quadrant we plug in our equations for our passes these equations are our conquered solutions to the quadrants lastly we use numpy to implement a new matrix by using the np dot array feature and input our four c quadrants pretty cool the recursive solution is very similar only we're recursively splitting the matrices into our quadrants and recursively computing our seven passes what did we learn what did we learn we learned that the merge store is an efficient general purpose sort that can be implemented in several ways including the top-down and bottom-up approach we learned that matrix multiplication is used in simple graphics all the way up to hd tvs and we wrote our own python program to calculate two matrices we looked at strassen's algorithm for matrix multiplication and learned that he discovered how to get the lowest amount of calculations possible for multiplying two matrices to this day computational efficiency of matrix multiplication is still a hot topic in theoretical computer science apparently if you google greediest person a real live person does pop up can you imagine like googling the worst person in the world and your face gets blasted on the screen now i'm not going to show who this person is because i don't know who he is and it's not really important just kind of funny but it does tie in with our algorithm what is greed to you like what is a greedy approach say your beautiful old granny baked a pie for your family and uncle bob shows up you know amy's ex-husband and he takes the biggest piece of pie for himself that'd be pretty greedy wouldn't it by him eating the largest portion that sure would make the pie easier to finish wouldn't it it wouldn't be great for everyone else or their rumbling tummies but by taking the biggest portion and leaving just little portions to take care of that's sort of the concept behind the algorithm the paradigm behind the green concept is that it builds up a solution piece by piece always choosing the next piece that offers the mo the obvious and most immediate benefit by using several iterations and by obtaining the best result at a certain iteration the results should be computed in other words it follows the problem-solving method of making the locally optimum choice at each stage with the hope of finding the global optimum something to keep in mind though is that they do not consistently find the globally optimum solution because generally speaking they don't operate exhaustively on all the data nevertheless they are useful because they are quick and often give good approximations to the optimum if a greedy algorithm can be proven to yield the global optimum for a given problem class it typically becomes the method of choice a really fun problem that we can lead off with is called assign mice to holes what we need to do is put every mouse to its nearest hole to minimize the time how can we do that and what's the optimal approach what would you think about sorting the positions of the mice and holes first that would be pretty greedy of us wouldn't it this allows us to put a particular mouse closest to the corresponding hole in the holes list we can then find the maximum difference between the mice and the corresponding hole position to determine how much time it will take to get there now does being greedy always equate to maximum of something regarding problem solutions not necessarily don't let that word fool you for this problem we're finding the maximum difference hint subtraction to find the minimum amount of time it takes for our mice to travel as a quick side note another problem that i would encourage you to learn on your own a triple dog dare you is the kids with greatest candies problem using the greedy approach this is considered an easy problem so don't worry too much the problem is similar to this one by asking for the distribution of the minimum number of candies that can be given to a kid and then seeing which kid will contain the maximum number of candies so again the greedy approach can be tricky we have to carefully decipher word usages to make sure we're solving the problem accurately but with that being said the assigned mice to holes problem will help set you on some solid ground and make it a bit easier to work on other challenges now if you do decide to tackle the candy problem and i do highly encourage you to do that i'll give you a little hint the brute force method would be a one by one distribution of candies to each child until the condition satisfies and yet the greedy way would be to traverse the array just twice from beginning to end and back again by greedily determining the minimum number of candies required by each child as a personal challenge to yourself work out how that could be written it'll be fun let's head over to our ides and slam dunk some mice into holes okay we need to get our mice into holes and we have to do it quickly but first things first we have to make sure that there are an equal amount of holes to our mice this is our base now we initialize our greedy approach by sorting the mice first then we create a variable to store our maximum difference and loop through the length of our mice in our if statement we create the condition that if the position of the mouse subtracted from the position of the hole is greater than the maximum difference our max diff variable gets reassigned to hold that difference lastly we just return the largest difference our last mouse gets to the hole in x amount of time by sorting our two lists first this puts us at an advantage to finding the minimum time faster our code is concise short and along with python's sort feature we are really rocking it out next up is kind of a doozy the fractional knapsack a pretty well known problem for our greedy algorithm if you were a little bored with our mice and no holes you won't be with the knapsack for a step up on the greedy method let's take a peek into what's called the fractional knapsack now this is intense fractional knapsack freshness people okay so this problem on the surface seems really complicated but it's only as complicated as you want to make it you know what i mean so let's not make it complicated okay so just so what you can do is just envision me it's the apocalypse it's the end of the world wait maybe it's just a monday food is scarce people are bartering water is practically non-existent so i need to conserve every bit of energy i have to walk to the market and try to trade what i have to stay alive okay now i have five objects i can take our knapsack or bag is our container for holding our objects think of our array as a storage device and each object is worth something some are worth more than others and each object weighs something some objects way more than others the key to this problem is to make the right decision on which objects are going to bring me the most profit i mean i gotta know i have animals to feed that haven't become somebody else's dinner you know while at the same time they can't be too heavy that i can't carry in my container because this is crucial i might have to make a decision based on its object the weight of the object not necessarily its profit if i want to make it back alive from zombies r us now the real kick in the head on solving this lies in that little teeny tiny word fractional this means that my objects can be divided if they are divisible say one of my objects contains three chapsticks i can divide that object and bring only two chapsticks if it will make a difference who knows cat fat might be a real hot commodity remember in that book of eli movie where he killed that cat well it was for food but he also made chapstick out of it not saying my chapstick would be that it'd probably be made from beeswax or something don't forget i'm risking my brains to go to the market to feed my animals in the first place so no cancel be harmed here no siree bob okay wow that was a really long way off the beaten path if let's get back to the problem so the weight is divisible and it would help to best fit how many profitable objects in my backpack then we should do that why we need to fill to the brim in our fixed size knapsack the most valuable items that we are able to carry for the steps of our algorithm keep in mind we are given weights and values of n items and we need to put these items in a knapsack of capacity w to get the maximum total value in the knapsack by the way in the o1 knapsack problem a whole different problem is one where we're not allowed to break items down or divide them using fractions we either take the whole item or don't take it but in this problem fractions can be used a really efficient solution to this problem is to use the greedy approach as opposed to brute force remember brute force is calculating every possible solution and is typically computationally expensive meaning it takes a lot of runtime and memory space the basic idea is to calculate the ratio of value slash weight for each item and sort the item on the basis of this ratio then take the item with the highest ratio greedy remember and add them until we can't add the next item as a whole and at the end add the next item as much as we can this will generally always be the optimal solution to this problem you'll see what i mean when we get into our ides and start coding it so let's get to work okay we'll define our functions with three parameters we need our values our weights and the capacity of the bag now we have our created variables here but i implemented print calls to show you what's going on we have our items a range of zero to four equaling five items the ratios are values divided by weight using floor division to eliminate floats list comprehension is good to use when you can then we'll sort our ratios in decreasing order lastly the ratios index positions are printed here to show the to show you the order that it will be computed in i'm going to take out the third variable here it as it won't be needed i just wanted to show you how it matches up with its index position our ratios being sorted is taken care of in the items.sort line we need a counter to keep a running tally of our max value we will create a list that is the length of our values we'll call fractions that will contain all zeros i'll tell you why we're doing this at the end of the program now it's time to run our for loop we'll iterate over our items and if the weight of our item is less than capacity it will add a one to our fractions list of zeros at its index position then we'll add that value to our max value and subtract the weight from our capacity now when all those conditions satisfy and we hit our else we take the fractional difference of our last item and add it to our max value then we return our maximum value which is 500 now here's the key you might be wondering this we have an item that weighs a 10 and it's worth 90. at a capacity of 150 we could put 15 of these items into our bag for a value of 15 times 90 equaling 1350. why can't we just do that we can't do that because what we're looking at today is what is called the bounded knapsack problem or bkp for short the scenario i just painted a 15 15 of the same items would be allowing for copies of that item called the called the ukp type short for unbounded knapsack problem and that's a whole other ball of wax kids this is why we set up the fractions list containing nothing but zeros this is important because it's putting in our highest values first and then taking a fraction of the last item from maximum capacity in our bag each item counts as one in our fractions list until every zero is turned into a one but our very last item to change from zero to one is that special one that gets the remaining capacity divided by the weight that figure gets multiplied to our value and then added to our max value in the case of our program that ends up being 28 and a half percent and what's 28 and a half percent of 140 is the value of 40 that puts us up to 500. sorting our ratios in decreasing order gives us the optimal or best approach this is considered greedy as you are placing items with the largest ratios into our bag first now you can sort by price and you can sort by weight as those are considered methods and they will get you close to 500 but it's just not 500. and we should always strive for the best method algorithmically hopefully you now understand a pretty well-known problem not only in logistics but other fields as well like manufacturing and finance it's all about optimization what is the optimal way to get the items of highest value into a bag that you can reasonably carry and this greedy concept can be carried out in other reasonable scenarios as well with the goal of calculating solutions whether that be approximations or actual figures let's move on to our last section with good old fibonacci in our mind breaker episode we're going to talk about another well-known mathematician leonardo alpisa aka fibonacci considered to be the most talented western mathematician of the middle ages according to wikipedia he wrote the libre abachi the book of calculation and is it is a historic 13th century latin manuscript on arithmetic which includes the posing and solving of a problem involving the population growth of rabbits based on idealized assumptions the solution generate generation by generation of rabbit offspring was a sequence of numbers later known as the famous fibonacci numbers or fibonacci sequence in a little side compartment of mathematics however what we are going to talk about today is the greedy algorithm for egyptian fractions first described by fibonacci for transforming rational numbers into egyptian fractions an egyptian fraction is a representation of an irreducible fraction as a sum of distinct unit fractions and this means that every positive fraction can be represented as a sum of unique unit fractions a fraction is a unit fraction if the numerator is 1 and the denominator is a positive integer for example 1 3 is a unit fraction to take a closer look we'll reduce a fraction of 7 14 in a pizza example the egyptian way in order to generate egyptian fractions we will utilize the greedy algorithm because although possible to use brute force search algorithms to find it it would be extremely inefficient remember 3d algorithms are for optimizing our problems we always want to know and understand the optimal solution as a side note although fibonacci's greedy algorithm isn't the only way to efficiently solve our problem he's our focus for today let's look at a program so yeah i got this program here we're importing some tools scroll down some we got three functions going strong a main a validate a converting function we got some wrappers nestled functions we got some yields which means it's a generator not even gonna touch that this is a lot of code heading into nearly 50 lines is it good yes hard to write depends but if you're looking for kindergarten style programming you come to the right place i totally dumbed it down to show you the mechanics not that you're dumb i love simple make it plain am i right so we have this pie remember that bob took a big old chunk of let's change that to a pizza since it kind of goes with our theme of leonardo of pizza or fibonacci so to get this real simple we'll write a function that takes our numerator and our denominator we'll implement an empty list for our denominators we won't need one for our numerators because we already know that they're going to be ones then we write our while loop that as long as our numerator isn't zero we can create a variable that stores our quotient using the math dot seal that will round it up this is important for when we have a number that's a float lower than one next we reassign our numerator to be the product of the quotient and the difference of our denominator subtracted from our numerator then we reassign our denominator to be multiplied by our quotient or x for our fraction of 7 12 this is going to put a 2 and a 12 into our egypt list and those two numbers are our lowest common denominators or lcd for short all that's left to do now is put a 1 over those lcds as those are our egyptian fractions and that can be accomplished a few ways but basically i just implemented some good old-fashioned string formatting by iterating over our egypt list of denominators and adding them to an empty string once we do that we just return it the caveat to this really simple program is that it probably doesn't work for really complex fractions or when the numerator is larger than the denominator but this is a good exercise in understanding how to break down a fraction the egyptian way ultimately all of this runs more along the line of recreational mathematics however there are still open problems involving egyptian fractions that have yet to be solved or proved who knows maybe you can be the next mathematical genius to solve one of them so what did we learn about greedy algorithms we learned optimization of solutions to problems using the greedy algorithm provided in our example with the mice in the holes it's like a delicious big pie where you take the biggest slice out first this makes the pie easier to finish we learned that chapstick made from cats is a hot commodity in the apocalypse kidding we walk through the fractional nap stack problem where we find the largest value of an item in a way to maximize the total value within the knapsack we want to avoid brute force here because finding all the possible subsets would take too much time we learned that fibonacci was the first to describe an algorithm for transforming rational numbers into egyptian fractions and it is where we really take the largest unit fraction we can and then and then repeat that on the remainder although this is purely mathematics it's still a good representation of the greedy algorithm what do you think when you hear the word dynamic well if you're a programmer or an aspiring programmer you may not know what to think what does being dynamic really mean for once in my life it would be awesome to be described as dynamic because when we talk about a dynamic person it means energetic spirited active lively zestful vital vigorous maybe this is why when it comes to computer science students can become intimidated with the subject of dynamic programming ultimately the word dynamic means a process or system characterized by constant change activity or progress with its roots in greek to the word dynamous meaning power hint dynamite so it's no wonder we subconsciously shy away from it because it just sounds like a handful it dangerous pretty wild how words and their meanings really deep down can make us feel a certain way you know but i'm here to help you out and put you at ease and tell you a little secret they introduce dynamic programming to children okay maybe not children children but like upper elementary middle schoolers kids like that so if they can learn about it so can you but first we have to unplug our preconditioned mentality if you will to think and believe that anything in computer science is too hard it's not it's all just one big treasure hunt to find information and knowledge that best suits your intellectual filter not all people teach all things the same way not all people learn information or absorb knowledge the same way so let's take a deep breath and step back to look at the different dynamics that are out there that's a long list for us there should only be two that should really mean something that's dynamic programming languages and dynamic programming as a methodology you can have programming languages that are either dynamic or static python is dynamic by the way and then you have programming methodologies that are concerned with analyzing a problem by developing algorithms based on modern programming techniques in the world of dynamic programming dp is used when the solution to a problem can be viewed as a result of a sequence of decisions with the intended outcome of reducing run time and any implementation that can make a solution more efficient is considered optimizing it in an early lesson we saw several problems that can be viewed in this way i.e the knapsack problem essentially the difference between the greedy method and dp is that in the greedy method only one decision sequence is ever generated and in dp many decision sequences may be generated however sequences containing sub-optimal sub-sequences cannot be optimal and as far as possible will not be generated and this is the key that helps make a reduced run time optimal substructure means that optimal solutions of subproblems can be used to find the optimal solutions of the overall problem in dp this is called the principle of optimality the principle of optimality as relayed by richard bellman who introduced dynamic programming in 1953 states that an optimal policy has the property that whatever the initial state and initial decision are the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision so what does that mean in general we can solve a problem with optimal substructure by doing three things breaking the problem down into smaller sub problems solving the sub problems recursively and then using the optimal solutions to construct an optimal solution for the original problem but there's an issue with this that we need to be aware of and that is sometimes when we do this we can get overlapping subproblems we want to avoid that for instance in the fibonacci sequence f3 equals f1 plus f2 and f4 equals f2 plus f3 computing each number involves computing f2 because both f3 and f4 are needed to compute f5 a naive approach to computing f5 may end up computing f2 twice or more in order to avoid this we instead save or store the solutions to problems we have already solved in dynamic programming there are three basic methods we have recursion top down with memoization and bottom up with tabulation and although we could have chosen the well-worn path of the fibonacci sequence to do this oh no i'm encouraging you to step out and think bigger have confidence you are smart and you can do big things so let's get ugly with it in our first lesson what are ugly numbers and why do we call them ugly and what do we do with them to answer the first question i saw this and i think it will give you a big hint okay that's funny and i wish i could have been the one to think it up but alas i was too slow to the game darn i stumbled upon a pretty funny thread about ugly numbers and i stole that so shh don't tell on me but the long and short of it is this to check if a number is ugly in the first place we divide the number by the greatest divisible powers of two three and five and if the number becomes one then it's an ugly number otherwise it's not we're employing our power of prime factorization we learned that way back in the fifth grade so that tells me that you probably don't remember but it'll all come back to you today the sequence of one to six eight nine 10 12 15 shows the first 11 ugly numbers by convention one is included all right now that you got that under your belt let's tackle the problem of finding the nth ugly number can we find the hundredth ugly number would you believe that if we crafted a program using brute force it would be over a thousand iterations for the hundredth number i think i broke my visualizer trying to run it and we don't want to break things or make our computers smoke out the back or anything like that so it's time to incorporate our spirited energized vigorous programming that's like dinomite but not a lot of dynamite we'll start small and just find the 15th ugly number how does that sound since we're going big and not going home we're gonna shoot for the bottom up method for a dynamic approach if we use a pretty simple iterative with some recursion solution we're still looking at nearly 600 steps or iterations in the program to get our results as compared to just a little over a hundred steps for the bottom-up dynamic programming method talk about optimization if we use simple iteration and continuously loop through all the numbers to find whether each number is ugly or not it can really bog down when we get to larger numbers with dynamic programming instead of starting from the head we start from the bottom we're also using a table to help us store the values for easy access if we look at the ugly number sequence 1 to 6 8 9 10 12 15 we can see that it can be further divided into sub sequences of 2 3 and 5. and these subsequences themselves are ugly numbers therefore we take every ugly number from the above sequences and choose the smallest ugly number in every step to make sure that we don't miss any number in between let's head into our ides okay so if we're looking for the nth ugly number in a sequence we have to write a function that will tell us if our numbers can be evenly divided in the first place meaning no remainder x modulo y equaling 0 gives us what we need to prove that if there is a remainder we'll just write it to return our original number for our second step before we can find the nth ugly number position we have to check if it's an ugly number we can do this recursively by going back to our first function the successive division what this does is plug in the number we're checking and successively or successfully if you want to think of it that way dividing it by two three and five if our number is successfully divided by two three and five with no remainder we have an ugly number on our hands let's check a six it's true six is ugly okay so we have what we need to find our nth number six is fairly easy since every number before it is ugly so the sixth ugly number is six but what's the 15th number well let's write a program to find out essentially what we're doing is merely creating a counter coupled with recursively calling back our ugly check function we'll create two variables one for i to iterate up our sequence and one for our counter and then we just incorporate a while loop to say as long as our number is greater than our counter we'll add one to i heading up our number sequence and if that number within our while loop is ugly add a 1 to our counter then we just return i so what's our 15th ugly number it's 24. now if we run this program we have a lot of running back in our recursive calls for every number in our sequence and that's a lot of running back with 600 steps or iterations that's a lot considering with dp we can write a much more efficient program that cuts all those iterations by nearly 80 percent let's check out the difference the first major thing we can do is eliminate those three functions within our original program we won't need those remember when i said we were going to implement a table to store information well that's what we're doing then we'll start our first position in that table or in other words a dynamic programming array to store the ugly numbers next set pointers for our multiples of 2 3 and 5 and we can do this all in one line which is pretty cool you'll see how this works as we get deeper into the program here's our multiples of two three and five in their own variables after that we loop from one to n at each step and we find the minimum ugly number out of three multiples and store it in our dp array we're also increasing the pointer for the number whose multiple has been added and replace it by its next multiple so suppose a multiple of two has been added to the array we increase twos pointer by one and multiply the previous multiple to two to get the next multiple and so on and so forth for other numbers as well and this way starting from the base case we generate all the ugly numbers and then apply dynamic programming to store the numbers in the array until we get the nth ugly number this approach is way better than the previous one because instead of checking all the numbers for being ugly we just used the previous ugly numbers to generate new ones watch how this runs through the program this really is the better way very efficient now let's put this knowledge to good use on a very famous problem called the traveling salesman problem if you haven't heard of this yet you will best to get it in your brain bucket now rather than later the traveling salesman problem is one of the most intensely studied and famous problems in computational mathematics with its main main really main focus on optimization so much research has gone into this challenge of finding the cheapest shortest fastest route in the visitation of locations by this dashingly handsome or beautiful salesperson this person starts in their home city travels around and returns to their starting point most easily expressed in a graph the general form of the tsp traveling salesperson appears to have been first studied by mathematicians during the 1930s in vienna and at harvard notably by karl menger menger defines the problem considers the brute force algorithm and observes the non-optimality of the nearest neighbor heuristic using the mailman as an example now the order in which the person travels isn't cared about as long as he visits each one once during his trip and finishes where he was at the first in the most cost effective way but there's a catch maybe the salesman needs to take a plane to one of the cities and this will cost him a pretty penny maybe he can walk to one of his cities therefore making it a free trip the cost associated with the trip describes how difficult it is to to traverse the journey or graph for us computer scientists whether that's money or time or distance required to complete the traversal the salesman ideally wants to keep every cost as low as possible he wants the cheapest fastest shortest route wouldn't you the easiest and most expensive solution is to simply try all the permutations and then see which one is cheapest using brute force the problem with this though is that for n cities you have n minus 1 factorial possibilities this means that just for 10 cities there are over 180 000 combinations to try since the start city is defined there could be permutations on the remaining nine and at 20 cities this just becomes simply infeasible this is why four is often used in the majority of problems as you'll quite often see in the 4x4 matrices keeping it small makes it much more manageable and understandable which is good the awesome news for us is that the problem is solvable but keep in mind that there can also be solutions to the problems that are approximations or commonly called heuristic algorithms if that's what is being asked for according to wikipedia even though the problem is computationally difficult many heuristics and exact algorithms are known so that some instances with tens of thousands of cities can be solved and even problems with millions of cities can be approximated within a fraction of one percent wow so let's get to the nitty gritty and look at our steps number one consider city one as the starting and ending point number two generate all n one factorial permutations of cities three calculate cost of every permutation and keep track of minimum cost permutation four return the permutation with minimum cost it's not hard to see how this could get computationally expensive in a very short amount of time so we will move into the optimize method right away for our savings and our sanity the goal is to break this problem down into the smallest pieces possible and then solve solve solve let's get into it because permutations are a big part of the tsp problem we're going to import intertools permutations to make our lives a whole lot easier it's totally okay for this one we'll implement a variable that we'll call v short for vertices and vertices are the dots on our graph think of our sales person traveling to four cities on our graph a single dot is called a vertex on our graph and they link or connect to one another now we can move on to implementing our function call here with two parameters our graph that will be a four by four matrix and s is going to be our counter that will need to calculate the sum of our path i'll explain this a little bit deeper at the end of the program we'll create an empty list for our vertices to be stored in and we'll call this vertex just to make it plain this is going to tell us the best route for our rows in the graph again this is going to be come real clear at the end of the program so hold on to yourselves then we iterate over our range of v and if the index does not equal us which is zero we append it to our empty vertex list this is going to show us where our salesperson is traveling within the graph but here's a little catch that we need to be aware of check out our graph see those trails of zeros we have no need to calculate those so when we append our indices to our vertex list we're only producing three integers one two and three next we create another empty list that we'll call min path we need to know the best route so this will store our lowest combination of vertices within the graph then we create a variable that we'll call next permutation and we'll implement the inter tools permutations module here to give us all the combinations of the vertices for one two and three since we have three numbers we know that the amount of permutations will be six then we iterate over all those combinations and create a counter that we'll call current pathway we'll reassign our s to a variable we'll call k and k will represent the row in our graph and as we iterate over our indices within our permutations by using j this becomes our columns i know this sounds i know this all sounds really confusing but stay with me when we add the k and j of our graph to our current pathway look what prints out this is calculating all the paths within our graph and adding them together pretty cool isn't it next we reassign k to j and then use an addition operator to add the sums to our graph to the current pathway append them to our min pass hold them in a variable called x that's sorted and simply return the very first number in our sorted list which is our lowest number our shortest route on the graph to see how this travels on the graph watch this this is how it is adding up within our program hopefully you can see and understand how this is all working it sounds so much more complicated than it really is but it's only math we're simply calculating the paths of a matrix by pulling out all the combinations or permutations of the indices and returning the lowest number or lowest sum of the path it's not too bad my recommendation to you would be to create your own graph and then run it in the program once you do that map that course on paper or even whiteboard it to see it visually for our very last lesson today and not only for dp but all together i'm so sad to leave you so let's make this session a great one what we're doing for our mindbreaker sounds really intimidating but i can assure you that once we break this down you're gonna say wow that wasn't even that bad and then you can brag to all your friends and then they'll shun you for your genius but it'll be totally worth it i i mean because who needs friends am i right now your brain won't break too much if we take each word out and examine it first we have palindromic which is religious palindrome matrix we'll keep it low and slow with a 3x3 and then just paths which we're only going to go right and down only since we worked on a matrix in our last problem this should be old hat hopefully by now you have a decent handle on breaking down the problem into smaller ones called sub problems and solving them little by little in order to solve the whole tips for getting started on the palindromic matrix path problem would be to first know how to check whether a string is a palindrome or not in the first place you can use python's python has a little pip install program called palindrome that checks whether a string is pendulum or not but i do highly recommend you learn how to do this on your own because it will help with this problem the second tip would be knowing how to traverse a matrix going right and down only we're not going to get too crazy for our final lesson and just have some fun with it by printing our palindrome strings we're not going to return counts or find the longest because that might make some of us cry and there will be no crying today any tears that gets shed must be happy tears only whether that's joy at finishing this course or not seeing my face anymore tears of accomplishment are fine but no tears of sadness okay to keep it simple we'll start at ground zero and start with an empty three by three matrix and find all the unique paths what's really cool about this is that it's actually just a math problem what we'll do is create in our three by three by starting with a row of ones that we will build up from our bottom row and far right column will be ones and when we add their adjacent numbers together and build up we get a row of ones one one one at the bottom and then three two one in the middle and then six three one at the top if we return row zero that will give us six and that tells us that we have six unique paths in our matrix this will come in handy later when we implement this principle into our matrix of strings we can know that we will have six strings returned to us and all we need to do is check whether they're palindromes and print those out so we're not going to talk much if at all about the naive approach or brute force or whatever the difference is in optimization no let's part ways on a good note and have some fun with this i mean we walked through 14 other problems with multiple methods in a relatively short amount of time and here we are breaking our minds on palindromic matrix paths so yeah let's get straight to the optimum let's code the paths problem first shall we we'll start by creating our function with two parameters our row and our column we already know it's going to be a three by three then we create our dynamic programming array of all ones which you can envision as our bottom row of ones next we iterate over our rows in a for loop and then create another dp array which can be envisioned as an accumulative next row up in our matrix our original for loop is going to iterate three times 0 1 2 for each row in our matrix in a second for loop we now want to iterate from the bottom up and reassign our new row elements by adding one element to the one next to it going left we do this twice while in our final iteration it has accumulated each row to end with six three one we then reassign our original row as the final row and return the very first element which will be six our answer to the number of paths now this isn't super necessary but it will give you an idea of the path traversal within a three by three matrix and will give us a good launch point to moving up to a matrix consisting of letters we'll keep it in the realm of just two letters a and b and we'll write a very quick little program to see how many palindromes of a and b there are let's import intertools to help us and then create our rows and columns of letters a neat little feature of inter tools is product with an asterisk on our matrix this will print out every combination of letters in our matrix totaling 27. yes there will be duplicates here but it's nothing that python's set can't handle let's create an empty list called p1 and then iterate over our list of 27 tuples join them together to make it easy on the eyes and append them to our empty list then all that's left to do is check which ones are palindromes by making a new function plugging in our p1 create another empty list p2 and then iterating over a non-duplicate set of p1 incorporate an if statement is it a palindrome yes put it in our empty list then return it okay so far we've traversed a matrix in order to count the number of paths in it we created a three by three matrix of just two letters found every possible combination and created a function to pull the palindromes from it we are doing fabulously if you know how to count the paths of a matrix and find the palindromes in a matrix you're totally equipped to take on the palindromic paths problem let's get cracking so before we start i have to tell you there's going to be a little bit of a difference here for this program it's the order of traversal we're going to go from the top and right to the bottom not the bottom up and left to the top so keep that in mind as we march forward we're going to throw in our little palindrome checker up here first before we print them out at the end of our function hopefully by now you're familiar with that next we're going to create our main function with several parameters a string that will be empty but we're just going to call it string here a for our array our pointers that we'll call i and j our row and column that we'll call m and n now our conditional if statements are going to traverse the paths of our array we minus one from m and n because as you know this is python and we only need to iterate from indices starting at zero then one then two for our total size of rows and columns three by three see the i plus one and the j plus one within our recursive callbacks look at these slides to see the paths you could also print i and j within the conditional statements on your own to see it as well but when we add one to our pointers we're moving to the next element then once the traversal is completed it hits our else statement and that hits up our palindrome checker if it's true it'll print then it moves on to do the next reversal over and over until it's done and there you have it four palindrome strings in our matrix yay so what did we learn on our final lesson we learned about dynamic programming which is finding the optimal solution to sub problems that can be used to find the optimal solutions to the overall problem we saw this in our lesson with ugly numbers the traveling salesman problem and palindromic matrix paths in the easy lesson we learned about ugly numbers what they are and how to write a program to find the nth ugly number in the sequence avoiding brute force and recursion we were able to implement dynamic programming to optimize the solution from over one thousand iterations down to just a little over one we looked at the very famous traveling salesman problem with its main focus in optimizing a solution to finding the most efficient route a solution used across the board for so many companies in order to keep operational costs low and lastly we broke down the mind breaker lesson by studying unique paths in a matrix string palindromes within a matrix and combining those two problems together to find all the palindromic paths within a matrix are you excited i know that i am we covered so much ground in this course it's crazy hopefully you took lots of notes so you can practice later you should be coding something every day even if it's just for a couple minutes 10 to 15. since every little bit helps now listen to your mother thank you so much for joining me today and if you made it all the way here kudos to you i wish you all the best in your programming journey bye\n"