WEBVTT - What is an algorithm? 0:00:04.400 --> 0:00:07.800 Welcome to tech Stuff, a production from I Heart Radio. 0:00:12.119 --> 0:00:14.920 Hey there, and welcome to tech Stuff. I'm your host, 0:00:15.080 --> 0:00:18.000 Jonathan Strickland. I'm an executive producer with I Heart Radio 0:00:18.079 --> 0:00:21.600 and a love of all things tech, and I frequently 0:00:21.840 --> 0:00:25.600 speak about algorithms on this show. I talked about them 0:00:25.640 --> 0:00:30.120 all the time, talk about Facebook's algorithm or YouTube's algorithm. 0:00:30.240 --> 0:00:34.440 We talk about search algorithms and recommendation algorithms and tons 0:00:34.680 --> 0:00:37.800 of others. But I haven't really spent a ton of 0:00:37.840 --> 0:00:42.760 time talking about what algorithms actually are. Like it kind 0:00:42.760 --> 0:00:47.519 of becomes shorthand for do not look behind the curtain, right, 0:00:47.680 --> 0:00:49.959 It doesn't really help you if you don't know more 0:00:50.080 --> 0:00:53.160 about it. I might go as far as to say 0:00:53.200 --> 0:00:55.680 it's a set of rules or instructions to carry out 0:00:55.680 --> 0:00:59.120 a task, but that's pretty reductive and it doesn't really 0:00:59.160 --> 0:01:02.280 help you understand and what algorithms actually do. So today 0:01:02.800 --> 0:01:05.640 I thought we'd talk a little bit about algorithms and 0:01:05.720 --> 0:01:08.360 what they do in general, and then maybe chat about 0:01:08.360 --> 0:01:11.600 a few famous examples and some fun, little quirky stuff. 0:01:11.680 --> 0:01:15.480 So before I dive into this, we do need to 0:01:15.600 --> 0:01:20.759 establish a few things, and arguably the most important of 0:01:20.800 --> 0:01:24.360 those things is that I am not a mathematician, I 0:01:24.400 --> 0:01:28.120 am not a computer scientist. I'm a guy who loves tech, 0:01:28.520 --> 0:01:32.279 and I'm decent at research, and I do my best 0:01:32.360 --> 0:01:36.480 to communicate topics in an informative and you know, on 0:01:36.520 --> 0:01:39.839 a good day and entertaining way. So with that in mind, 0:01:40.280 --> 0:01:43.000 I fully admit that this is a subject that is 0:01:43.040 --> 0:01:48.160 outside of my narrow expertise, and so my descriptions and 0:01:48.240 --> 0:01:52.800 explanations will be from a very high level. And you 0:01:52.880 --> 0:01:55.560 might even be able to get something like this just 0:01:55.640 --> 0:01:59.480 by glancing at a pamphlet that's about a computer science 0:01:59.520 --> 0:02:04.280 introduct the recourse. So for all you folks out there 0:02:04.280 --> 0:02:06.480 who are deep in the computer sciences, this is going 0:02:06.520 --> 0:02:10.760 to be like a children's story book for you, possibly 0:02:10.880 --> 0:02:15.520 one where you don't like the illustrations very much. Another 0:02:15.600 --> 0:02:19.600 thing that I need to establish is that algorithm itself 0:02:19.680 --> 0:02:23.560 is a very broad term, you know, in that sense 0:02:23.680 --> 0:02:28.079 it's kind of like the word program or app or software, 0:02:28.639 --> 0:02:32.040 and that these words are categories that can have a 0:02:32.080 --> 0:02:36.320 wide variety of specific instances. For example, let's just take 0:02:36.320 --> 0:02:39.040 a look at software. If I'm talking about software, I 0:02:39.040 --> 0:02:43.240 could be talking about a very simple program that serves 0:02:43.360 --> 0:02:47.520 as a basic calculator that can add and subtract and 0:02:47.520 --> 0:02:51.160 divide and multiply. That could be a piece of software, 0:02:51.240 --> 0:02:53.919 be a very simple one, or I might talk about 0:02:53.960 --> 0:02:57.760 something a little more complicated, like a word processing program. 0:02:57.919 --> 0:03:01.240 Or I could talk about an advanced three D shooter 0:03:01.480 --> 0:03:07.720 video game, or an incredibly complicated computer simulation program, or 0:03:07.760 --> 0:03:10.240 anything in between. All of those could fall into the 0:03:10.280 --> 0:03:14.760 realm of software well. Algorithms similarly come in a wide 0:03:14.840 --> 0:03:19.000 variety of functions and complexity. There are some that are 0:03:19.000 --> 0:03:23.119 elegant in their simplicity, and there are some that when 0:03:23.120 --> 0:03:26.000 I look at them written out in in what is 0:03:26.320 --> 0:03:33.600 clearly well defined terminology, uh, I'm just left wondering what 0:03:33.639 --> 0:03:35.600 the heck it is I just saw. They might as 0:03:35.600 --> 0:03:38.680 well be hieroglyphics to me. In other words, But let's 0:03:38.680 --> 0:03:43.400 start off by talking about the word algorithm itself. Now, 0:03:44.640 --> 0:03:48.720 unlike a lot of words that we use specifically in English, 0:03:49.240 --> 0:03:53.920 algorithm does not have its roots in Latin vocabulary. There 0:03:53.960 --> 0:03:57.400 are words in Latin that are like al gore and 0:03:57.480 --> 0:04:01.040 things like that, but that's not where algorithm comes from. Instead, 0:04:01.720 --> 0:04:07.600 it's a latinized version of an Arabic name. Algorithm comes 0:04:07.600 --> 0:04:10.920 from algorithmic, which is the name that Latin scholars gave 0:04:10.960 --> 0:04:15.160 to a brilliant man named al qua Ritzmy and my 0:04:15.320 --> 0:04:19.000 apologies for the butchering of the pronunciation of that name. 0:04:19.200 --> 0:04:24.840 No disrespect is intended. It's merely American ignorance. Anyway. This 0:04:24.960 --> 0:04:31.719 particular mathematician philosophers scholar served as a very important astronomer 0:04:31.760 --> 0:04:36.200 and librarian in Baghdad in the ninth century. His work 0:04:36.240 --> 0:04:40.479 in mathematics was truly foundational, so much so that we 0:04:40.600 --> 0:04:44.680 get the word algebra from a work that he published. 0:04:45.320 --> 0:04:49.440 He treated algebra as a distinct branch of mathematics, when 0:04:49.520 --> 0:04:51.799 before it was just kind of lumped in with other stuff. 0:04:52.160 --> 0:04:54.360 And he did a lot of work in showing how 0:04:54.440 --> 0:04:58.400 to work various types of equations and how to balance equations. 0:04:58.600 --> 0:05:02.039 And on a personal note, this was something that I 0:05:02.160 --> 0:05:04.800 used to love to do in my mathematics courses. I 0:05:04.839 --> 0:05:08.279 could really see the beauty in determining if two sides 0:05:08.320 --> 0:05:11.960 of an equation truly were equal. It was like an 0:05:12.000 --> 0:05:15.240 elegant puzzle and I really love that. But again, just 0:05:15.279 --> 0:05:18.000 to be clear, my love of algebra and trigonometry is 0:05:18.040 --> 0:05:21.240 pretty much where math and I parted ways, because when 0:05:21.279 --> 0:05:25.080 calculus came along, I was I was pretty much done, 0:05:25.160 --> 0:05:27.640 so at that point it was it was beyond my 0:05:27.880 --> 0:05:33.080 ken as they say. Anyway, back to our Arabic scholar, 0:05:33.520 --> 0:05:38.000 he highlighted the importance and effectiveness of using a methodical 0:05:38.160 --> 0:05:42.760 approach towards the solution of problems, and that kind of 0:05:42.800 --> 0:05:47.440 gets at the heart of what algorithms actually are. The 0:05:47.480 --> 0:05:51.240 basic definition, which I kind of alluded to earlier is 0:05:51.480 --> 0:05:55.400 quote a process or set of rules to be followed 0:05:55.480 --> 0:06:00.640 in calculations or other problems solving operations, especially by a 0:06:00.640 --> 0:06:05.080 computer end quote that's from Oxford Languages. But you know 0:06:05.480 --> 0:06:07.560 this can apply to all sorts of stuff. For example, 0:06:07.760 --> 0:06:11.719 if you've ever seen anyone who can solve Rubik's cubes, 0:06:12.160 --> 0:06:15.040 those those puzzles that are in cube form where you've 0:06:15.040 --> 0:06:17.760 got all the little, uh different colors of squares and 0:06:17.800 --> 0:06:20.440 your job is to make each side of the cube 0:06:20.480 --> 0:06:24.080 the same color. Well, there are people who can solve 0:06:24.160 --> 0:06:27.800 Rubik's cubes in in in a fraction of like, like 0:06:28.000 --> 0:06:30.359 less than a minute. It's it's amazing to watch them go. 0:06:30.480 --> 0:06:33.400 It's so fast and it's hard to keep up with 0:06:33.400 --> 0:06:39.080 what they're doing. They are essentially following algorithms these processes 0:06:39.200 --> 0:06:45.799 that will get to a dependable and replicable outcome based 0:06:45.839 --> 0:06:49.120 on what you're doing. Um So, an algorithm is really 0:06:49.160 --> 0:06:52.279 just a way for us to problem solve. Let's say 0:06:52.279 --> 0:06:54.920 we have a particular outcome that we want to achieve. 0:06:55.240 --> 0:06:58.320 The algorithm is the recipe that we followed to go 0:06:58.440 --> 0:07:01.320 from whatever our starting can to. S is our starting 0:07:01.360 --> 0:07:04.680 state in order to get to the outcome we want 0:07:04.680 --> 0:07:08.640 to our target state, it needs to be well defined. 0:07:08.920 --> 0:07:11.280 Algorithms have to be well defined because computers are not 0:07:11.320 --> 0:07:15.960 really capable of implementing vague instructions. It needs to have 0:07:16.800 --> 0:07:19.600 a pretty solid approach so that the computer, when following 0:07:19.640 --> 0:07:23.280 the algorithm quote unquote, knows exactly what to do based 0:07:23.320 --> 0:07:26.880 upon the current state of the problem. It also needs 0:07:26.880 --> 0:07:32.320 to be finite. Computers are not capable of handling infinite possibilities, 0:07:32.800 --> 0:07:36.080 so the algorithm has to work within certain parameters, and 0:07:36.160 --> 0:07:39.240 those parameters depend upon the nature of the problem you're 0:07:39.280 --> 0:07:42.080 trying to solve and the equipment that you have to 0:07:42.160 --> 0:07:46.200 solve it with. So let's take a problem that computers 0:07:46.320 --> 0:07:51.360 typically struggle to achieve, and that is random number generation 0:07:51.680 --> 0:07:55.200 or r n G. Now, you would think that creating 0:07:55.240 --> 0:07:58.680 a random number would be easy. I mean, we can 0:07:58.720 --> 0:08:01.880 do it just by throwing some dice for example, Right, 0:08:01.920 --> 0:08:04.280 you can throw a die and and whatever the number 0:08:04.560 --> 0:08:08.360 comes up, that's your random number. But computers have to 0:08:08.400 --> 0:08:13.600 follow specific instructions and execute operations that by definition need 0:08:13.640 --> 0:08:17.400 to have a predictable and replicable outcomes. So computers find 0:08:17.480 --> 0:08:22.480 random number generation really tricky. Typically, the best we can 0:08:22.520 --> 0:08:25.560 hope for when it comes down to this sort of 0:08:25.600 --> 0:08:29.640 thing is pseudo random numbers. So these are numbers that, 0:08:29.760 --> 0:08:33.480 to an extent, appear to be random, right Like, on 0:08:33.720 --> 0:08:38.920 casual observation, it looks like the computer is generating random numbers. However, 0:08:38.960 --> 0:08:42.720 if you were to really seriously dig down into the process, 0:08:43.160 --> 0:08:46.480 you might discover that they are not really random at all. 0:08:47.120 --> 0:08:49.760 But we just need them to be random enough, right. 0:08:49.840 --> 0:08:52.720 We need it to be close enough to seeming to 0:08:52.760 --> 0:08:55.400 be random for it to fulfill the function we need. 0:08:55.880 --> 0:08:59.000 If it's not truly random for a lot of applications, 0:08:59.559 --> 0:09:04.320 that ends being you know, negligible. On a related note, 0:09:04.720 --> 0:09:07.960 there are some types of mathematical problems that have many 0:09:07.960 --> 0:09:12.280 degrees of freedom lots of variables. For example, so a 0:09:12.360 --> 0:09:14.360 problem that does have a lot of variables could have 0:09:14.360 --> 0:09:16.959 a lot of potential solutions, and so it could be 0:09:17.000 --> 0:09:20.480 a challenge for computers to solve. We need algorithms to 0:09:20.480 --> 0:09:24.040 tackle these sorts of problems, to go at them in 0:09:24.080 --> 0:09:29.240 ways that go beyond deterministic computation, which I guess I 0:09:29.280 --> 0:09:34.160 should define that. So, deterministic computation refers to a process 0:09:34.200 --> 0:09:39.000 in which each successive state of an operation depends completely 0:09:39.080 --> 0:09:43.640 on the previous state. So what comes next always depends 0:09:43.720 --> 0:09:47.120 upon what came just before. And I'll give you an example. 0:09:47.440 --> 0:09:49.480 Let's say I give you a math problem. I say 0:09:49.960 --> 0:09:52.000 you need to add these two numbers together. And let's 0:09:52.000 --> 0:09:55.839 say it's like, uh, five and six, and then from 0:09:55.960 --> 0:09:59.040 the sum of those numbers you have to subtract four. Well, 0:09:59.280 --> 0:10:01.960 you at first add those two numbers together, so five 0:10:02.000 --> 0:10:05.160 plus six you got eleven, and then you would subtract 0:10:05.679 --> 0:10:10.240 four from that number, and so eleven minus four equals seven. 0:10:10.840 --> 0:10:14.160 And this process is deterministic, because I gave you those 0:10:14.160 --> 0:10:19.600 specific instructions that computers do really well with deterministic processes. 0:10:19.679 --> 0:10:23.440 These are pretty easy to follow. These sorts of processes 0:10:23.480 --> 0:10:27.160 are by their nature replicable. So in other words, if 0:10:27.200 --> 0:10:30.240 I ask you to do that same operation. If I 0:10:30.280 --> 0:10:33.520 tell you add five and six together and then subtract four, 0:10:34.360 --> 0:10:36.400 it doesn't matter how many times you are you do 0:10:36.520 --> 0:10:38.959 that that process, right, You're always going to come out 0:10:39.559 --> 0:10:41.840 with the same answer. It's always going to come back 0:10:42.200 --> 0:10:45.680 no matter what you do, You're gonna always have seven 0:10:45.760 --> 0:10:49.480 as your answer, just based on that same input. So 0:10:49.840 --> 0:10:53.840 there are a family of algorithms that collectively get the 0:10:53.920 --> 0:10:58.680 name Monte Carlo algorithms, and they're named after Monte Carlo, 0:10:58.920 --> 0:11:01.400 the area of Monaco that is famous for being the 0:11:01.440 --> 0:11:05.480 location of lots of high end casinos have been there. 0:11:05.960 --> 0:11:09.680 It's not really my jam, but it is pretty darn flashy. 0:11:10.240 --> 0:11:14.559 So the reason these algorithms get the name Monte Carlo 0:11:14.640 --> 0:11:19.400 algorithms is that, like gambling, they deal with an element 0:11:19.480 --> 0:11:24.680 of randomization. So gambling is called gambling because you're taking 0:11:24.679 --> 0:11:28.760 a risk. You're gambling, you're betting that you're gonna beat 0:11:28.800 --> 0:11:31.400 the odds in whichever game it is that you're playing, 0:11:31.520 --> 0:11:34.439 and that you're going to achieve an outcome that's favorable 0:11:34.480 --> 0:11:38.120 to you, which you experience as a payout. So whether 0:11:38.160 --> 0:11:41.720 it's throwing dice or playing a card game or placing 0:11:41.720 --> 0:11:45.200 bets at a roulette wheel or playing a slot machine. 0:11:45.280 --> 0:11:47.880 You are engaged in an activity in which there is 0:11:48.080 --> 0:11:51.800 some element of chance, at least in theory if the 0:11:51.800 --> 0:11:55.000 game is honest, and what you're hoping for is that 0:11:55.400 --> 0:12:00.280 chance lands in your favor. Similarly, Monty car are Low 0:12:00.360 --> 0:12:04.440 algorithms often focus on chance and risk assessments such as 0:12:04.880 --> 0:12:08.200 what are the odds that if I do this one thing, 0:12:08.840 --> 0:12:12.480 I'm gonna totally regret doing it later? But you know, 0:12:12.640 --> 0:12:15.320 more of the as a computational problem and not a 0:12:15.400 --> 0:12:20.959 lifestyle choice. Well, back in nineteen scientists at the Los 0:12:21.040 --> 0:12:25.920 Alamos Scientific Laboratory, including John von Neumann, uh stand All 0:12:26.200 --> 0:12:30.240 Lam and Nick Metropolis, proposed what would become known as 0:12:30.240 --> 0:12:34.960 the Metropolis algorithm, one of the Monte Carlo algorithms, and 0:12:35.000 --> 0:12:39.199 the purpose of this algorithm was to approximate solutions two 0:12:39.440 --> 0:12:45.559 very complicated mathematical problems where going through a deterministic approach 0:12:45.880 --> 0:12:49.640 to find the definitive answer just wasn't feasible. So, in 0:12:49.679 --> 0:12:53.160 other words, for certain complicated math problems, figuring out the 0:12:53.200 --> 0:12:56.839 quote unquote real answer would really just take too long, 0:12:57.240 --> 0:12:59.480 perhaps to the point where you would never get there 0:12:59.480 --> 0:13:02.240 within your lifetime. So you need a way to kind 0:13:02.280 --> 0:13:05.959 of get a ballpark solution that hopefully is closer to 0:13:06.000 --> 0:13:09.720 being correct than incorrect. Doesn't sound like the sort of 0:13:09.720 --> 0:13:12.080 thing that computers would be particularly good at doing right 0:13:12.120 --> 0:13:15.960 off the bat. Right. In fact, the algorithm allows computers 0:13:16.000 --> 0:13:20.320 to mimic a randomized process, so it's not truly random, 0:13:20.520 --> 0:13:24.120 but it's random ish if you like, And it uses 0:13:24.160 --> 0:13:27.320 this to approximate a solution to whatever the problem is 0:13:27.360 --> 0:13:30.440 that you're trying to solve that falls into this category. 0:13:30.600 --> 0:13:34.320 I once saw a simulation of a randomized process using 0:13:34.320 --> 0:13:38.640 the Monte Carlo method that I thought was pretty nifty, 0:13:38.760 --> 0:13:41.560 and it was determining what is the value of pie. 0:13:41.679 --> 0:13:44.840 Let's say that you don't know the value of pie 0:13:45.120 --> 0:13:47.640 and you're just trying to figure it out. So and 0:13:47.679 --> 0:13:49.400 by the way, I mean pie is in p I 0:13:49.480 --> 0:13:53.840 not as in the delicious pie dessert treat. So here's 0:13:53.880 --> 0:13:56.720 the scenario. Imagine that you've got a table and the 0:13:56.760 --> 0:13:59.520 tables like I don't know, three ft to a side, 0:14:00.040 --> 0:14:03.920 and positioned over this table is a robotic arm, and 0:14:04.000 --> 0:14:07.720 this robotic arm can pick up and drop large ball 0:14:07.800 --> 0:14:11.760 bearings onto the table, and the arm can just move 0:14:11.880 --> 0:14:13.920 over the entire region of the table, so it's got 0:14:13.920 --> 0:14:17.360 a three ft by three ft range of motion. And 0:14:17.640 --> 0:14:21.880 in on this table you set down two containers. You've 0:14:21.920 --> 0:14:26.360 got one that's that's a circular container, and one that's square. 0:14:26.960 --> 0:14:31.160 And the square container measures six inches to a side. Uh, 0:14:31.280 --> 0:14:35.440 the radius of the circular circular container is also six inches, 0:14:35.480 --> 0:14:37.800 so that means it's got a twelve inch diameter. Right. 0:14:38.080 --> 0:14:42.160 So those are your containers, and you've got your situation 0:14:42.200 --> 0:14:45.680 with your your robot arm above this three ft square table. 0:14:46.440 --> 0:14:48.840 So the robotic arms job is to pick up ball 0:14:48.880 --> 0:14:54.320 bearings and then from a random que will drop that 0:14:54.360 --> 0:14:58.120 ball bearing somewhere above the table. So some of those 0:14:58.160 --> 0:15:00.920 balls are going to fall into the square container, some 0:15:01.040 --> 0:15:03.720 of them are going to fall into the round container. 0:15:03.800 --> 0:15:05.440 Some of them are not going to fall in either. 0:15:06.200 --> 0:15:09.720 And if the process is truly random, meaning there's an 0:15:09.800 --> 0:15:12.600 equal chance that it will drop a ball bearing over 0:15:12.680 --> 0:15:16.800 any given point of that table, over time, we would 0:15:16.800 --> 0:15:19.600 expect to see more ball bearings fall into the round 0:15:19.680 --> 0:15:24.040 container because it has a greater area and there's more 0:15:24.080 --> 0:15:27.360 space for a ball bearing to fall into one of these. 0:15:27.920 --> 0:15:31.680 At the end of repeating this process many many times, 0:15:32.000 --> 0:15:35.080 we should be able to take these two containers and 0:15:35.120 --> 0:15:38.360 then count the number of ball bearings in each of them. 0:15:38.440 --> 0:15:41.360 And if we divide the number of ball bearings in 0:15:41.400 --> 0:15:44.680 the circular container by the number of ball bearings that 0:15:44.720 --> 0:15:48.200 fell into the square container, we're gonna get results that 0:15:48.240 --> 0:15:52.960 should be really close to pie. And you might think, wait, 0:15:54.480 --> 0:15:57.960 why why would the number of ball bearings in one 0:15:58.000 --> 0:16:01.680 container versus another, and then divide fighting those why would 0:16:01.720 --> 0:16:04.160 you get pie? Well, if you have a process that 0:16:04.400 --> 0:16:08.440 is uniformly random across an area, like our hypothetical three 0:16:08.440 --> 0:16:12.520 ft square table, the probability that a dropped ball bearing 0:16:12.520 --> 0:16:16.240 will land in one of those two specific containers is 0:16:16.240 --> 0:16:21.120 proportional to that specific containers area or cross section. So 0:16:21.520 --> 0:16:23.080 then we just ask, all, right, well, how do we 0:16:23.160 --> 0:16:25.960 define area? Well, with the square, it's really simple, right. 0:16:26.040 --> 0:16:28.800 We take one side of a square in this case, 0:16:28.800 --> 0:16:32.080 it's six inches, and we multiply it by itself six 0:16:32.120 --> 0:16:34.960 times six. Because all sides of a square are equal, 0:16:35.040 --> 0:16:36.960 we know that the length and the width are each 0:16:37.000 --> 0:16:39.760 going to be six inches. We multiply those together. We 0:16:39.800 --> 0:16:42.840 get thirty six square inches. That is the area or 0:16:42.960 --> 0:16:47.360 cross section of our square container. But for our circular container, 0:16:48.000 --> 0:16:50.760 we take the radius, which again in this case the 0:16:50.840 --> 0:16:53.960 radius is six inches, and we square it and then 0:16:54.040 --> 0:16:59.000 we multiply that number by pie. So area for the 0:16:59.120 --> 0:17:03.720 circular contain or is six times six squared times pie. 0:17:03.840 --> 0:17:06.640 And if we divide the cross section of the circular 0:17:06.680 --> 0:17:10.679 container by the cross section of the square container, the 0:17:10.800 --> 0:17:15.600 two six squared, you know, the two elements the squared 0:17:15.600 --> 0:17:18.400 elements cancel each other out, and so all we're left 0:17:18.400 --> 0:17:22.120 with is pie. So the end result is that when 0:17:22.160 --> 0:17:25.520 we count up these ball bearings that have landed randomly 0:17:25.560 --> 0:17:29.399 in these containers, that that difference, the division that we 0:17:29.520 --> 0:17:33.480 get that should be a close approximation of pie. Now 0:17:33.520 --> 0:17:36.160 it's not going to be precise. Chances are the number 0:17:36.160 --> 0:17:38.680 of ball bearings in the two containers will just get 0:17:38.720 --> 0:17:42.560 you close to pie. But it illustrates how a randomized 0:17:42.600 --> 0:17:46.480 process can help you get to a particular solution that 0:17:46.600 --> 0:17:50.479 might otherwise be difficult to ascertain. There are videos on 0:17:50.480 --> 0:17:53.359 YouTube that show this particular simulation. It's kind of a 0:17:53.400 --> 0:17:56.400 famous one, so you can actually watch and get kind 0:17:56.400 --> 0:17:58.520 of an understanding of what I said to you makes 0:17:58.600 --> 0:18:02.159 no sense whatsoever. There are other options for you to 0:18:02.240 --> 0:18:06.040 look into that might help, and that is a great example. 0:18:06.600 --> 0:18:09.479 But what are the actual algorithms that fall into the 0:18:09.560 --> 0:18:13.720 Monte Carlo methods spectrum? What are they used to do well? 0:18:13.800 --> 0:18:17.119 They can be used to simulate things like fluid dynamics 0:18:17.280 --> 0:18:21.919 or cellular structures or the interaction of disordered materials. So 0:18:21.960 --> 0:18:25.159 in other words, these are all processes. They have a 0:18:25.240 --> 0:18:28.600 lot of potential variables at play, and you can think 0:18:28.640 --> 0:18:33.200 of variables as representing uncertainty, something that computers typically don't 0:18:33.359 --> 0:18:37.679 do well with. You know, from a general stance, computers 0:18:37.760 --> 0:18:43.640 excel at specific instances rather than potential instances. So algorithms 0:18:43.680 --> 0:18:48.400 like the Metropolis algorithm would lead computer scientists to develop 0:18:48.560 --> 0:18:52.719 methodologies to kind of work around the limitations of computers 0:18:52.720 --> 0:18:58.359 and leverage computational power and tackling very difficult problems in 0:18:58.400 --> 0:19:02.199 that way. In the Monte Carlo family of algorithms, we 0:19:02.280 --> 0:19:05.600 typically assume that the results we get are going to 0:19:06.560 --> 0:19:09.119 have a potential for being wrong, like there'll be a 0:19:09.160 --> 0:19:12.080 small percentage of error that we have to take into account, 0:19:12.640 --> 0:19:14.600 and so keeping that in mind, we need to frame 0:19:14.640 --> 0:19:18.480 results as being again approximations of an answer rather than 0:19:18.560 --> 0:19:21.800 the definitive answer to whatever problem it is we're trying 0:19:21.840 --> 0:19:24.120 to solve. For me, this was one of those things 0:19:24.119 --> 0:19:26.919 that was very difficult to grasp for a long time 0:19:27.080 --> 0:19:30.480 because I was equating it to math class, where you're 0:19:30.480 --> 0:19:33.359 supposed to get the answer. Now, when we come back, 0:19:33.560 --> 0:19:36.360 we'll talk about a few more famous algorithms and what 0:19:36.400 --> 0:19:46.720 they do. But first let's take a quick break. Now. 0:19:46.760 --> 0:19:49.080 In our previous section, I talked about a family of 0:19:49.119 --> 0:19:52.840 algorithms that trace their history back to nineteen and so 0:19:52.960 --> 0:19:55.200 does the next one I want to talk about, which 0:19:55.240 --> 0:19:59.879 was created by George Dantzig who worked for the Rand Corporation, 0:20:00.040 --> 0:20:03.520 and Danzig created a process that would lead to what 0:20:03.560 --> 0:20:08.160 we call linear programming. So at its most basic level, 0:20:08.400 --> 0:20:12.919 linear programming is about taking some function and maximizing or 0:20:13.040 --> 0:20:17.119 minimizing that function with regard to various constraints. But that 0:20:17.200 --> 0:20:19.800 is super vague, right, I mean, it's not terribly helpful. 0:20:20.080 --> 0:20:22.520 It feels like I'm talking in a circle. But this 0:20:22.600 --> 0:20:26.320 is one that's really important for say, business developers. So 0:20:26.400 --> 0:20:29.600 let's talk about a slightly more specific use case. Let's 0:20:29.600 --> 0:20:32.680 say that you are launching a business and you're trying 0:20:32.720 --> 0:20:35.800 to make some you know, big decisions as you're going 0:20:35.840 --> 0:20:38.840 to do this, and you're going to manufacture and sell 0:20:39.040 --> 0:20:42.439 a product of some sort, some physical thing. Now, your 0:20:42.480 --> 0:20:45.800 whole goal as a business is to make money from 0:20:46.000 --> 0:20:48.359 the work you do, and to do that, you need 0:20:48.400 --> 0:20:50.720 to figure out what your costs are going to be 0:20:51.359 --> 0:20:55.400 and how you cannot just offset these costs but make 0:20:55.520 --> 0:20:59.440 enough money to actually profit from it, so cover all 0:20:59.480 --> 0:21:03.360 your costs plus some extra. So in this case, what 0:21:03.400 --> 0:21:05.560 you're trying to do is figuring out how you can 0:21:05.600 --> 0:21:11.720 minimize costs and maximize profits. Right. The constraints come into 0:21:11.720 --> 0:21:15.080 play as you start to look at specifics, like maybe 0:21:15.119 --> 0:21:18.200 you're gonna partner with a fabrication company, and maybe you've 0:21:18.200 --> 0:21:20.679 actually got a few choices. You've got different companies that 0:21:20.720 --> 0:21:23.679 you could go with. Well, these choices could represent constraints 0:21:23.680 --> 0:21:27.480 in your approach. Perhaps one is more expensive than the others, 0:21:27.480 --> 0:21:31.200 but it can produce a greater volume of product, so 0:21:31.440 --> 0:21:34.119 you'd be able to get more product out to market 0:21:34.280 --> 0:21:38.480 in less time. Or maybe you've got one that's more expensive, 0:21:38.600 --> 0:21:42.800 but it's also less likely to have fabrication errors, and 0:21:43.080 --> 0:21:46.680 errors can be both costly and time consuming to address, 0:21:46.720 --> 0:21:50.280 So you have to quantify all these variables and use 0:21:50.359 --> 0:21:54.040 them as constraints to start figuring out your men maxing approach. 0:21:54.119 --> 0:21:58.400 Here line, your programming simply looks for the optimum value 0:21:58.560 --> 0:22:01.920 of a linear expression, and depending on the problem you're 0:22:01.960 --> 0:22:06.280 trying to solve, like maximizing profit versus minimizing costs, you're 0:22:06.280 --> 0:22:09.800 either looking for the highest value being optimum or the 0:22:09.800 --> 0:22:12.639 lowest value being optimum. Like with costs, you want that 0:22:12.680 --> 0:22:14.840 to be the lowest, and you have to look at 0:22:14.880 --> 0:22:19.119 what constraints are at play with any given expression. So 0:22:19.200 --> 0:22:23.359 Danzig's approach to linear programming, called the simplex method, was 0:22:23.440 --> 0:22:27.639 efficient and elegant and far more simplified than other methodologies 0:22:27.680 --> 0:22:31.000 attempting to kind of do the same thing around that time. 0:22:31.080 --> 0:22:34.359 But it also had some limitations, and that's because the 0:22:34.400 --> 0:22:38.040 real world isn't as simple as math tends to be. 0:22:38.359 --> 0:22:42.520 Like math tends to be pretty, you know, firm in 0:22:42.560 --> 0:22:44.320 the grand scheme of things, in the world is a 0:22:44.320 --> 0:22:48.280 little more wibbly wobbly. So a linear programming solution only 0:22:48.280 --> 0:22:52.600 works if the various relationships between the different elements like 0:22:52.680 --> 0:22:55.520 the requirements and the restrictions and the constraints that you've 0:22:55.560 --> 0:22:57.760 set up with this problem. It only works if all 0:22:57.800 --> 0:23:01.040 of those relationships are linear or other words, for a 0:23:01.040 --> 0:23:04.840 given change in one variable, we see a given change 0:23:04.960 --> 0:23:08.800 in other variables, and that is super vague. So we're 0:23:08.800 --> 0:23:11.400 going to talk about two variables. Will reduce it down 0:23:11.400 --> 0:23:14.840 to that. So we'll use the classic X and Y 0:23:14.920 --> 0:23:17.720 as our variables. Those can stand in for all sorts 0:23:17.720 --> 0:23:21.520 of different values. And let's say that we see there's 0:23:21.520 --> 0:23:24.520 a relationship between X and Y, and that if the 0:23:24.600 --> 0:23:29.600 value of X changes from one to two, we then 0:23:29.640 --> 0:23:34.040 see that the value of hy goes from three to nine. Well, 0:23:34.040 --> 0:23:36.359 that doesn't tell us anything on its own, right. We 0:23:36.440 --> 0:23:39.320 just know that if x is one, y is three. 0:23:39.400 --> 0:23:42.360 If x is two, y is nine. If we then 0:23:42.400 --> 0:23:46.879 see that if x is three, then why is fifteen? 0:23:47.400 --> 0:23:52.200 And when x is four, why is twenty one? We 0:23:52.359 --> 0:23:55.600 start to see a linear relationship because each time x 0:23:55.640 --> 0:23:59.679 increases by one, Y increases by six, the rate of 0:23:59.720 --> 0:24:05.080 increase for each variable is linear. It's it's not like 0:24:05.119 --> 0:24:08.000 the rate of increase doesn't change. So we've got this 0:24:08.119 --> 0:24:14.040 linear relationship here. We can contrast this with exponential relationships, 0:24:14.080 --> 0:24:17.879 in which we see not a constant increase but a 0:24:17.960 --> 0:24:22.359 constant ratio in successive terms in one variable when you 0:24:22.480 --> 0:24:25.439 change another. So in this case, let's say that we 0:24:25.520 --> 0:24:28.680 find out then when X is one, why is three? 0:24:29.320 --> 0:24:33.160 When X is two, why is nine? When X is three, 0:24:33.720 --> 0:24:37.000 why is twenties seven? Now we see that why is 0:24:37.000 --> 0:24:42.000 not increasing by six each time. We're seeing that the 0:24:42.080 --> 0:24:46.000 value of why is multiplied by three each time X 0:24:46.000 --> 0:24:48.760 goes up one. So we're seeing there's a constant ratio 0:24:49.000 --> 0:24:52.760 of change with why with regard to X. This gets 0:24:52.840 --> 0:24:56.959 into an exponential relationship. So when someone describes something as 0:24:57.000 --> 0:25:02.439 having exponential growth, what this is supposed to mean is 0:25:02.480 --> 0:25:06.439 that you should see a rate of growth that is 0:25:06.520 --> 0:25:11.159 increasing by some exponent per given unit of time. So 0:25:11.200 --> 0:25:14.320 it's not just that the thing is growing. In fact, 0:25:14.320 --> 0:25:17.520