WEBVTT - Rerun: What is an algorithm? 0:00:04.400 --> 0:00:07.800 Welcome to tech Stuff, a production from I Heart Radio. 0:00:11.880 --> 0:00:14.200 Hey there, and welcome to tech Stuff. I'm your host, 0:00:14.320 --> 0:00:16.760 Jonathan Strickland. I'm an executive producer with I Heart Radio. 0:00:16.840 --> 0:00:19.600 And how the tech are you. I'm not doing so 0:00:19.640 --> 0:00:22.599 great myself right now. I'm running a low fever. I'm 0:00:22.600 --> 0:00:24.919 hoping that I just have like a stomach bug or 0:00:24.960 --> 0:00:27.320 something and that it's not a second case of COVID, 0:00:27.360 --> 0:00:29.960 because I don't want to be that guy. Uh. And 0:00:30.160 --> 0:00:32.080 that's a good reminder that if you are in an 0:00:32.120 --> 0:00:35.599 area where the COVID numbers have not really slacked off, 0:00:36.320 --> 0:00:38.280 still a good idea to wear a mask, you know, 0:00:38.360 --> 0:00:42.520 limit your exposure to other folks. Seriously, this is no fun. 0:00:42.600 --> 0:00:43.919 You don't want to go through it if you can 0:00:43.960 --> 0:00:47.080 avoid it. So yeah, just you know, I care about 0:00:47.080 --> 0:00:50.760 you guys, so take care of yourself. Also, you know 0:00:51.280 --> 0:00:53.640 that means that I'm not really able to write a 0:00:53.640 --> 0:00:56.640 new episode because I can't read good when I got 0:00:56.640 --> 0:00:59.360 a fever. So we're gonna have a little bit of 0:00:59.360 --> 0:01:01.680 a rerun. I apologize for that. I wish I could 0:01:01.720 --> 0:01:04.480 avoid it, I really do. But I also feel like 0:01:04.480 --> 0:01:07.080 this is an episode that is timeless. It's one that 0:01:07.240 --> 0:01:10.240 is important. It's called what Is an Algorithm? Which originally 0:01:10.280 --> 0:01:13.759 published last year on July twenty one, And the reason 0:01:13.760 --> 0:01:16.280 why I think it's important is that a lot of 0:01:16.280 --> 0:01:20.280 people know the word algorithm, but they don't have a 0:01:20.280 --> 0:01:23.000 deeper appreciation of what that actually means. We almost just 0:01:23.080 --> 0:01:26.400 use it as a placeholder. It might as well be magic, right. 0:01:26.680 --> 0:01:29.800 The Facebook algorithm determines what you see and what you 0:01:29.880 --> 0:01:34.160 don't see, but that doesn't really explain what an algorithm is. 0:01:34.280 --> 0:01:37.920 So I hope that you find this episode interesting and 0:01:38.240 --> 0:01:41.520 if you would like to leave a suggestion for an 0:01:41.520 --> 0:01:43.440 episode topic for me in the future. There are a 0:01:43.440 --> 0:01:45.280 couple different ways of doing it. One is you can 0:01:45.280 --> 0:01:48.360 go over to the I Heart Radio podcast app, which 0:01:48.400 --> 0:01:50.680 is free. You can just navigate over to the tech 0:01:50.720 --> 0:01:54.320 stuff page and there is a little microphone icon which 0:01:54.360 --> 0:01:56.520 allows you to leave a talk back message up to 0:01:56.720 --> 0:01:59.200 thirty seconds in length, so you can always leave me 0:01:59.240 --> 0:02:01.800 a message if you like. You can indicate if I 0:02:01.840 --> 0:02:05.000 could use the audio in an upcoming episode, which would 0:02:05.040 --> 0:02:06.840 be a lot of fun. But I'm not gonna just 0:02:06.880 --> 0:02:09.240 assume that you're cool with that. You'll have to tell me. 0:02:09.880 --> 0:02:11.839 And um, A lot of people have been doing that. 0:02:11.919 --> 0:02:14.440 They've been leaving messages. It's been great. You've all been 0:02:14.560 --> 0:02:18.040 so kind and so enthusiastic, and I love it. Keep 0:02:18.120 --> 0:02:20.560 them coming. Also, if you don't want to use the app, 0:02:20.600 --> 0:02:22.679 I totally get it. You can always leave me a 0:02:22.720 --> 0:02:24.880 message on Twitter. The handle for the show is tech 0:02:24.960 --> 0:02:28.600 Stuff hs W. Now let's get to this episode that 0:02:28.639 --> 0:02:32.160 originally published July twenty one, two thousand twenty one. What 0:02:32.560 --> 0:02:39.560 is an algorithm? I frequently speak about algorithms on the show. 0:02:39.639 --> 0:02:42.880 I talked about them all the time, about Facebook's algorithm 0:02:43.000 --> 0:02:47.760 or YouTube's algorithm. We talk about search algorithms and recommendation 0:02:47.840 --> 0:02:51.840 algorithms and tons of others. But I haven't really spent 0:02:52.040 --> 0:02:55.800 a ton of time talking about what algorithms actually are. 0:02:56.240 --> 0:03:01.000 Like it kind of become shorthand for do not look 0:03:01.040 --> 0:03:03.760 behind the curtain, right, It doesn't really help you if 0:03:03.760 --> 0:03:07.000 you don't know more about it. Uh. I might go 0:03:07.120 --> 0:03:08.960 as far as to say it's a set of rules 0:03:09.040 --> 0:03:12.240 or instructions to carry out a task, but that's pretty 0:03:12.280 --> 0:03:15.720 reductive and it doesn't really help you understand what algorithms 0:03:15.760 --> 0:03:18.800 actually do. So today I thought we'd talk a little 0:03:18.800 --> 0:03:21.960 bit about algorithms and what they do in general, and 0:03:22.000 --> 0:03:25.160 then maybe chat about a few famous examples and some fun, 0:03:25.280 --> 0:03:29.560 little quirky stuff. So before I dive into this, we 0:03:29.680 --> 0:03:34.320 do need to establish a few things, and arguably the 0:03:34.360 --> 0:03:37.360 most important of those things is that I am not 0:03:37.440 --> 0:03:41.840 a mathematician. I am not a computer scientist. I'm a 0:03:41.840 --> 0:03:46.000 guy who loves tech, and I'm decent at research, and 0:03:46.120 --> 0:03:50.000 I do my best to communicate topics in an informative 0:03:50.160 --> 0:03:53.160 and you know, on a good day and entertaining way. 0:03:53.600 --> 0:03:56.560 So with that in mind, I fully admit that this 0:03:56.640 --> 0:04:00.720 is a subject that is outside of my narrow expertise, 0:04:01.200 --> 0:04:04.360 and so my descriptions and explanations will be from a 0:04:04.480 --> 0:04:08.480 very high level. Uh. And you might even be able 0:04:08.520 --> 0:04:11.400 to get something like this just by glancing at a 0:04:11.480 --> 0:04:18.039 pamphlet that's about a computer science introductory course. So for 0:04:18.120 --> 0:04:19.719 all you folks out there who are deep in the 0:04:19.720 --> 0:04:23.320 computer sciences, this is going to be like a children's 0:04:23.440 --> 0:04:27.320 story book for you, possibly one where you don't like 0:04:27.400 --> 0:04:31.479 de illustrations very much. Another thing that I need to 0:04:31.600 --> 0:04:35.960 establish is that algorithm itself is a very broad term, 0:04:36.720 --> 0:04:39.359 you know, in that sense, it's kind of like the 0:04:39.400 --> 0:04:44.440 word program or app or software, and that these words 0:04:44.520 --> 0:04:49.000 are categories that can have a wide variety of specific instances. 0:04:49.279 --> 0:04:52.360 For example, let's just take a look at software. If 0:04:52.360 --> 0:04:55.640 I'm talking about software, I could be talking about a 0:04:55.760 --> 0:05:00.120 very simple program that serves as a basic calculator that 0:05:00.200 --> 0:05:04.680 can add and subtract and divide and multiply. That could 0:05:04.760 --> 0:05:06.960 be a piece of software, be a very simple one. 0:05:07.640 --> 0:05:10.040 Or I might talk about something a little more complicated, 0:05:10.120 --> 0:05:13.960 like a word processing program. Or I could talk about 0:05:14.040 --> 0:05:18.960 an advanced three D shooter video game, or an incredibly 0:05:19.080 --> 0:05:23.800 complicated computer simulation program, or anything in between. All of 0:05:23.839 --> 0:05:27.280 those could fall into the realm of software well. Algorithms 0:05:27.720 --> 0:05:32.680 similarly come in a wide variety of functions and complexity. 0:05:32.720 --> 0:05:35.800 There are some that are elegant in their simplicity, and 0:05:35.839 --> 0:05:38.839 there are some that when I look at them written 0:05:38.839 --> 0:05:46.160 out in in what is clearly well defined terminology, uh, 0:05:46.240 --> 0:05:49.040 I'm just left wondering what the heck it is I 0:05:49.080 --> 0:05:51.640 just saw. They might as well be hieroglyphics to me. 0:05:51.680 --> 0:05:54.760 In other words, but let's start off by talking about 0:05:54.839 --> 0:06:00.599 the word algorithm itself. Now, unlike a lot of words 0:06:01.040 --> 0:06:05.599 that we use specifically in English, algorithm does not have 0:06:05.760 --> 0:06:10.440 its roots in Latin vocabulary. There are words in Latin 0:06:10.520 --> 0:06:13.200 that are like al gore and things like that, but 0:06:13.320 --> 0:06:17.719 that's not where algorithm comes from. Instead, it's a Latinized 0:06:18.040 --> 0:06:23.840 version of an Arabic name. Algorithm comes from algorithmic, which 0:06:23.880 --> 0:06:26.640 is the name that Latin scholars gave to a brilliant 0:06:26.880 --> 0:06:31.359 man named al Ka Ritzmy and my apologies for the 0:06:31.440 --> 0:06:35.680 butchering of the pronunciation of that name. No disrespect is intended. 0:06:36.400 --> 0:06:43.760 It's merely American ignorance anyway. This particular mathematician philosophers scholar 0:06:44.360 --> 0:06:48.159 served as a very important astronomer and librarian in Baghdad 0:06:48.520 --> 0:06:53.360 in the ninth century. His work in mathematics was truly foundational, 0:06:53.880 --> 0:06:57.600 so much so that we get the word algebra from 0:06:57.640 --> 0:07:01.680 a work that he published. He treated algebra as a 0:07:01.760 --> 0:07:05.120 distinct branch of mathematics, when before it was just kind 0:07:05.120 --> 0:07:07.440 of lumped in with other stuff. And he did a 0:07:07.440 --> 0:07:11.000 lot of work and showing how to work various types 0:07:11.000 --> 0:07:13.600 of equations and how to balance equations. And on a 0:07:13.680 --> 0:07:17.559 personal note, this was something that I used to love 0:07:17.600 --> 0:07:20.400 to do in my mathematics courses. I could really see 0:07:20.400 --> 0:07:23.800 the beauty in determining if two sides of an equation 0:07:24.280 --> 0:07:27.880 truly were equal. It was like an elegant puzzle, and 0:07:27.880 --> 0:07:30.440 I really love that. But again, just to be clear, 0:07:30.560 --> 0:07:33.520 my love of algebra and trigonometry is pretty much where 0:07:33.960 --> 0:07:37.120 math and I parted ways, because when calculus came along, 0:07:37.640 --> 0:07:40.400 I was I was pretty much done. So at that 0:07:40.440 --> 0:07:45.880 point it was it was beyond my ken as they say. Anyway, 0:07:46.240 --> 0:07:50.000 back to our Arabic scholar, he highlighted the importance and 0:07:50.040 --> 0:07:56.080 effectiveness of using a methodical approach towards the solution of problems, 0:07:56.280 --> 0:07:59.480 and that kind of gets at the heart of what 0:07:59.720 --> 0:08:04.440 our gorhythms actually are. The basic definition, which I kind 0:08:04.440 --> 0:08:08.440 of alluded to earlier is quote a process or set 0:08:08.560 --> 0:08:12.520 of rules to be followed in calculations or other problems 0:08:12.520 --> 0:08:17.360 solving operations, especially by a computer. End quote that's from 0:08:17.400 --> 0:08:21.120 Oxford Languages. But you know this can apply to all 0:08:21.120 --> 0:08:23.960 sorts of stuff. For example, if you've ever seen anyone 0:08:24.400 --> 0:08:28.400 who can solve Rubics cubes, those those puzzles that are 0:08:28.520 --> 0:08:31.080 in cube form where you've got all the little, uh 0:08:31.240 --> 0:08:33.320 different colors of squares and your job is to make 0:08:33.760 --> 0:08:37.880 each side of the cube the same color. Well, there 0:08:37.880 --> 0:08:40.880 are people who can solve Rubik's cubes in in a 0:08:41.080 --> 0:08:44.040 fraction of like, like less than a minute. It's it's 0:08:44.080 --> 0:08:46.920 amazing to watch them go. It's so fast and it's 0:08:46.960 --> 0:08:49.600 hard to keep up with what they're doing. They are 0:08:49.720 --> 0:08:56.280 essentially following algorithms, these processes that will get to a 0:08:56.360 --> 0:09:02.640 dependable and replicable outcome based on what you're doing. Um So, 0:09:02.679 --> 0:09:04.839 an algorithm is really just a way for us to 0:09:05.200 --> 0:09:08.600 problem solve. Let's say we have a particular outcome that 0:09:08.679 --> 0:09:12.120 we want to achieve. The algorithm is the recipe that 0:09:12.160 --> 0:09:15.240 we followed to go from whatever our starting condition is 0:09:15.360 --> 0:09:19.000 our starting state. In order to get to the outcome 0:09:19.080 --> 0:09:22.080 we want to our target state, it needs to be 0:09:22.559 --> 0:09:25.760 well defined. Algorithms have to be well defined because computers 0:09:25.760 --> 0:09:30.439 are not really capable of implementing vague instructions. It needs 0:09:30.440 --> 0:09:33.600 to have a pretty solid approach so that the computer, 0:09:33.720 --> 0:09:37.000 when following the algorithm quote unquote, knows exactly what to 0:09:37.040 --> 0:09:41.000 do based upon the current state of the problem. It 0:09:41.040 --> 0:09:44.640 also needs to be finite. Computers are not capable of 0:09:44.800 --> 0:09:49.200 handling infinite possibilities, so the algorithm has to work within 0:09:49.280 --> 0:09:53.200 certain parameters, and those parameters depend upon the nature of 0:09:53.240 --> 0:09:56.160 the problem you're trying to solve. And the equipment that 0:09:56.240 --> 0:09:59.240 you have to solve it with. So let's take a 0:09:59.320 --> 0:10:04.120 problem that computers typically struggle to achieve, and that is 0:10:04.360 --> 0:10:08.720 random number generation or r in G. Now you would 0:10:08.760 --> 0:10:13.000 think that creating a random number would be easy. I mean, 0:10:13.040 --> 0:10:16.600 we can do it just by throwing some dice for example, Right, 0:10:16.640 --> 0:10:19.000 you can throw a die and and whatever the number 0:10:19.280 --> 0:10:23.080 comes up, that's your random number. But computers have to 0:10:23.120 --> 0:10:28.280 follow specific instructions and execute operations that by definition need 0:10:28.360 --> 0:10:32.120 to have a predictable and replicable outcomes. So computers find 0:10:32.200 --> 0:10:37.160 random number generation really tricky. Typically, the best we can 0:10:37.240 --> 0:10:40.280 hope for when it comes down to this sort of 0:10:40.320 --> 0:10:44.360 thing is pseudo random numbers. So these are numbers that, 0:10:44.480 --> 0:10:48.200 to an extent, appear to be random, right Like, on 0:10:48.440 --> 0:10:53.640 casual observation, it looks like the computer is generating random numbers. However, 0:10:53.679 --> 0:10:57.440 if you were to really seriously dig down into the process, 0:10:57.880 --> 0:11:00.840 you might discover that they are not really really random 0:11:00.880 --> 0:11:04.480 at all. But we just need them to be random enough, right. 0:11:04.559 --> 0:11:07.440 We need it to be close enough to seeming to 0:11:07.480 --> 0:11:10.200 be random for it to fulfill the function we need 0:11:10.600 --> 0:11:13.719 if it's not truly random. For a lot of applications 0:11:14.280 --> 0:11:19.040 that ends up being, you know, negligible. On a related note, 0:11:19.440 --> 0:11:22.640 there are some types of mathematical problems that have many 0:11:22.679 --> 0:11:27.000 degrees of freedom lots of variables, for example. So a 0:11:27.080 --> 0:11:29.079 problem that does have a lot of variables could have 0:11:29.080 --> 0:11:31.679 a lot of potential solutions, and so it could be 0:11:31.720 --> 0:11:35.200 a challenge for computers to solve. We need algorithms to 0:11:35.200 --> 0:11:38.760 tackle these sorts of problems, to go at them in 0:11:38.800 --> 0:11:43.960 ways that go beyond deterministic computation, which I guess I 0:11:44.000 --> 0:11:48.880 should define that. So, deterministic computation refers to a process 0:11:48.920 --> 0:11:53.720 in which each successive state of an operation depends completely 0:11:53.800 --> 0:11:58.360 on the previous state. So what comes next always depends 0:11:58.440 --> 0:12:01.840 upon what came just before. And I'll give you an example. 0:12:02.160 --> 0:12:03.840 Let's say I give you a math problem, and I 0:12:03.920 --> 0:12:06.439 say you need to add these two numbers together. And 0:12:06.520 --> 0:12:10.120 let's say it's like, uh, five and six, and then 0:12:10.320 --> 0:12:13.800 from the sum of those numbers you have to subtract four. Well, 0:12:14.000 --> 0:12:16.680 you would first add those two numbers together, so five 0:12:16.720 --> 0:12:19.880 plus six you got eleven, and then you would subtract 0:12:20.440 --> 0:12:24.960 four from that number, and so eleven minus four equal seven. 0:12:25.559 --> 0:12:28.880 And this process is deterministic because I gave you those 0:12:28.880 --> 0:12:34.319 specific instructions that computers do really well with deterministic processes. 0:12:34.400 --> 0:12:38.160 These are pretty easy to follow. These sorts of processes 0:12:38.200 --> 0:12:41.880 are by their nature replicable. So in other words, if 0:12:41.920 --> 0:12:44.959 I ask you to do that same operation, if I 0:12:45.000 --> 0:12:48.200 tell you add five and six together and then subtract four, 0:12:49.080 --> 0:12:51.120 it doesn't matter how many times you are you do 0:12:51.240 --> 0:12:53.679 that that process, right, You're always going to come out 0:12:54.280 --> 0:12:56.560 with the same answer. It's always going to come back 0:12:56.920 --> 0:13:00.480 no matter what you do, You're gonna always of seven 0:13:00.480 --> 0:13:04.160 as your answer, just based on that same input. So 0:13:04.559 --> 0:13:08.560 there are a family of algorithms that collectively get the 0:13:08.640 --> 0:13:13.400 name Monte Carlo algorithms, and they're named after Monte Carlo, 0:13:13.640 --> 0:13:16.120 the area of Monaco that is famous for being the 0:13:16.160 --> 0:13:20.199 location of lots of high end casinos have been there. 0:13:20.679 --> 0:13:24.800 It's not really my jam, but it is pretty darn flashy. 0:13:24.920 --> 0:13:29.280 So the reason these algorithms get the name Monte Carlo 0:13:29.360 --> 0:13:34.120 algorithms is that, like gambling, they deal with an element 0:13:34.200 --> 0:13:39.400 of randomization. So gambling is called gambling because you're taking 0:13:39.400 --> 0:13:43.480 a risk. You're gambling, you're betting that you're gonna beat 0:13:43.520 --> 0:13:46.120 the odds in whichever game it is that you're playing. 0:13:46.240 --> 0:13:49.160 And that you're going to achieve an outcome that's favorable 0:13:49.200 --> 0:13:52.839 to you, which you experience as a payout. So, whether 0:13:52.880 --> 0:13:56.440 it's throwing dice or playing a card game, or placing 0:13:56.440 --> 0:14:00.000 bets at a roulette wheel or playing a slot machine, 0:14:00.040 --> 0:14:02.560 you are engaged in an activity in which there is 0:14:02.800 --> 0:14:06.480 some element of chance, at least in theory if the 0:14:06.520 --> 0:14:09.720 game is honest, and what you're hoping for is that 0:14:10.120 --> 0:14:16.160 chance lands in your favor. Similarly, Monte Carlo algorithms often 0:14:16.200 --> 0:14:19.920 focus on chance and risk assessments such as what are 0:14:19.920 --> 0:14:23.760 the odds that if I do this one thing, I'm 0:14:23.760 --> 0:14:27.560 gonna totally regret doing it later? But you know, more 0:14:27.600 --> 0:14:31.720 of the a computational problem and not a lifestyle choice. Well, 0:14:31.760 --> 0:14:37.680 back in ninet, scientists at the Los Alamos Scientific Laboratory, 0:14:37.840 --> 0:14:41.800 including John von Neumann, uh stand All Lam and Nick 0:14:41.880 --> 0:14:46.479 Metropolis propose what would become known as the Metropolis algorithm, 0:14:46.680 --> 0:14:50.320 one of the Monte Carlo algorithms, and the purpose of 0:14:50.320 --> 0:14:55.960 this algorithm was to approximate solutions two very complicated mathematical 0:14:56.040 --> 0:15:01.480 problems where going through a deterministic approach to find the 0:15:01.520 --> 0:15:05.080 definitive answer just wasn't feasible. So In other words, for 0:15:05.240 --> 0:15:09.000 certain complicated math problems, figuring out the quote unquote real 0:15:09.200 --> 0:15:12.440 answer would really just take too long, perhaps to the 0:15:12.440 --> 0:15:15.239 point where you would never get there within your lifetime. 0:15:15.560 --> 0:15:17.440 So you need a way to kind of get a 0:15:17.480 --> 0:15:22.360 ballpark solution that hopefully is closer to being correct than incorrect. 0:15:23.320 --> 0:15:25.360 Doesn't sound like the sort of thing that computers would 0:15:25.360 --> 0:15:27.640 be particularly good at doing right off the bat, right. 0:15:28.240 --> 0:15:33.040 In fact, the algorithm allows computers to mimic a randomized process, 0:15:33.320 --> 0:15:37.400 so it's not truly random, but it's random ish if 0:15:37.440 --> 0:15:40.400 you like, and it uses this to approximate a solution 0:15:40.480 --> 0:15:43.200 to whatever the problem is that you're trying to solve 0:15:43.240 --> 0:15:46.920 that falls into this category. I once saw a simulation 0:15:47.280 --> 0:15:51.120 of a randomized process using the Monte Carlo method that 0:15:51.200 --> 0:15:55.000 I thought was pretty nifty, and it was determining what 0:15:55.160 --> 0:15:57.360 is the value of pie. Let's say that you don't 0:15:57.440 --> 0:16:00.800 know the value of pie and you're just trying to 0:16:00.840 --> 0:16:03.000 figure it out. So and by the way, I mean 0:16:03.040 --> 0:16:05.400 pie is in p I not as in the delicious 0:16:06.000 --> 0:16:10.160 pie dessert treat. So here's the scenario. Imagine that you've 0:16:10.200 --> 0:16:12.600 got a table and the tables like, I don't know, 0:16:13.120 --> 0:16:17.000 three ft to a side, and positioned over this table 0:16:17.120 --> 0:16:20.280 is a robotic arm. And this robotic arm can pick 0:16:20.400 --> 0:16:24.920 up and drop large ball bearings onto the table, and 0:16:25.200 --> 0:16:27.720 the arm can just move over the entire region of 0:16:27.760 --> 0:16:29.560 the table, so it's got a three ft by three 0:16:29.640 --> 0:16:34.040 ft range of motion. And in on this table you 0:16:34.200 --> 0:16:38.080 set down two containers. You've got one that's that's a 0:16:38.080 --> 0:16:42.920 circular container and one that's square. And the square container 0:16:43.040 --> 0:16:47.400 measures six inches to a side. The radius of the 0:16:47.480 --> 0:16:50.840 circular container is also six inches, so that means it's 0:16:50.840 --> 0:16:55.080 got a twelve inch diameter. Right, So those are your containers, 0:16:55.520 --> 0:16:58.440 and you've got your situation with your your robot arm 0:16:58.720 --> 0:17:02.280 above this three ft square table. So the robotic arms 0:17:02.360 --> 0:17:06.680 job is to pick up ball bearings and then from 0:17:06.680 --> 0:17:10.879 a random que will drop that ball bearing somewhere above 0:17:10.960 --> 0:17:13.600 the table. So some of those balls are going to 0:17:13.680 --> 0:17:16.280 fall into the square container, some of them are going 0:17:16.320 --> 0:17:19.040 to fall into the round container, some of them are 0:17:19.040 --> 0:17:22.200 not going to fall in either. And if the process 0:17:22.320 --> 0:17:25.760 is truly random, meaning there's an equal chance that it 0:17:25.800 --> 0:17:28.679 will drop a ball bearing over any given point of 0:17:28.720 --> 0:17:32.480 that table, over time, we would expect to see more 0:17:32.520 --> 0:17:36.119 ball bearings fall into the round container because it has 0:17:36.160 --> 0:17:39.800 a greater area and there's more space for a ball 0:17:39.840 --> 0:17:43.120 bearing to fall into one of these. At the end 0:17:43.119 --> 0:17:47.240 of repeating this process many, many times, we should be 0:17:47.320 --> 0:17:50.600 able to take these two containers and then count the 0:17:50.680 --> 0:17:53.600 number of ball bearings in each of them. And if 0:17:53.640 --> 0:17:56.919 we divide the number of ball bearings in the circular 0:17:57.000 --> 0:17:59.920 container by the number of ball bearings that fell into 0:18:00.040 --> 0:18:03.399 the square container, we're gonna get results that should be 0:18:03.640 --> 0:18:09.920 really close to pie. And you might think, wait, why 0:18:09.960 --> 0:18:13.160 why would the number of ball bearings in one container 0:18:13.280 --> 0:18:17.520 versus another, and then dividing those why would you get pie? Well, 0:18:17.560 --> 0:18:21.280 if you have a process that is uniformly random across 0:18:21.320 --> 0:18:24.879 an area, like our hypothetical three ft square table, the 0:18:24.960 --> 0:18:28.560 probability that a dropped ball bearing will land in one 0:18:28.600 --> 0:18:32.879 of those two specific containers is proportional to that specific 0:18:32.920 --> 0:18:37.439 containers area or cross section. So then we just ask, all, right, well, 0:18:37.440 --> 0:18:39.800 how do we define area? Well, with the square, it's 0:18:39.840 --> 0:18:42.360 really simple, right. We take one side of a square 0:18:42.880 --> 0:18:45.840 in this case, it's six inches, and we multiply it 0:18:45.880 --> 0:18:48.760 by itself six times six. Because all sides of a 0:18:48.800 --> 0:18:50.960 square are equal, we know that the length and the 0:18:51.000 --> 0:18:53.480 width are each going to be six inches. We multiply 0:18:53.520 --> 0:18:56.720 those together. We get thirty six square inches. That is 0:18:56.760 --> 0:19:00.520 the area or cross section of our square container. But 0:19:00.640 --> 0:19:04.639 for our circular container, we take the radius, which again 0:19:05.000 --> 0:19:07.600 this case, the radius is six inches, and we square 0:19:07.640 --> 0:19:12.360 it and then we multiply that number by pie. So 0:19:12.680 --> 0:19:17.200 area for the circular container is six times six squared 0:19:17.359 --> 0:19:20.679 times pie. And if we divide the cross section of 0:19:20.720 --> 0:19:24.680 the circular container by the cross section of the square container, 0:19:25.320 --> 0:19:29.879 the two six squared you know, the two elements the 0:19:29.960 --> 0:19:32.840 squared elements cancel each other out, and so all we're 0:19:32.920 --> 0:19:36.600 left with is pie. So the end result is that 0:19:36.680 --> 0:19:39.760 when we count up these ball bearings that have landed 0:19:39.840 --> 0:19:43.960 randomly in these containers, that that difference, the division that 0:19:44.040 --> 0:19:48.000 we get that should be a close approximation of pie. 0:19:48.040 --> 0:19:50.520 Now it's not going to be precise. Chances are the 0:19:50.600 --> 0:19:53.119 number of ball bearings in the two containers will just 0:19:53.200 --> 0:19:56.600 get you close to pie. But it illustrates how a 0:19:56.720 --> 0:20:01.080 randomized process can help you get to a particular solution 0:20:01.119 --> 0:20:05.040 that might otherwise be difficult to ascertain. There are videos 0:20:05.080 --> 0:20:08.000 on YouTube that show this particular simulation. It's kind of 0:20:08.000 --> 0:20:10.640 a famous one. So you can actually watch and get 0:20:10.960 --> 0:20:12.959 kind of an understanding of what I said to you 0:20:13.000 --> 0:20:16.719 makes no sense whatsoever. There are other options for you 0:20:16.800 --> 0:20:20.000 to look into that might help, And that is a 0:20:20.040 --> 0:20:23.639 great example. But what are the actual algorithms that fall 0:20:23.720 --> 0:20:27.160 into the Monte Carlo methods spectrum? What are they used 0:20:27.160 --> 0:20:30.000 to do well? They can be used to simulate things 0:20:30.119 --> 0:20:35.000 like fluid dynamics, or cellular structures or the interaction of 0:20:35.080 --> 0:20:39.000 disordered materials. So in other words, these are all processes. 0:20:39.320 --> 0:20:42.800 They have a lot of potential variables at play, and 0:20:42.880 --> 0:20:46.480 you can think of variables as representing uncertainty, something that 0:20:46.560 --> 0:20:50.600 computers typically don't do well with. You know, from a 0:20:50.680 --> 0:20:57.400 general stance, computers excel at specific instances rather than potential instances. 0:20:57.440 --> 0:21:01.760 So algorithms like the Metropolis algor rhythm would lead computer 0:21:01.840 --> 0:21:05.840 scientists to develop methodologies to kind of work around the 0:21:05.880 --> 0:21:11.760 limitations of computers and leverage computational power and tackling very 0:21:11.800 --> 0:21:16.159 difficult problems in that way. In the Monte Carlo family 0:21:16.200 --> 0:21:19.280 of algorithms, we typically assume that the results we get 0:21:19.760 --> 0:21:23.359 are going to have a potential for being wrong, like 0:21:23.400 --> 0:21:25.800 there'll be a small percentage of error that we have 0:21:25.840 --> 0:21:28.520 to take into account, and so keeping that in mind, 0:21:28.560 --> 0:21:32.199 we need to frame results as being again approximations of 0:21:32.200 --> 0:21:35.280 an answer, rather than the definitive answer to whatever problem 0:21:35.320 --> 0:21:38.159 it is we're trying to solve. For me, this was 0:21:38.200 --> 0:21:40.400 one of those things that was very difficult to grasp 0:21:40.600 --> 0:21:43.760 for a long time because I was equating it to 0:21:44.040 --> 0:21:47.320 math class, where you're supposed to get the answer. Now, 0:21:47.320 --> 0:21:49.440 when we come back, we'll talk about a few more 0:21:49.560 --> 0:21:52.520 famous algorithms and what they do. But first let's take 0:21:52.760 --> 0:22:02.960 a quick break. Now. In our previous section, I talked 0:22:02.960 --> 0:22:05.680 about a family of algorithms that trace their history back 0:22:05.680 --> 0:22:09.080 to nineteen and so does the next one I want 0:22:09.119 --> 0:22:12.800 to talk about, which was created by George Dantzig, who 0:22:12.960 --> 0:22:17.240 worked for the Rand Corporation. And Danzig created a process 0:22:17.359 --> 0:22:20.840 that would lead to what we call linear programming. So 0:22:21.119 --> 0:22:24.959 at its most basic level, linear programming is about taking 0:22:25.040 --> 0:22:29.639 some function and maximizing or minimizing that function with regard 0:22:29.720 --> 0:22:33.200 to various constraints. But that is super vague, right, I mean, 0:22:33.240 --> 0:22:35.879 it's not terribly helpful. It feels like I'm talking in 0:22:35.880 --> 0:22:39.520 a circle. But this is one that's really important for say, 0:22:39.680 --> 0:22:42.960 business developers. So let's talk about a slightly more specific 0:22:43.080 --> 0:22:46.160 use case. Let's say that you are launching a business 0:22:46.960 --> 0:22:49.680 and you're trying to make some you know, big decisions 0:22:49.840 --> 0:22:51.919 as you're going to do this, and you're going to 0:22:52.240 --> 0:22:57.000 manufacture and sell a product of some sort, some physical thing. Now, 0:22:57.040 --> 0:22:59.840 your whole goal as a business is to make money 0:23:00.280 --> 0:23:02.919 from the work you do, and to do that, you 0:23:02.960 --> 0:23:05.159 need to figure out what your costs are going to 0:23:05.240 --> 0:23:09.359 be and how you cannot just offset these costs but 0:23:09.960 --> 0:23:13.960 make enough money to actually profit from it, so cover 0:23:14.000 --> 0:23:17.439 all your costs plus some extra. So in this case, 0:23:17.920 --> 0:23:20.040 what you're trying to do is figuring out how you 0:23:20.080 --> 0:23:26.200 can minimize costs and maximize profits. Right. The constraints come 0:23:26.200 --> 0:23:29.399 into play as you start to look at specifics, like 0:23:29.560 --> 0:23:32.760 maybe you're gonna partner with a fabrication company, and maybe 0:23:32.760 --> 0:23:35.280 you've actually got a few choices. You've got different companies 0:23:35.320 --> 0:23:37.720 that you could go with. Well, these choices could represent 0:23:37.800 --> 0:23:41.600 constraints in your approach. Perhaps one is more expensive than 0:23:41.640 --> 0:23:45.200 the others, but it can produce a greater volume of product, 0:23:45.760 --> 0:23:48.399 so you'd be able to get more product out to 0:23:48.480 --> 0:23:52.440 market in less time. Or maybe you've got one that's 0:23:52.440 --> 0:23:57.320 more expensive but it's also less likely to have fabrication errors, 0:23:57.359 --> 0:24:00.400 and errors can be both costly and time can assuming 0:24:00.440 --> 0:24:04.320 to address. So you have to quantify all these variables 0:24:04.400 --> 0:24:07.440 and use them as constraints to start figuring out your 0:24:07.520 --> 0:24:11.840 men maxing approach. Here, linear programming simply looks for the 0:24:11.880 --> 0:24:16.000 optimum value of a linear expression, and depending on the 0:24:16.040 --> 0:24:20.560 problem you're trying to solve, like maximizing profit versus minimizing costs, 0:24:20.800 --> 0:24:24.359 you're either looking for the highest value being optimum or 0:24:24.400 --> 0:24:27.240 the lowest value being optimum. Like with costs, you want 0:24:27.280 --> 0:24:29.440 that to be the lowest, and you have to look 0:24:29.440 --> 0:24:33.159 at what constraints are at play with any given expression. 0:24:33.720 --> 0:24:37.480 So Danzing's approach to linear programming, called the simplex method, 0:24:37.960 --> 0:24:41.400