WEBVTT 00:00:00.000 --> 00:00:01.740 I was looking at my phone this morning, you know, 00:00:01.740 --> 00:00:04.320 scrolling through this feed of news stories that 00:00:04.320 --> 00:00:06.419 seem suspiciously tailored to exactly what I 00:00:06.419 --> 00:00:08.740 was anxious about yesterday. And I caught myself 00:00:08.740 --> 00:00:11.779 doing that thing we all do. I muttered, the algorithm 00:00:11.779 --> 00:00:14.960 is out to get me today. It's become this universal 00:00:14.960 --> 00:00:17.260 shorthand. It's the invisible hand, the ghost 00:00:17.260 --> 00:00:21.539 in the machine, the thing we blame for, for social 00:00:21.539 --> 00:00:24.019 media addiction or these weirdly specific ads. 00:00:24.670 --> 00:00:26.989 But as I was prepping for this, I realized I 00:00:26.989 --> 00:00:29.589 was using the word algorithm as a synonym for 00:00:29.589 --> 00:00:33.799 magic or maybe conspiracy. That is the standard 00:00:33.799 --> 00:00:36.000 operating procedure for the 21st century. It 00:00:36.000 --> 00:00:38.960 really is. We've elevated the algorithm singular 00:00:38.960 --> 00:00:41.880 with a capital A into this sort of digital deity. 00:00:41.979 --> 00:00:44.560 It sees all, it knows all, and it controls our 00:00:44.560 --> 00:00:46.679 attention. But you strip away all that Silicon 00:00:46.679 --> 00:00:49.600 Valley mysticism, that word has a very concrete, 00:00:49.719 --> 00:00:52.439 very rigid definition. And frankly, the reality 00:00:52.439 --> 00:00:55.060 of what an algorithm is, and I mean the mathematical 00:00:55.060 --> 00:00:58.219 reality, is far more interesting than the boogeyman 00:00:58.219 --> 00:01:00.780 version we talk about. That's exactly why I wanted 00:01:00.780 --> 00:01:03.140 to do this deep dive. I want to dismantle that 00:01:03.140 --> 00:01:06.200 mysticism. We are going to trace this concept 00:01:06.200 --> 00:01:08.760 from its absolute origins, which surprisingly 00:01:08.760 --> 00:01:12.200 involve writing in mud, not coding in Python. 00:01:12.989 --> 00:01:16.709 all the way to the bleeding edge of quantum mechanics. 00:01:16.989 --> 00:01:19.489 It's a huge journey. It is. But I don't want 00:01:19.489 --> 00:01:20.969 to just stay in the history books. I want to 00:01:20.969 --> 00:01:23.390 understand the mechanics. Yeah. Because my understanding 00:01:23.390 --> 00:01:25.849 is that an algorithm isn't just code. It's a 00:01:25.849 --> 00:01:28.849 specific kind of logic. Precisely. If you take 00:01:28.849 --> 00:01:30.969 nothing else away from this conversation today, 00:01:31.109 --> 00:01:33.829 it should be this. An algorithm is not inherently 00:01:33.829 --> 00:01:37.349 digital. It doesn't require a microchip. You 00:01:37.349 --> 00:01:39.340 can run an algorithm with a pen and paper. Or 00:01:39.340 --> 00:01:41.180 a pile of rocks. You can run one with a pile 00:01:41.180 --> 00:01:44.299 of rocks. At its core, an algorithm is a tool 00:01:44.299 --> 00:01:46.840 for solving a problem. But it's a very, very 00:01:46.840 --> 00:01:49.219 specific type of tool. It's not just a guideline. 00:01:49.959 --> 00:01:52.980 It's a wigger. So let's start there. If I'm a 00:01:52.980 --> 00:01:55.060 computer scientist or a mathematician and I say 00:01:55.060 --> 00:01:57.760 I have an algorithm for this, what am I actually 00:01:57.760 --> 00:01:59.719 promising you? Because I feel like I use the 00:01:59.719 --> 00:02:02.319 word loosely to mean a method, but you're saying 00:02:02.319 --> 00:02:06.250 there's a stricter criteria. Much stricter. So 00:02:06.250 --> 00:02:09.509 in a formal context, an algorithm is a finite 00:02:09.509 --> 00:02:13.169 sequence of well -defined computer -implementable 00:02:13.169 --> 00:02:16.669 instructions, typically to solve a class of problems 00:02:16.669 --> 00:02:19.810 or to perform a computation. Okay, that's a mouthful. 00:02:19.810 --> 00:02:22.949 Let's unpack that. Let's do it. There are a few 00:02:22.949 --> 00:02:24.789 key words in there that carry all the weight. 00:02:24.830 --> 00:02:28.969 The big ones are finite and well -defined. Finite 00:02:28.969 --> 00:02:31.770 seems obvious. It has to end. You can't have 00:02:31.770 --> 00:02:34.229 a recipe that just says stir forever. You would 00:02:34.229 --> 00:02:36.830 think it's obvious, but in computation, it's 00:02:36.830 --> 00:02:39.590 a profound constraint. It's not just that it 00:02:39.590 --> 00:02:42.530 should end, it must end. An algorithm has to 00:02:42.530 --> 00:02:44.509 proceed through a series of well -defined successive 00:02:44.509 --> 00:02:47.129 states and eventually terminate with an output. 00:02:47.370 --> 00:02:49.550 So an infinite loop. An infinite loop is the 00:02:49.550 --> 00:02:51.409 classic example of what is not an algorithm. 00:02:51.870 --> 00:02:53.629 If you write a set of instructions that get stuck 00:02:53.629 --> 00:02:56.710 where step 10 sends you back to step 5 and step 00:02:56.710 --> 00:02:59.469 5 sends you back to step 10 forever, that is 00:02:59.469 --> 00:03:01.270 technically not an algorithm. It's a procedure 00:03:01.270 --> 00:03:03.930 that fails to halt. It's a broken promise. It's 00:03:03.930 --> 00:03:06.930 a broken promise. Exactly. An algorithm is a 00:03:06.930 --> 00:03:09.889 contract. You give me an input, any valid input 00:03:09.889 --> 00:03:12.530 for that class of problem, and I promise I will 00:03:12.530 --> 00:03:15.330 perform these specific steps and I will deliver 00:03:15.330 --> 00:03:18.800 an output. It is. Deterministic. Deterministic. 00:03:18.860 --> 00:03:21.539 Meaning what exactly? Meaning if we both follow 00:03:21.539 --> 00:03:23.840 the algorithm for, say, long division with the 00:03:23.840 --> 00:03:26.479 same two numbers, we absolutely must get the 00:03:26.479 --> 00:03:29.259 same result every time. If we don't, one of us 00:03:29.259 --> 00:03:31.120 didn't follow the algorithm correctly. There's 00:03:31.120 --> 00:03:33.500 no room for interpretation. OK, so that brings 00:03:33.500 --> 00:03:35.680 up attention I found in the research. We have 00:03:35.680 --> 00:03:38.539 this rigorous definition, deterministic, finite, 00:03:38.680 --> 00:03:41.400 correct results. But then we look at the algorithms 00:03:41.400 --> 00:03:44.520 running Netflix or TikTok. Those don't feel deterministic 00:03:44.520 --> 00:03:46.759 at all. Not in the slightest. If I open my feed 00:03:46.759 --> 00:03:49.680 today and then I refresh it a second later, I 00:03:49.680 --> 00:03:51.319 get something different. And half the time, the 00:03:51.319 --> 00:03:54.340 recommendation is garbage. So is that actually 00:03:54.340 --> 00:03:57.000 an algorithm in the strict sense? This is the 00:03:57.000 --> 00:03:58.900 crucial distinction that gets lost in the pop 00:03:58.900 --> 00:04:00.860 culture conversation. It's probably the biggest 00:04:00.860 --> 00:04:03.240 misconception out there. What we colloquially 00:04:03.240 --> 00:04:05.699 call the algorithm on social media is often a 00:04:05.699 --> 00:04:08.300 complex stack of systems, but the core decision 00:04:08.300 --> 00:04:11.120 -making part is largely based on heuristics, 00:04:11.300 --> 00:04:13.960 not just pure algorithms. Okay, differentiate 00:04:13.960 --> 00:04:16.600 those for me. Algorithm versus heuristic. An 00:04:16.600 --> 00:04:19.759 algorithm, in the pure mathematical sense, finds 00:04:19.759 --> 00:04:22.970 the correct answer. If I ask you to sort a list 00:04:22.970 --> 00:04:25.970 of 5 ,000 names alphabetically, there's only 00:04:25.970 --> 00:04:29.910 one correct order. A true sorting algorithm like 00:04:29.910 --> 00:04:33.050 merge sort or quick sort will find that exact 00:04:33.050 --> 00:04:36.269 verifiable order every single time. It optimizes 00:04:36.269 --> 00:04:38.310 for correctness. Okay, that makes sense. One 00:04:38.310 --> 00:04:40.470 right answer. Right. But now let's ask a different 00:04:40.470 --> 00:04:43.129 kind of question. If I ask a system, what is 00:04:43.129 --> 00:04:45.750 the perfect cat video to show this listener right 00:04:45.750 --> 00:04:49.550 now to maximize their happiness? Well, what's 00:04:49.550 --> 00:04:51.189 the correct answer to that? There isn't one. 00:04:51.230 --> 00:04:53.970 It's completely subjective. Exactly. Yeah. There's 00:04:53.970 --> 00:04:57.089 no scientifically verifiable correct answer. 00:04:57.389 --> 00:04:59.990 It's subjective. It's a moving target. And this 00:04:59.990 --> 00:05:02.029 is where we use a heuristic. A heuristic is a 00:05:02.029 --> 00:05:05.810 problem -solving approach that is practical. 00:05:06.050 --> 00:05:08.519 It's a shortcut. A rule of thumb. So it's not 00:05:08.519 --> 00:05:10.240 trying to find the perfect answer because that's 00:05:10.240 --> 00:05:12.600 impossible. It's not. And even if it were possible, 00:05:12.819 --> 00:05:15.360 it would be too slow. A heuristic doesn't guarantee 00:05:15.360 --> 00:05:18.019 the optimal or perfect solution. Instead, it 00:05:18.019 --> 00:05:20.600 provides a satisfactory solution in a reasonable 00:05:20.600 --> 00:05:23.560 amount of time. It trades precision for speed. 00:05:23.839 --> 00:05:26.480 So it's a guess, a highly educated, statistically 00:05:26.480 --> 00:05:29.540 probable guess, but still a guess. It's an estimation. 00:05:30.160 --> 00:05:32.519 I mean, think about it. If Netflix tried to calculate 00:05:32.519 --> 00:05:35.560 the mathematically perfect show for you by analyzing 00:05:35.560 --> 00:05:37.740 every frame of every movie ever made against 00:05:37.740 --> 00:05:40.459 a model of every neuron in your brain, the heat 00:05:40.459 --> 00:05:42.279 death of the universe would happen before the 00:05:42.279 --> 00:05:44.240 video loaded. Right. That's not a great user 00:05:44.240 --> 00:05:46.839 experience. Not at all. So instead, it uses a 00:05:46.839 --> 00:05:49.360 heuristic. A simple one might be, this person 00:05:49.360 --> 00:05:51.259 just watched three action movies starring Dwayne 00:05:51.259 --> 00:05:53.279 Johnson. They'll probably like another one. It's 00:05:53.279 --> 00:05:55.540 a shortcut that usually works. That reframes 00:05:55.540 --> 00:05:58.350 the frustration people feel then. When the algorithm 00:05:58.350 --> 00:06:01.149 serves you something totally bizarre, it's not 00:06:01.149 --> 00:06:03.430 that the machine has some deep insight into your 00:06:03.430 --> 00:06:06.589 soul and is judging you. No. It's that the heuristic 00:06:06.589 --> 00:06:08.670 took a shortcut that didn't land. The rule of 00:06:08.670 --> 00:06:11.870 thumb failed. Precisely. It's a rule of thumb 00:06:11.870 --> 00:06:15.269 encoded into math. And this concept of rules 00:06:15.269 --> 00:06:18.149 brings us to some really useful everyday analogies. 00:06:18.529 --> 00:06:20.629 We often hear that a recipe is an algorithm. 00:06:21.579 --> 00:06:24.639 And that's true, but only if the recipe is rigorous 00:06:24.639 --> 00:06:26.879 enough. What do you mean? Well, a step that says 00:06:26.879 --> 00:06:29.939 add salt to taste is not algorithmic. It requires 00:06:29.939 --> 00:06:32.300 human judgment. It's not well -defined. But a 00:06:32.300 --> 00:06:34.759 step that says add precisely five grams of sodium 00:06:34.759 --> 00:06:38.240 chloride, that is algorithmic. Okay. It removes 00:06:38.240 --> 00:06:41.319 the ambiguity. Completely. Or think about a bureaucracy. 00:06:41.560 --> 00:06:42.879 I was thinking about this the other day. The 00:06:42.879 --> 00:06:45.720 DMV is a massive flesh -and -blood algorithm. 00:06:45.959 --> 00:06:48.240 That's a truly terrifying image. It is, but think 00:06:48.240 --> 00:06:50.379 about the structure. Input. You walk in with 00:06:50.379 --> 00:06:53.410 a specific form. Process. Go to window one. Then 00:06:53.410 --> 00:06:55.329 there's a conditional statement. If the form 00:06:55.329 --> 00:06:57.709 is stamped, then proceed to window two. If it 00:06:57.709 --> 00:06:59.910 is not stamped, go to the back of the line. The 00:06:59.910 --> 00:07:02.490 dreaded else condition. The else condition. And 00:07:02.490 --> 00:07:04.910 it continues like that, step by step, until you 00:07:04.910 --> 00:07:07.649 get the output. A driver's license or rejection 00:07:07.649 --> 00:07:10.529 notice. The clerk in the window isn't supposed 00:07:10.529 --> 00:07:13.050 to use their own judgment or creativity. They 00:07:13.050 --> 00:07:16.060 are a processor. executing a line of code. So 00:07:16.060 --> 00:07:18.459 if the clerk starts making exceptions, you know, 00:07:18.500 --> 00:07:20.420 oh, you seem like a nice person. I'll let that 00:07:20.420 --> 00:07:22.980 missing signature slide. They're essentially 00:07:22.980 --> 00:07:26.839 introducing. bugs into the system. Or features, 00:07:27.040 --> 00:07:29.160 depending on if the exception benefits you. But 00:07:29.160 --> 00:07:31.579 yes, exactly. The whole system relies on the 00:07:31.579 --> 00:07:34.800 rigidity of the steps. And this need for rigid, 00:07:34.939 --> 00:07:37.920 repeatable steps is ancient. It predates computers 00:07:37.920 --> 00:07:40.300 by thousands of years. We tend to think this 00:07:40.300 --> 00:07:42.360 all started with Alan Turing or, you know, Bill 00:07:42.360 --> 00:07:44.959 Gates. But the history of the algorithm is really 00:07:44.959 --> 00:07:47.660 the history of civilization trying to organize 00:07:47.660 --> 00:07:49.800 itself. Let's go back to that origin, because 00:07:49.800 --> 00:07:52.779 the word itself, algorithm. It feels very foreign. 00:07:52.819 --> 00:07:55.079 It has that al - prefix, like algebra. Which 00:07:55.079 --> 00:07:58.120 is a dead giveaway of its Arabic origins. The 00:07:58.120 --> 00:08:01.000 etymology is actually a fascinating story of 00:08:01.000 --> 00:08:03.660 a game of telephone played across centuries and 00:08:03.660 --> 00:08:06.180 languages. We need to go back to the 9th century, 00:08:06.319 --> 00:08:08.600 to the House of Wisdom in Baghdad. The intellectual 00:08:08.600 --> 00:08:10.639 center of the world at the time. Absolutely. 00:08:10.860 --> 00:08:13.420 This was the hub of science, math, and philosophy. 00:08:13.660 --> 00:08:16.639 And there was a Persian scholar there named Mu'mat 00:08:16.639 --> 00:08:19.699 ibn Musa al -Khwarizmi. Al -Khwarizmi. And if 00:08:19.699 --> 00:08:21.800 you say that fast enough... Yeah, it takes a 00:08:21.800 --> 00:08:24.220 few centuries of mangling to get there. Al -Khwarizmi 00:08:24.220 --> 00:08:27.620 was a polymath, a true genius. He wrote a groundbreaking 00:08:27.620 --> 00:08:31.220 book around 825 AD. In Arabic, the title was 00:08:31.220 --> 00:08:34.379 something like Kitab al -Asab al -Hindi, which 00:08:34.379 --> 00:08:36.879 translates to the Book of Indian Computation. 00:08:37.120 --> 00:08:39.779 Indian computation? Yes. He was essentially introducing 00:08:39.779 --> 00:08:42.639 and synthesizing the Hindu -Arabic numeral system, 00:08:42.720 --> 00:08:46.100 our number 0, 1, 2, 3, and so on to the Islamic 00:08:46.100 --> 00:08:49.120 world. And from there, it was eventually transmitted 00:08:49.120 --> 00:08:51.809 to Europe. So before this, Europe is stuck using 00:08:51.809 --> 00:08:55.169 Roman numerals. Yes. And just try doing long 00:08:55.169 --> 00:08:57.450 division with Roman numerals. It's an absolute 00:08:57.450 --> 00:09:01.090 nightmare. How do you divide CXA3 by 9X? It doesn't 00:09:01.090 --> 00:09:03.850 work well at all. Alex Goresmy's book laid out 00:09:03.850 --> 00:09:05.909 the step -by -step procedures for how to add, 00:09:06.070 --> 00:09:09.129 subtract, multiply, and divide using the decimal 00:09:09.129 --> 00:09:11.590 system and place values. It was revolutionary. 00:09:12.070 --> 00:09:14.309 So he wrote the algorithm for doing arithmetic. 00:09:14.429 --> 00:09:16.590 He wrote the book on it. When his works were 00:09:16.590 --> 00:09:19.110 translated into Latin in the 12th century, the 00:09:19.110 --> 00:09:21.269 translators were faced with his name, Alcorismi. 00:09:21.570 --> 00:09:23.029 They didn't know what to do with it, so they 00:09:23.029 --> 00:09:26.870 just Latinized it. It became Algorismus. So Algorism 00:09:26.870 --> 00:09:29.769 originally just meant doing math with decimals, 00:09:29.769 --> 00:09:32.389 the new way. Exactly. Algorism was the name of 00:09:32.389 --> 00:09:34.730 the newfangled method of calculation. It was 00:09:34.730 --> 00:09:37.009 contrasted with the old way. Using an abacus. 00:09:37.549 --> 00:09:39.850 But then fast forward a few hundred years to 00:09:39.850 --> 00:09:43.070 the 15th century, European scholars are rediscovering 00:09:43.070 --> 00:09:45.570 classical Greek texts. Right. They look at this 00:09:45.570 --> 00:09:48.710 word algorithm and they mistakenly confuse it 00:09:48.710 --> 00:09:51.049 with the Greek word arithmos, which means number. 00:09:51.129 --> 00:09:53.509 It's the root of our word arithmetic. They thought 00:09:53.509 --> 00:09:55.629 it had a Greek root that it didn't actually have. 00:09:55.850 --> 00:09:57.330 Right. They thought it was a spelling error. 00:09:57.629 --> 00:10:00.409 So they corrected it. They changed the es in 00:10:00.409 --> 00:10:03.110 algorithm to a phi to make it look more Greek. 00:10:03.289 --> 00:10:06.350 And so algorithm became algorithm. It was essentially 00:10:06.350 --> 00:10:09.850 a typo that stuck. I love that. The very word 00:10:09.850 --> 00:10:13.070 for a precise, rigid set of instructions comes 00:10:13.070 --> 00:10:16.129 from a sloppy translation error. The irony is 00:10:16.129 --> 00:10:18.529 pretty thick, isn't it? But while the name comes 00:10:18.529 --> 00:10:20.990 from the 9th century, the actual practice is 00:10:20.990 --> 00:10:24.029 much, much older. If we define an algorithm as 00:10:24.029 --> 00:10:26.330 a step -by -step procedure to solve a problem, 00:10:26.919 --> 00:10:29.500 We can find them written in cuneiform on clay 00:10:29.500 --> 00:10:32.320 tablets in ancient Mesopotamia, dating back to 00:10:32.320 --> 00:10:35.460 around 2500 BC. This is the Sumerian stuff. Yes. 00:10:36.100 --> 00:10:38.600 Archaeologists unearthed these tablets near Baghdad, 00:10:38.720 --> 00:10:41.019 and they are, for all intents and purposes, textbooks. 00:10:41.500 --> 00:10:44.000 They lay out procedures for division and for 00:10:44.000 --> 00:10:46.539 calculating compound interest for loans. So even 00:10:46.539 --> 00:10:48.960 back then, algorithms were about money. Some 00:10:48.960 --> 00:10:51.659 things never change. But they didn't have algebraic 00:10:51.659 --> 00:10:54.480 symbols like X or Y. They wrote it out in prose, 00:10:54.580 --> 00:10:57.100 like a recipe. Take the number, find its reciprocal, 00:10:57.320 --> 00:11:00.019 multiply by the dividend. It's a script for a 00:11:00.019 --> 00:11:02.379 human computer to follow. And the Babylonians 00:11:02.379 --> 00:11:04.779 took this further with astronomy, right? I read 00:11:04.779 --> 00:11:07.460 they were incredible record keepers. The Babylonians 00:11:07.460 --> 00:11:10.179 were obsessed with predicting the future, both 00:11:10.179 --> 00:11:13.159 for religious and agricultural reasons. Where 00:11:13.159 --> 00:11:15.659 will the planet Jupiter be next month? When is 00:11:15.659 --> 00:11:17.860 the next solar eclipse? You can't just eyeball 00:11:17.860 --> 00:11:20.740 that. You need a rigorous calculation. And they 00:11:20.740 --> 00:11:23.259 developed algorithms for that. They did. They 00:11:23.259 --> 00:11:25.220 developed incredibly sophisticated algorithms 00:11:25.220 --> 00:11:28.340 to track and predict planetary motion, all using 00:11:28.340 --> 00:11:30.960 a base -60 number system. Which is why we still 00:11:30.960 --> 00:11:34.100 have 60 seconds in a minute. 60 minutes in an 00:11:34.100 --> 00:11:37.500 hour and 360 degrees in a circle. We are running 00:11:37.500 --> 00:11:40.019 Babylonian legacy code. We absolutely are. It's 00:11:40.019 --> 00:11:41.960 baked into our daily lives. And the Egyptians 00:11:41.960 --> 00:11:44.779 were doing the same. The Rhine Mathematical Papyrus, 00:11:44.860 --> 00:11:47.919 which dates to around 1550 BC, is basically a 00:11:47.919 --> 00:11:50.500 textbook of algorithms for architects and scribes. 00:11:50.580 --> 00:11:53.259 It has step -by -step guides on how to calculate 00:11:53.259 --> 00:11:55.639 the slope of a pyramid or how to fairly divide 00:11:55.639 --> 00:11:57.919 loaves of bread among workers. Practical problems. 00:11:58.279 --> 00:12:01.720 Very practical. It's all about process. And that 00:12:01.720 --> 00:12:04.419 brings us to the Greeks. Who really formalized 00:12:04.419 --> 00:12:07.500 the idea of mathematical proof and logic? There's 00:12:07.500 --> 00:12:10.179 one ancient algorithm I bet you remember learning 00:12:10.179 --> 00:12:13.080 in school. It's probably the only one that gets 00:12:13.080 --> 00:12:15.379 taught by name in a non -computer science class. 00:12:16.029 --> 00:12:19.210 The sieve of Eratosthenes. The sieve, yes, for 00:12:19.210 --> 00:12:21.389 finding prime numbers. Exactly. And it's such 00:12:21.389 --> 00:12:24.350 a beautiful, elegant, tactile algorithm. It's 00:12:24.350 --> 00:12:26.450 a perfect example of how an algorithm differs 00:12:26.450 --> 00:12:29.009 from just randomly looking for something. Walk 00:12:29.009 --> 00:12:30.870 us through it because the process is the whole 00:12:30.870 --> 00:12:33.350 point. Okay, so imagine you have a big scroll 00:12:33.350 --> 00:12:35.990 and you list out all the numbers from 1 to, say, 00:12:36.009 --> 00:12:38.289 100. You want to find all the prime numbers in 00:12:38.289 --> 00:12:40.809 that list. The brute force way would be to look 00:12:40.809 --> 00:12:43.980 at each number individually. is 91 prime. Let 00:12:43.980 --> 00:12:45.980 me try dividing it by 2, then by 3, by 4, by 00:12:45.980 --> 00:12:49.559 5. That's incredibly slow and error -prone. Eratosthenes, 00:12:49.580 --> 00:12:52.360 a Greek mathematician around 200 BC, came up 00:12:52.360 --> 00:12:55.000 with a much smarter process, an algorithm. Start 00:12:55.000 --> 00:12:57.820 with the first prime, 2. Circle it. Now go through 00:12:57.820 --> 00:12:59.519 your entire list and cross out every multiple 00:12:59.519 --> 00:13:03.320 of 2. So 4, 6, 8, 10, all the way to 100. They're 00:13:03.320 --> 00:13:05.330 all gone. You've eliminated half the numbers 00:13:05.330 --> 00:13:08.470 in one pass. Pretty much. Step two, find the 00:13:08.470 --> 00:13:10.730 very next number on your list that isn't crossed 00:13:10.730 --> 00:13:12.809 out. That number is three. Circle it. It must 00:13:12.809 --> 00:13:15.730 be prime. Now go through the list and cross out 00:13:15.730 --> 00:13:18.049 every multiple of three. So six is already gone, 00:13:18.110 --> 00:13:21.710 but nine, 15, 21, you cross them out. And you 00:13:21.710 --> 00:13:24.490 just keep repeating that same instruction. Find 00:13:24.490 --> 00:13:27.230 the next available number, circle it, then eliminate 00:13:27.230 --> 00:13:28.990 all its multiples. You just keep turning the 00:13:28.990 --> 00:13:32.000 crank. The next number is five. circle it, cross 00:13:32.000 --> 00:13:34.580 out its multiples, then seven. And you keep going. 00:13:34.659 --> 00:13:37.259 When you finish, every single number that is 00:13:37.259 --> 00:13:39.220 left, the ones that haven't been crossed out, 00:13:39.259 --> 00:13:41.460 must be prime. You don't have to check them individually. 00:13:41.740 --> 00:13:44.399 The process guarantees the result. That's the 00:13:44.399 --> 00:13:47.480 key. It's the elimination of guesswork and redundant 00:13:47.480 --> 00:13:50.360 work. It's the triumph of process over brute 00:13:50.360 --> 00:13:52.539 force. And speaking of eliminating guesswork, 00:13:52.559 --> 00:13:54.639 we have to mention another giant from that Islamic 00:13:54.639 --> 00:13:56.899 golden age. We talked about al -Kharizmi, but 00:13:56.899 --> 00:13:59.210 we have to talk about al -Kindi. He was working 00:13:59.210 --> 00:14:01.649 around the same time also in Baghdad. This is 00:14:01.649 --> 00:14:03.669 the code breaker. The father of cryptanalysis. 00:14:04.190 --> 00:14:06.490 Before Al -Kindi, if you intercepted a secret 00:14:06.490 --> 00:14:08.990 message where every letter was substituted for 00:14:08.990 --> 00:14:11.129 another, a simple cipher, you just had to guess. 00:14:11.230 --> 00:14:13.669 It was pure trial and error. Root force again. 00:14:13.789 --> 00:14:16.149 Right. But Al -Kindi, who was also a musician 00:14:16.149 --> 00:14:18.309 and an optician and a philosopher, had a key 00:14:18.309 --> 00:14:21.250 insight. He noticed a pattern in language itself. 00:14:21.759 --> 00:14:23.720 He realized that in any given language, some 00:14:23.720 --> 00:14:26.639 letters appear far more often than others. In 00:14:26.639 --> 00:14:30.019 English, for instance, E's is everywhere. Z is 00:14:30.019 --> 00:14:32.659 very rare. Frequency analysis. He invented it. 00:14:32.740 --> 00:14:35.940 He turned that observation into a rule, an algorithm 00:14:35.940 --> 00:14:39.740 for breaking codes. Step one, get a long, unencrypted 00:14:39.740 --> 00:14:42.080 text in the target language and count the frequency 00:14:42.080 --> 00:14:44.559 of every letter. E appears about 12 % of the 00:14:44.559 --> 00:14:47.600 time, T about 9%, and so on. Make a table. Step 00:14:47.600 --> 00:14:50.340 two. Take the secret encrypted message and count 00:14:50.340 --> 00:14:52.440 the frequency of every symbol in it. Step three. 00:14:52.860 --> 00:14:55.120 Assume the most common symbol in the secret message 00:14:55.120 --> 00:14:57.120 corresponds to the most common letter in the 00:14:57.120 --> 00:14:59.679 language. So you swap it with E. Then swap the 00:14:59.679 --> 00:15:01.620 second most common symbol with T. You keep doing 00:15:01.620 --> 00:15:03.320 that. And the message starts to reveal itself. 00:15:03.620 --> 00:15:06.500 It starts to become readable. He turned code 00:15:06.500 --> 00:15:08.720 breaking from a mystical art into a statistical 00:15:08.720 --> 00:15:11.980 science. A repeatable process. This brings us 00:15:11.980 --> 00:15:13.919 to a really interesting pivot point in the story. 00:15:15.000 --> 00:15:18.159 All of these examples. Sumerian division, the 00:15:18.159 --> 00:15:21.100 Greek sieve, Arab code breaking. They were all 00:15:21.100 --> 00:15:24.379 algorithms designed to be run by humans. The 00:15:24.379 --> 00:15:26.820 computer was a person with a stylus or a quill 00:15:26.820 --> 00:15:30.440 pen. Yes, the wetware. Exactly. But at some point, 00:15:30.460 --> 00:15:32.679 we decided we wanted to outsource the labor. 00:15:32.820 --> 00:15:34.720 We wanted to mechanize the process of thinking. 00:15:34.899 --> 00:15:37.179 The mechanization of the algorithm. This is the 00:15:37.179 --> 00:15:39.940 industrial revolution of thought. And oddly enough, 00:15:40.059 --> 00:15:42.440 the conceptual bridge isn't a calculator. It's 00:15:42.440 --> 00:15:45.360 the clock. The clock. How so? Think about the 00:15:45.360 --> 00:15:47.480 verge escapement mechanism in a weight -driven 00:15:47.480 --> 00:15:50.100 mechanical clock from the Middle Ages. That tick 00:15:50.100 --> 00:15:52.960 -tock sound. That is the sound of a machine controlling 00:15:52.960 --> 00:15:55.559 the release of energy in discrete, quantized 00:15:55.559 --> 00:15:58.059 packets. It is a machine that follows a rigid, 00:15:58.200 --> 00:16:00.220 unthinking rule set to divide the continuous 00:16:00.220 --> 00:16:03.080 flow of time into identical units. Okay, I see 00:16:03.080 --> 00:16:06.299 that. It's automation. It's automation. And it 00:16:06.299 --> 00:16:09.730 inspired the idea of automata. These intricate 00:16:09.730 --> 00:16:12.590 machines and clockwork figures that could move 00:16:12.590 --> 00:16:14.809 by themselves according to a preset program. 00:16:15.070 --> 00:16:18.690 This planted the seed of an idea. If we can make 00:16:18.690 --> 00:16:21.549 a machine follow rules to move, can we make one 00:16:21.549 --> 00:16:24.870 follow rules to think? And this leads us to the 00:16:24.870 --> 00:16:27.509 19th century and the two people who I think are 00:16:27.509 --> 00:16:30.590 the most fascinating what -if story in the history 00:16:30.590 --> 00:16:33.289 of technology, Charles Babbage and Ada Lovelace. 00:16:33.789 --> 00:16:35.649 The tragedy of Babbage and Lovelace is that they 00:16:35.649 --> 00:16:37.669 were living in 1840, but they were thinking in 00:16:37.669 --> 00:16:39.909 1940. They were a century ahead of their time. 00:16:40.070 --> 00:16:42.370 So tell us about Babbage. Charles Babbage was 00:16:42.370 --> 00:16:45.610 a brilliant but famously grumpy English mathematician. 00:16:46.009 --> 00:16:48.889 He was frustrated by the errors he found in hand 00:16:48.889 --> 00:16:51.370 -calculated mathematical tables, like logarithm 00:16:51.370 --> 00:16:53.929 tables. These were full of mistakes made by the 00:16:53.929 --> 00:16:55.950 human computers who compiled them, so he set 00:16:55.950 --> 00:16:58.230 out to build a machine to do it perfectly. His 00:16:58.230 --> 00:17:00.269 first design was the difference engine. The one 00:17:00.269 --> 00:17:02.250 we really care about is the second one, the analytical 00:17:02.250 --> 00:17:06.059 engine. Yes. The analytical engine was a massive 00:17:06.059 --> 00:17:08.480 leap forward. It wasn't just a special purpose 00:17:08.480 --> 00:17:11.099 calculator like the difference engine. Because 00:17:11.099 --> 00:17:14.039 calculators already existed in some form, Pascal 00:17:14.039 --> 00:17:16.920 had built one in the 1600s. Right. So what made 00:17:16.920 --> 00:17:19.000 the analytical engine different? It was designed 00:17:19.000 --> 00:17:21.420 to be a general purpose computer. It had all 00:17:21.420 --> 00:17:23.539 the fundamental components of a modern computer 00:17:23.539 --> 00:17:26.039 just built out of brass gears and steam power. 00:17:26.339 --> 00:17:30.500 It had a store, what we would call memory or 00:17:30.500 --> 00:17:33.420 RAM. It had a mill, what we would call the central 00:17:33.420 --> 00:17:35.920 processing unit or CPU. And it took its instructions 00:17:35.920 --> 00:17:38.660 from punch cards. Yes. He borrowed the idea from 00:17:38.660 --> 00:17:41.269 the jacquard loom. which used punch cards to 00:17:41.269 --> 00:17:44.069 control the patterns in woven fabrics. A hole 00:17:44.069 --> 00:17:46.170 in the card meant one thing, no hole meant another. 00:17:46.650 --> 00:17:48.910 Babbage realized he could use this to feed not 00:17:48.910 --> 00:17:51.309 just data, but instructions into his machine. 00:17:51.589 --> 00:17:53.789 But he never actually built it. He never fully 00:17:53.789 --> 00:17:56.069 built it. He was a perfectionist. He kept changing 00:17:56.069 --> 00:17:58.170 the design. He ran out of funding from the British 00:17:58.170 --> 00:18:01.410 government. And he alienated most of his machinists. 00:18:01.869 --> 00:18:05.769 It was this incredible, sprawling brass and scheme 00:18:05.769 --> 00:18:08.849 monster that existed almost entirely on paper. 00:18:08.990 --> 00:18:10.789 And this is where Ada Lovelace comes in. This 00:18:10.789 --> 00:18:12.789 is where Ada Lovelace, the daughter of the poet 00:18:12.789 --> 00:18:15.680 Lord Byron, enters the story. She was a gifted 00:18:15.680 --> 00:18:18.039 mathematician, which was rare for a woman of 00:18:18.039 --> 00:18:21.440 her era. She met Babbage, saw his plans, and 00:18:21.440 --> 00:18:23.859 understood them perhaps better than he did. She 00:18:23.859 --> 00:18:27.140 saw something he had missed. What was that? Babbage 00:18:27.140 --> 00:18:30.339 saw his machine as a super calculator, a number 00:18:30.339 --> 00:18:33.720 cruncher. Lovely saw its potential as a symbol 00:18:33.720 --> 00:18:36.500 manipulator. She realized that the numbers in 00:18:36.500 --> 00:18:38.859 the machine didn't have to just represent quantities. 00:18:39.299 --> 00:18:41.119 This is that famous quote I have in the notes. 00:18:41.220 --> 00:18:44.160 She wrote that the engine might... compose elaborate 00:18:44.160 --> 00:18:47.339 and scientific pieces of music of any degree 00:18:47.339 --> 00:18:49.940 of complexity or extent. That is the conceptual 00:18:49.940 --> 00:18:52.000 moment the modern computer is born. That's the 00:18:52.000 --> 00:18:54.279 leap. She understood that a number in a gear 00:18:54.279 --> 00:18:56.839 could represent a musical note. It could represent 00:18:56.839 --> 00:18:59.140 a letter of the alphabet, a logical state, a 00:18:59.140 --> 00:19:01.799 pixel. If you can write an algorithm to manipulate 00:19:01.799 --> 00:19:04.319 numbers, you can write an algorithm to manipulate 00:19:04.319 --> 00:19:06.920 any kind of symbol. You can compute reality. 00:19:07.400 --> 00:19:09.740 And to prove it, she wrote the first program 00:19:09.740 --> 00:19:13.220 for this theoretical machine. She did. She translated 00:19:13.220 --> 00:19:15.900 a paper about the analytical engine, and in her 00:19:15.900 --> 00:19:18.400 own notes on the translation, which were three 00:19:18.400 --> 00:19:21.079 times longer than the original paper, she included 00:19:21.079 --> 00:19:24.019 a detailed step -by -step algorithm to calculate 00:19:24.019 --> 00:19:26.700 a complex sequence of numbers called the Bernoulli 00:19:26.700 --> 00:19:28.779 numbers. And that's considered the first piece 00:19:28.779 --> 00:19:31.410 of computer software. It is widely cited as the 00:19:31.410 --> 00:19:34.089 first algorithm specifically designed to be executed 00:19:34.089 --> 00:19:37.210 by a machine, written a full century before the 00:19:37.210 --> 00:19:40.009 first electronic general purpose computer, ENIAC, 00:19:40.210 --> 00:19:43.210 was built. She is rightly considered the world's 00:19:43.210 --> 00:19:45.509 first programmer. But since the machine wasn't 00:19:45.509 --> 00:19:47.710 built, the theory kind of went dormant for a 00:19:47.710 --> 00:19:50.269 while. It was this fascinating dead end until 00:19:50.269 --> 00:19:53.150 the 20th century. And then we get Alan Turing. 00:19:53.309 --> 00:19:56.569 Turing, the man who formalized everything. In 00:19:56.569 --> 00:19:59.769 1936, he published a paper that is arguably the 00:19:59.769 --> 00:20:02.089 most important single document in the history 00:20:02.089 --> 00:20:05.210 of computer science on computable numbers. And 00:20:05.210 --> 00:20:06.609 he wasn't trying to build a computer. He was 00:20:06.609 --> 00:20:09.630 trying to solve a logic puzzle. He was. It was 00:20:09.630 --> 00:20:12.109 a famous problem posed by the mathematician David 00:20:12.109 --> 00:20:14.990 Hilbert called the Entscheidungsproblem, the 00:20:14.990 --> 00:20:17.730 decision problem. The question was, essentially, 00:20:17.990 --> 00:20:20.490 is there an algorithm that can take any logical 00:20:20.490 --> 00:20:23.750 statement and determine, yes or no, whether that 00:20:23.750 --> 00:20:25.990 statement is universally valid? Sort of a truth 00:20:25.990 --> 00:20:28.789 machine. A universal truth machine. To answer 00:20:28.789 --> 00:20:31.349 this question, Turing had to first define what 00:20:31.349 --> 00:20:34.349 an algorithm or a method of computation actually 00:20:34.349 --> 00:20:37.509 was. And to do that, he invented a thought experiment. 00:20:38.459 --> 00:20:40.839 The Turing machine. Now, again, this isn't a 00:20:40.839 --> 00:20:42.680 physical machine you can go out and buy at Best 00:20:42.680 --> 00:20:45.119 Buy. No, it's a mathematical model of computation. 00:20:45.700 --> 00:20:48.359 It's the simplest possible computer you can imagine. 00:20:49.019 --> 00:20:51.880 Imagine an infinitely long tape of paper divided 00:20:51.880 --> 00:20:54.559 into squares, like a roll of toilet paper. And 00:20:54.559 --> 00:20:57.359 there's a little box, the head. that sits over 00:20:57.359 --> 00:20:59.700 one square at a time. This head can do only three 00:20:59.700 --> 00:21:01.180 things. It can read the symbol on the square, 00:21:01.339 --> 00:21:03.339 it can write a new symbol on the square, and 00:21:03.339 --> 00:21:05.720 it can move one square to the left or one square 00:21:05.720 --> 00:21:08.579 to the right. That's it. Read, write, move. That's 00:21:08.579 --> 00:21:11.319 it. And it has a little book of rules, a state 00:21:11.319 --> 00:21:14.240 table, that tells it what to do. For example, 00:21:14.299 --> 00:21:16.539 a rule might say... If you are in state four 00:21:16.539 --> 00:21:18.640 and you read a one, write a one, move to the 00:21:18.640 --> 00:21:21.420 right and change to state six. It sounds incredibly 00:21:21.420 --> 00:21:23.880 simple, almost too simple. That's the genius 00:21:23.880 --> 00:21:26.460 of it, because Turing proved that this incredibly 00:21:26.460 --> 00:21:29.000 simple mechanism can perform any computation 00:21:29.000 --> 00:21:32.099 that is possible to perform. If an algorithm 00:21:32.099 --> 00:21:35.490 exists to solve a problem. Turing machine can 00:21:35.490 --> 00:21:37.369 run it. This is the universal Turing machine. 00:21:37.509 --> 00:21:40.569 Exactly. Your iPhone, a supercomputer at NASA, 00:21:40.849 --> 00:21:43.589 they're just very, very fast, very small, very 00:21:43.589 --> 00:21:46.309 fancy Turing machines. They don't do anything 00:21:46.309 --> 00:21:48.690 fundamentally different from read, write, and 00:21:48.690 --> 00:21:52.150 move based on a set of rules. This is the theoretical 00:21:52.150 --> 00:21:54.910 basis of all modern computing. But Turing also 00:21:54.910 --> 00:21:56.769 proved something devastating with this model. 00:21:57.069 --> 00:22:00.009 He did. By defining what was computable, he could 00:22:00.009 --> 00:22:01.710 also prove that there are some problems that 00:22:01.710 --> 00:22:04.549 are uncomputable, problems for which no algorithm 00:22:04.549 --> 00:22:06.369 can ever exist. This is the halting problem, 00:22:06.509 --> 00:22:09.650 right? The famous halting problem. In simple 00:22:09.650 --> 00:22:13.009 terms, the question is this. Can you write a 00:22:13.009 --> 00:22:16.210 program, let's call it program H, that can analyze 00:22:16.210 --> 00:22:19.150 any other program and its input and tell you 00:22:19.150 --> 00:22:21.789 with 100 % certainty if that other program will 00:22:21.789 --> 00:22:25.309 eventually finish, that is, halt. Or if it will 00:22:25.309 --> 00:22:27.609 get stuck in an infinite loop and run forever? 00:22:27.890 --> 00:22:30.130 And the answer is? The answer is a resounding 00:22:30.130 --> 00:22:33.089 no. It is logically impossible. He proved it 00:22:33.089 --> 00:22:35.450 with a beautiful contradiction. You can't write 00:22:35.450 --> 00:22:37.349 a general purpose algorithm that can perfectly 00:22:37.349 --> 00:22:39.450 predict the behavior of all other algorithms. 00:22:39.690 --> 00:22:41.990 This means there are hard fundamental limits 00:22:41.990 --> 00:22:44.869 to what computation can ever achieve. We can't 00:22:44.869 --> 00:22:46.630 solve everything. That is a humbling thought. 00:22:46.769 --> 00:22:49.009 We built these machines to be these perfect logical 00:22:49.009 --> 00:22:51.390 engines. And right at their theoretical foundation, 00:22:51.589 --> 00:22:53.630 there's a giant sign that says, here be dragons. 00:22:54.109 --> 00:22:57.009 Or some problems are unsolvable. Exactly. But 00:22:57.009 --> 00:22:58.750 for the problems we can solve, the next logical 00:22:58.750 --> 00:23:01.029 question is, well, how efficiently can we solve 00:23:01.029 --> 00:23:03.250 them? Because as we moved from Babbage's gears 00:23:03.250 --> 00:23:06.150 to vacuum tubes to silicon chips, we quickly 00:23:06.150 --> 00:23:08.609 realized that not all algorithms are created 00:23:08.609 --> 00:23:11.849 equal. Some are incredibly fast. Some are agonizingly, 00:23:11.849 --> 00:23:14.589 unusably slow. And this is where we get into 00:23:14.589 --> 00:23:17.250 algorithmic analysis. This is the stuff that 00:23:17.250 --> 00:23:19.690 makes first -year computer science students sweat. 00:23:20.460 --> 00:23:23.619 The dreaded big O notation. Right. Let's try 00:23:23.619 --> 00:23:26.759 to demystify this. The key idea, as I understand 00:23:26.759 --> 00:23:28.940 it, is that we don't measure an algorithm's speed 00:23:28.940 --> 00:23:32.160 in seconds, right? Because a supercomputer from 00:23:32.160 --> 00:23:35.319 2024 is obviously going to be faster than a desktop 00:23:35.319 --> 00:23:39.039 from 1994. Correct. Measuring in seconds is useless 00:23:39.039 --> 00:23:41.759 because hardware keeps getting faster. So instead, 00:23:41.960 --> 00:23:44.240 we measure an algorithm's efficiency in terms 00:23:44.240 --> 00:23:46.880 of its growth rate. How many steps or operations 00:23:46.880 --> 00:23:49.079 does the algorithm take relative to the size 00:23:49.079 --> 00:23:51.359 of the input? We use the letter N to represent 00:23:51.359 --> 00:23:53.920 the size of the input. Okay, N. So if I'm sorting 00:23:53.920 --> 00:23:56.980 a deck of playing cards, N is 52. If I'm sorting 00:23:56.980 --> 00:23:59.400 the phone book for New York City, N is, what, 00:23:59.440 --> 00:24:02.099 8 million? Exactly. And big O notation describes 00:24:02.099 --> 00:24:04.859 how the number of operations grows as N gets 00:24:04.859 --> 00:24:07.000 bigger. Let's start with the best case scenario. 00:24:07.200 --> 00:24:10.160 This is called O1, or constant time. Constant 00:24:10.160 --> 00:24:12.259 time. This means that no matter how big N is, 00:24:12.420 --> 00:24:14.660 the task always takes the same amount of time. 00:24:14.740 --> 00:24:17.180 It takes just one step. An example would be, 00:24:17.259 --> 00:24:20.200 give me the first name on a list. Whether that 00:24:20.200 --> 00:24:23.579 list has 10 names or 10 billion names, grabbing 00:24:23.579 --> 00:24:26.700 the very first one is a single operation. That's 00:24:26.700 --> 00:24:29.420 the dream. Instant access, regardless of scale. 00:24:29.599 --> 00:24:33.619 It is. The next level up is ON, or linear time. 00:24:33.839 --> 00:24:36.259 This is the most intuitive one. This is our brute 00:24:36.259 --> 00:24:40.259 force search. If I ask you, is the name Waldo 00:24:40.259 --> 00:24:43.849 in this unorganized pile of 100 papers? You have 00:24:43.849 --> 00:24:46.269 to look at every single paper one by one. You 00:24:46.269 --> 00:24:48.150 might get lucky and find them on the first try. 00:24:48.269 --> 00:24:50.529 You might. That's the best case. But we care 00:24:50.529 --> 00:24:52.490 about the worst case. In the worst case, Waldo 00:24:52.490 --> 00:24:54.750 is on the very last paper or not there at all. 00:24:54.809 --> 00:24:57.329 So if you have 100 papers and 100 could take 00:24:57.329 --> 00:24:59.549 you 100 steps. If you have a million papers, 00:24:59.730 --> 00:25:01.869 it could take a million steps. The work grows 00:25:01.869 --> 00:25:04.309 in a straight line equally with the data. It's 00:25:04.309 --> 00:25:07.130 manageable for small tasks, but it doesn't scale 00:25:07.130 --> 00:25:09.490 well if you have truly big data. Not at all. 00:25:09.549 --> 00:25:11.329 And this is why the next level up is where the 00:25:11.329 --> 00:25:13.680 real magic of computer science. happens. This 00:25:13.680 --> 00:25:16.960 is O log on or logarithmic time. This is the 00:25:16.960 --> 00:25:19.599 phone book analogy. The classic phone book analogy. 00:25:20.019 --> 00:25:22.680 It perfectly illustrates the power of an algorithm 00:25:22.680 --> 00:25:25.740 called binary search. So imagine the phone book 00:25:25.740 --> 00:25:28.539 again with its millions of names. But this time, 00:25:28.619 --> 00:25:31.259 critically, it's sorted alphabetically. You're 00:25:31.259 --> 00:25:34.390 looking for Smith. You don't start at A and read 00:25:34.390 --> 00:25:36.190 every name. That would be O -N. Well, you open 00:25:36.190 --> 00:25:37.630 it roughly to the middle. You open it to the 00:25:37.630 --> 00:25:39.869 middle. You see names starting with M. You know, 00:25:39.890 --> 00:25:42.789 Smith comes after M. So you can take the entire 00:25:42.789 --> 00:25:45.289 first half of the book from A to M and throw 00:25:45.289 --> 00:25:47.690 it away. You just deleted half the problem in 00:25:47.690 --> 00:25:49.880 a single step. In one step. Then you take the 00:25:49.880 --> 00:25:52.799 remaining half from M to Z and you cut that in 00:25:52.799 --> 00:25:56.160 half. You land on R. Still not there. Smith is 00:25:56.160 --> 00:25:59.059 after R. So you throw away the M to R section. 00:25:59.279 --> 00:26:01.619 You keep splitting the problem in half again 00:26:01.619 --> 00:26:03.700 and again. So how much faster is that, really? 00:26:03.880 --> 00:26:06.299 It's astronomically faster. Let's use that phone 00:26:06.299 --> 00:26:09.220 book of, say, one million names. A linear search, 00:26:09.460 --> 00:26:11.880 O in the worst case, takes one million steps. 00:26:12.240 --> 00:26:16.859 A binary search, O log N, takes about 20 steps. 00:26:17.099 --> 00:26:20.160 Wait, only 20. From a million down to 20? That's 00:26:20.160 --> 00:26:22.720 the power of logarithms. Two to the power of 00:26:22.720 --> 00:26:25.579 20 is roughly a million. You only need to cut 00:26:25.579 --> 00:26:28.420 the deck 20 times to find one specific card in 00:26:28.420 --> 00:26:31.019 a deck of a million. This is what makes searching 00:26:31.019 --> 00:26:33.839 massive databases possible. This is the power 00:26:33.839 --> 00:26:36.720 of a good algorithm. It turns an impossible task 00:26:36.720 --> 00:26:40.019 into a trivial one. But then, then there's the 00:26:40.019 --> 00:26:43.019 dark side. The bad algorithms. The ones that 00:26:43.019 --> 00:26:46.079 cause systems to grind to a halt. Oh, yes. The 00:26:46.079 --> 00:26:48.950 ones to be avoided at all costs. Yes. The next 00:26:48.950 --> 00:26:52.910 step up is O -N or quadratic time. This is what 00:26:52.910 --> 00:26:54.789 often happens when you have a nested Luke, when 00:26:54.789 --> 00:26:57.369 you have to compare every single item in a list 00:26:57.369 --> 00:27:00.089 to every other single item in that list. Can 00:27:00.089 --> 00:27:02.269 you give me an example? Sure. Imagine you have 00:27:02.269 --> 00:27:04.329 a list of 100 people in a room and you want to 00:27:04.329 --> 00:27:06.609 see if any two of them share a birthday. The 00:27:06.609 --> 00:27:08.549 simplest algorithm is to ask the first person 00:27:08.549 --> 00:27:10.089 their birthday, then compare it to the other 00:27:10.089 --> 00:27:12.549 99 people. Then you go to the second person and 00:27:12.549 --> 00:27:14.470 compare their birthday to the other 98 people. 00:27:15.039 --> 00:27:17.799 You see, for N people, you're doing roughly N 00:27:17.799 --> 00:27:20.160 squared comparisons. So if you have 10 people, 00:27:20.299 --> 00:27:22.500 it takes about 100 comparisons. If you have 100 00:27:22.500 --> 00:27:24.740 people, it takes 10 ,000. If you have 1 ,000 00:27:24.740 --> 00:27:27.259 people, it takes a million steps. The complexity 00:27:27.259 --> 00:27:30.099 explodes. This is why a startup's new social 00:27:30.099 --> 00:27:33.359 media app works perfectly fine with 50 beta testers 00:27:33.359 --> 00:27:35.920 and then completely crashes the moment they get 00:27:35.920 --> 00:27:38.720 5 ,000 users. Their algorithm was probably OM. 00:27:38.960 --> 00:27:40.680 And it gets even worse than that, doesn't it? 00:27:40.720 --> 00:27:44.000 It gets much, much worse. The truly terrifying 00:27:44.000 --> 00:27:47.920 one is O2N, or exponential time. This is the 00:27:47.920 --> 00:27:50.940 heat death of the universe algorithm. With exponential 00:27:50.940 --> 00:27:53.200 time, if you add just one more element to the 00:27:53.200 --> 00:27:55.079 input, you double the amount of work. Double 00:27:55.079 --> 00:27:57.720 it. Double it. The traveling salesman problem 00:27:57.720 --> 00:28:00.299 we mentioned earlier is a classic example. Finding 00:28:00.299 --> 00:28:02.319 the absolute shortest route to visit own cities 00:28:02.319 --> 00:28:04.279 requires checking a number of paths that grows 00:28:04.279 --> 00:28:07.440 exponentially. If you can solve it for 20 cities, 00:28:07.619 --> 00:28:09.980 adding the 21st city makes it twice as hard. 00:28:10.400 --> 00:28:12.519 Adding the 22nd makes it four times as hard. 00:28:12.920 --> 00:28:15.359 Very quickly, the problem becomes unsolvable 00:28:15.359 --> 00:28:18.279 for even the fastest supercomputers. So our modern 00:28:18.279 --> 00:28:21.059 security, like for banking and things, is basically 00:28:21.059 --> 00:28:22.920 relying on the inefficiency of these kinds of 00:28:22.920 --> 00:28:25.920 algorithms. Exactly. Modern encryption is built 00:28:25.920 --> 00:28:28.119 on the fact that certain mathematical problems, 00:28:28.359 --> 00:28:30.920 like factoring a very large number into its two 00:28:30.920 --> 00:28:33.740 prime components, are believed to be in this 00:28:33.740 --> 00:28:36.720 exponential or near exponential class for classical 00:28:36.720 --> 00:28:39.480 computers. It's not that it's impossible. It's 00:28:39.480 --> 00:28:42.160 that the O2n algorithm would take so long to 00:28:42.160 --> 00:28:44.640 run that the sun will burn out before it finishes. 00:28:44.839 --> 00:28:48.160 We rely on problems being intractable. We also 00:28:48.160 --> 00:28:50.039 need to touch on space complexity. We always 00:28:50.039 --> 00:28:52.779 focus on time, on speed, but computers have a 00:28:52.779 --> 00:28:55.180 finite amount of memory. Right, and there's very 00:28:55.180 --> 00:28:57.319 often a direct trade -off between the two. We 00:28:57.319 --> 00:28:59.660 call it the space -time trade -off. You can frequently 00:28:59.660 --> 00:29:02.299 make an algorithm run faster by allowing it to 00:29:02.299 --> 00:29:04.319 use more memory. How does that work? Think of 00:29:04.319 --> 00:29:07.000 it like this. You're a travel agent, and you 00:29:07.000 --> 00:29:08.779 constantly need to know the driving distance 00:29:08.779 --> 00:29:11.099 between any two major cities in the country. 00:29:11.839 --> 00:29:14.779 Option A is to save space. Every time a client 00:29:14.779 --> 00:29:17.099 asks, you use a mat and a formula to calculate 00:29:17.099 --> 00:29:19.900 the distance on the fly. This takes time CPU 00:29:19.900 --> 00:29:23.170 cycles, but uses very little memory. Option B 00:29:23.170 --> 00:29:25.609 is to save time. You spend a week calculating 00:29:25.609 --> 00:29:27.990 the distance between every possible pair of cities 00:29:27.990 --> 00:29:30.490 and write it all down in a giant lookup table, 00:29:30.609 --> 00:29:33.710 a huge book. Now, when a client asks, looking 00:29:33.710 --> 00:29:36.390 up the answer is instant, very fast time complexity. 00:29:36.569 --> 00:29:39.210 But you have to store and carry around this enormous 00:29:39.210 --> 00:29:41.690 book, which takes up a huge amount of space or 00:29:41.690 --> 00:29:44.049 memory. And modern computers have so much cheap 00:29:44.049 --> 00:29:46.609 RAM that we usually lazy and choose option B. 00:29:46.789 --> 00:29:48.990 We do. We are very wasteful of space today in 00:29:48.990 --> 00:29:51.339 many applications because memory is cheap. But 00:29:51.339 --> 00:29:53.700 back in the 1960s, programming for the Apollo 00:29:53.700 --> 00:29:56.339 missions, or even today in small embedded systems 00:29:56.339 --> 00:29:58.299 like the chip in your toaster, your car's engine, 00:29:58.500 --> 00:30:01.140 space complexity is absolutely critical. You 00:30:01.140 --> 00:30:03.539 have to be frugal. So we have the metrics for 00:30:03.539 --> 00:30:06.119 judging them. Now I want to open what you called 00:30:06.119 --> 00:30:08.799 the bestiary. I want to walk through the different 00:30:08.799 --> 00:30:11.160 species of algorithms, the different paradigms, 00:30:11.180 --> 00:30:12.940 because they really do have different personalities. 00:30:13.279 --> 00:30:14.980 They really do. They have different philosophies 00:30:14.980 --> 00:30:16.799 of problem solving. Okay, let's start with the 00:30:16.799 --> 00:30:19.619 one we've touched on already, brute force. The 00:30:19.619 --> 00:30:22.559 try -everything approach. Brute force is the 00:30:22.559 --> 00:30:25.319 simplest, most obvious, and often dumbest way 00:30:25.319 --> 00:30:27.799 to solve a problem. It's about systematically 00:30:27.799 --> 00:30:31.039 trying every single possible option until you 00:30:31.039 --> 00:30:33.619 find the right one. The quintessential example 00:30:33.619 --> 00:30:36.539 is cracking a password. If you don't know the 00:30:36.539 --> 00:30:38.819 password, you try A, then B, then C, then A, 00:30:38.839 --> 00:30:41.160 A, A, A, C. It's guaranteed to work eventually. 00:30:41.559 --> 00:30:44.549 Guaranteed. But for any non -trivial password, 00:30:44.829 --> 00:30:47.289 eventually might be longer than the age of the 00:30:47.289 --> 00:30:50.390 universe. It's the baseline against which smarter 00:30:50.390 --> 00:30:53.190 algorithms are measured. OK, so a smarter approach 00:30:53.190 --> 00:30:56.029 might be divide and conquer. Yes. Divide and 00:30:56.029 --> 00:30:58.670 conquer is a very powerful and elegant strategy. 00:30:59.029 --> 00:31:02.170 It's military strategy applied to math. You're 00:31:02.170 --> 00:31:05.950 faced with a huge, scary problem. The philosophy 00:31:05.950 --> 00:31:09.509 is don't try to solve the huge problem. break 00:31:09.509 --> 00:31:12.329 it down into smaller, identical subproblems, 00:31:12.329 --> 00:31:15.289 solve those little subproblems, and then combine 00:31:15.289 --> 00:31:17.609 their solutions to solve the original big one. 00:31:17.789 --> 00:31:19.750 This is the merge sort algorithm you mentioned 00:31:19.750 --> 00:31:21.970 for sorting lists. Merge sort is the textbook 00:31:21.970 --> 00:31:24.589 example. You have a huge unsorted list of numbers. 00:31:24.750 --> 00:31:26.849 Don't try to sort it all at once. Just split 00:31:26.849 --> 00:31:29.509 it in half. Now you have two smaller, easier 00:31:29.509 --> 00:31:32.049 problems. Split those halves. Keep splitting 00:31:32.049 --> 00:31:34.089 and splitting until all you have are tiny little 00:31:34.089 --> 00:31:36.609 lists with just one number in them. And a list 00:31:36.609 --> 00:31:39.329 with only one number is by d***. Definition already 00:31:39.329 --> 00:31:41.990 sorted. It is. The conquer part was easy. Now 00:31:41.990 --> 00:31:44.299 comes the combine part. You start merging those 00:31:44.299 --> 00:31:46.539 little one -item lists back together into two 00:31:46.539 --> 00:31:48.519 -item lists, but you merge them in sorted order. 00:31:48.759 --> 00:31:50.940 Then you merge the two -item lists into sorted 00:31:50.940 --> 00:31:53.440 four -item lists. You keep zippering them back 00:31:53.440 --> 00:31:55.940 together, and at the end, you have one big, perfectly 00:31:55.940 --> 00:31:58.720 sorted list. It's elegant, it's reliable, and 00:31:58.720 --> 00:32:01.319 it's much, much faster. A dumb sort like bubble 00:32:01.319 --> 00:32:03.920 sort. So dividing conquer is about breaking a 00:32:03.920 --> 00:32:06.420 scary problem into a bunch of tiny, non -scary 00:32:06.420 --> 00:32:09.519 problems. Precisely. Now, related to this is 00:32:09.519 --> 00:32:12.829 the concept of recursion versus iteration. Two 00:32:12.829 --> 00:32:15.150 different ways to implement that repeat a process 00:32:15.150 --> 00:32:17.690 idea. Okay. Iteration is the one most people 00:32:17.690 --> 00:32:20.490 are familiar with. It means using loops, a for 00:32:20.490 --> 00:32:23.450 loop or a while loop. You're explicitly telling 00:32:23.450 --> 00:32:26.670 the computer, do this thing 10 times or keep 00:32:26.670 --> 00:32:28.549 doing this thing until this condition is met. 00:32:28.650 --> 00:32:31.309 It's very direct. Recursion is a bit more mind 00:32:31.309 --> 00:32:34.109 bending. A recursive algorithm is one that calls 00:32:34.109 --> 00:32:35.910 itself to solve a smaller version of the same 00:32:35.910 --> 00:32:38.009 problem. It calls itself. It calls itself. The 00:32:38.009 --> 00:32:40.109 classic example is the Tower of Hanoi puzzle. 00:32:40.599 --> 00:32:43.059 To move a stack of five disks, the recursive 00:32:43.059 --> 00:32:45.880 solution is move the top four disks to the spare 00:32:45.880 --> 00:32:48.240 peg, then move the bottom disk to the destination, 00:32:48.579 --> 00:32:51.460 then move the four disks on top of it. But how 00:32:51.460 --> 00:32:53.319 do you move four disks? Well, the algorithm calls 00:32:53.319 --> 00:32:55.240 itself. To move four disks, you first move three 00:32:55.240 --> 00:32:57.640 disks. It keeps breaking it down until it gets 00:32:57.640 --> 00:32:59.960 to the simple case of moving just one disk. Sounds 00:32:59.960 --> 00:33:03.099 elegant, but also potentially dangerous. Like 00:33:03.099 --> 00:33:05.700 it could easily lead to an infinite loop. It 00:33:05.700 --> 00:33:08.930 can if you're not careful. Every recursive algorithm 00:33:08.930 --> 00:33:11.569 needs a base case, a condition that tells it 00:33:11.569 --> 00:33:13.809 when to stop calling itself and just return an 00:33:13.809 --> 00:33:16.470 answer. Without that, you get a stack overflow, 00:33:16.690 --> 00:33:18.930 which is the recursive version of an infinite 00:33:18.930 --> 00:33:21.269 loop. Let's move on to the greedy algorithms. 00:33:21.490 --> 00:33:23.549 You call these the impulsive ones. The ones that 00:33:23.549 --> 00:33:26.720 lack long -term vision. A greedy algorithm makes 00:33:26.720 --> 00:33:29.420 the locally optimal choice at every single stage, 00:33:29.640 --> 00:33:32.380 hoping that a series of locally optimal choices 00:33:32.380 --> 00:33:35.200 will lead to a globally optimal solution. The 00:33:35.200 --> 00:33:37.859 live in the moment algorithm. Exactly. Imagine 00:33:37.859 --> 00:33:40.299 you are navigating a maze where every path is 00:33:40.299 --> 00:33:42.980 lined with coins. A greedy algorithm stands at 00:33:42.980 --> 00:33:44.859 a junction. It looks left and sees a path with 00:33:44.859 --> 00:33:47.440 one coin. It looks right and sees a path with 00:33:47.440 --> 00:33:50.279 five coins. It immediately goes right. It doesn't 00:33:50.279 --> 00:33:52.339 care if the path on the right leads to a dead 00:33:52.339 --> 00:33:55.220 end or a monster 10 steps later. the biggest 00:33:55.220 --> 00:33:57.960 payoff right now. The marshmallow test of algorithms. 00:33:58.220 --> 00:34:01.440 It always eats the marshmallow. Yes. It has no 00:34:01.440 --> 00:34:04.339 impulse control. The traveling salesman problem 00:34:04.339 --> 00:34:06.680 is another good example. The greedy approach 00:34:06.680 --> 00:34:09.579 says, from where I am now, what is the absolute 00:34:09.579 --> 00:34:11.980 closest city I haven't visited yet? Okay, I'll 00:34:11.980 --> 00:34:14.599 go there. And it repeats that from every city. 00:34:15.119 --> 00:34:16.780 And does that actually work? Does it give you 00:34:16.780 --> 00:34:19.119 the shortest overall path? It gives you a path, 00:34:19.179 --> 00:34:21.340 and it's very fast to calculate. But it usually 00:34:21.340 --> 00:34:24.099 isn't the shortest path. It might send you to 00:34:24.099 --> 00:34:26.639 a nearby city that is way out on a limb, forcing 00:34:26.639 --> 00:34:29.420 you to make a very long trip later on. It gets 00:34:29.420 --> 00:34:32.239 stuck in local optima. So if you need the absolute 00:34:32.239 --> 00:34:35.940 best, perfect path, greedy fails, what do you 00:34:35.940 --> 00:34:38.199 use instead? Well, for that kind of problem, 00:34:38.280 --> 00:34:40.219 you might use dynamic programming. This is like 00:34:40.219 --> 00:34:42.940 the smart, cautious older sibling of the greedy 00:34:42.940 --> 00:34:45.880 algorithm. Dynamic programming also breaks a 00:34:45.880 --> 00:34:47.980 problem down into subproblems, but it has a memory. 00:34:48.179 --> 00:34:51.119 It uses a technique called memoization. Memoization. 00:34:51.340 --> 00:34:56.119 That's M -E -M -O, not memorization. Right. Memoization. 00:34:56.199 --> 00:34:58.940 It literally means writing it down in a memo. 00:34:59.360 --> 00:35:01.840 Imagine you are calculating the Fibonacci sequence, 00:35:01.980 --> 00:35:04.559 where each number is the sum of the previous 00:35:04.559 --> 00:35:08.110 two. A naive recursive algorithm to find the 00:35:08.110 --> 00:35:10.250 50th number would be incredibly slow because 00:35:10.250 --> 00:35:12.949 it recalculates the same values over and over 00:35:12.949 --> 00:35:15.769 and over again. Okay. A dynamic programming algorithm 00:35:15.769 --> 00:35:18.289 says, wait a minute, I've already calculated 00:35:18.289 --> 00:35:20.550 the value for the 10th Fibonacci number. I wrote 00:35:20.550 --> 00:35:22.349 it down in my notebook. Instead of recalculating 00:35:22.349 --> 00:35:24.690 it, I'll just look it up. It caches the results 00:35:24.690 --> 00:35:26.730 of subproblems so it never has to do the same 00:35:26.730 --> 00:35:29.250 work twice. And that's a huge speed up. It turns 00:35:29.250 --> 00:35:32.289 many exponential problems into linear or polynomial 00:35:32.289 --> 00:35:35.099 ones. This is fundamental to... how things like 00:35:35.099 --> 00:35:37.639 Google Maps can find the shortest route so quickly. 00:35:37.960 --> 00:35:40.300 It doesn't recalculate every road in the world 00:35:40.300 --> 00:35:42.800 every time you ask for directions. It uses known 00:35:42.800 --> 00:35:45.840 distances of smaller segments, solved subproblems, 00:35:45.840 --> 00:35:48.300 to stitch together a full route. I want to touch 00:35:48.300 --> 00:35:50.619 on one more category that seems really counterintuitive 00:35:50.619 --> 00:35:54.659 to me. Randomized algorithms. Why on earth would 00:35:54.659 --> 00:35:57.300 we want a computer, our machine of pure logic, 00:35:57.480 --> 00:36:00.159 to do something random? This is for when the 00:36:00.159 --> 00:36:03.659 problem is so monstrously big or complex that 00:36:03.659 --> 00:36:06.539 finding an exact answer is just too expensive 00:36:06.539 --> 00:36:09.719 or would take too long. Sometimes a probably 00:36:09.719 --> 00:36:11.960 correct answer that you can get in a second is 00:36:11.960 --> 00:36:13.800 much more valuable than a guaranteed correct 00:36:13.800 --> 00:36:16.059 answer that takes a year. We generally have two 00:36:16.059 --> 00:36:19.630 flavors. Monte Carlo and Las Vegas. Named after 00:36:19.630 --> 00:36:21.789 the gambling meccas, I assume. They are, and 00:36:21.789 --> 00:36:24.030 the analogy is perfect. A Las Vegas algorithm 00:36:24.030 --> 00:36:26.969 is like a slot machine that is guaranteed to 00:36:26.969 --> 00:36:29.329 eventually pay out the jackpot. It always gives 00:36:29.329 --> 00:36:32.250 the correct, deterministic answer. But you don't 00:36:32.250 --> 00:36:34.269 know how long it will take. You might get lucky 00:36:34.269 --> 00:36:36.329 and it finishes in a second, or you might be 00:36:36.329 --> 00:36:38.010 sitting there pulling the lever for an hour. 00:36:38.730 --> 00:36:40.429 but you can trust the result when you get it. 00:36:40.530 --> 00:36:43.349 Okay, so always correct, but runtime is random. 00:36:43.510 --> 00:36:46.349 What about Monte Carlo? A Monte Carlo algorithm 00:36:46.349 --> 00:36:49.010 is the opposite. It runs for a fixed, predictable 00:36:49.010 --> 00:36:51.809 amount of time, but the answer it gives has a 00:36:51.809 --> 00:36:54.610 small probability of being wrong. It's like playing 00:36:54.610 --> 00:36:56.389 a round of poker. You finish the hand in a few 00:36:56.389 --> 00:36:58.309 minutes, but you might have lost. It might say 00:36:58.309 --> 00:37:02.469 the answer is 42, and I'm 99 .999 % sure about 00:37:02.469 --> 00:37:05.630 that. Why would you ever accept a 99 % answer? 00:37:06.230 --> 00:37:08.869 When is that good enough? A great real world 00:37:08.869 --> 00:37:11.789 example is testing for prime numbers for cryptography. 00:37:11.989 --> 00:37:15.130 We need to find huge prime numbers, numbers with 00:37:15.130 --> 00:37:18.550 hundreds of digits, proving with 100 % mathematical 00:37:18.550 --> 00:37:20.730 certainty that a number that big is prime is 00:37:20.730 --> 00:37:23.969 very, very slow. But there's a Monte Carlo algorithm 00:37:23.969 --> 00:37:27.309 called the Miller -Raben primality test. It runs 00:37:27.309 --> 00:37:29.090 a few random checks on the number. If the number 00:37:29.090 --> 00:37:31.449 passes all the checks, the algorithm says this 00:37:31.449 --> 00:37:34.010 number is almost certainly prime. And almost 00:37:34.010 --> 00:37:35.989 certainly is good enough for our online security. 00:37:36.489 --> 00:37:39.449 It is. The probability of it being wrong after, 00:37:39.510 --> 00:37:43.409 say, 100 rounds of testing is so astronomically 00:37:43.409 --> 00:37:45.929 low -like, less than your chance of being hit 00:37:45.929 --> 00:37:48.010 by a meteor, that for all practical purposes, 00:37:48.150 --> 00:37:50.130 it's considered true. It's an engineering trade 00:37:50.130 --> 00:37:52.690 -off. Engineering accepts tolerance. Pure math 00:37:52.690 --> 00:37:55.110 does not. We've covered the mechanics, the types, 00:37:55.190 --> 00:37:56.690 the theory. I want to move to the real -world 00:37:56.690 --> 00:37:59.489 implications, specifically the legal side. If 00:37:59.489 --> 00:38:01.429 these algorithms are such valuable tools like 00:38:01.429 --> 00:38:03.929 industrial machines, can I own one? Can I get 00:38:03.929 --> 00:38:06.170 a patent on an algorithm? This is a legal and 00:38:06.170 --> 00:38:08.650 philosophical minefield. The short answer, in 00:38:08.650 --> 00:38:10.769 the United States at least, is no, you cannot 00:38:10.769 --> 00:38:13.150 patent math. You cannot patent the Pythagorean 00:38:13.150 --> 00:38:16.050 theorem. You can't patent E. Masser. They are 00:38:16.050 --> 00:38:17.969 considered fundamental truths of the universe, 00:38:18.230 --> 00:38:21.210 abstract ideas, and they belong to everyone. 00:38:21.510 --> 00:38:23.489 Software companies have thousands of patents. 00:38:23.809 --> 00:38:27.190 Amazon has a pattern on one -click buying. That's 00:38:27.190 --> 00:38:29.429 an algorithm. They do. And this is where the 00:38:29.429 --> 00:38:31.829 legal nuance comes in. The distinction the courts 00:38:31.829 --> 00:38:34.369 have tried to draw is between patenting the abstract 00:38:34.369 --> 00:38:37.369 idea and patenting a specific practical application 00:38:37.369 --> 00:38:40.130 of that idea. You can't patent the formula, but 00:38:40.130 --> 00:38:42.389 you might be able to patent the machine or process 00:38:42.389 --> 00:38:45.269 that uses the formula to do something tangible 00:38:45.269 --> 00:38:47.570 in the real world. What's the key case there? 00:38:47.670 --> 00:38:50.329 The landmark case is Diamond v. Dyer from 1981. 00:38:50.690 --> 00:38:53.570 It was about a process for curing synthetic rubber. 00:38:53.710 --> 00:38:56.409 Rubber curing. Not exactly the glamorous side 00:38:56.409 --> 00:38:58.730 of Silicon Valley. No, but it was a critical 00:38:58.730 --> 00:39:01.730 industrial process. The company had a computer 00:39:01.730 --> 00:39:04.449 running a well -known mathematical formula, the 00:39:04.449 --> 00:39:07.329 Arrhenius equation, to calculate the perfect 00:39:07.329 --> 00:39:10.690 curing time. The algorithm constantly rated the 00:39:10.690 --> 00:39:13.369 temperature inside the rubber mold and re -ran 00:39:13.369 --> 00:39:15.769 the calculation to determine the precise moment 00:39:15.769 --> 00:39:19.309 to open the press. The U .S. Patent Office rejected 00:39:19.309 --> 00:39:21.530 their patent, saying, you're just patenting a 00:39:21.530 --> 00:39:23.670 mathematical equation. But the Supreme Court 00:39:23.670 --> 00:39:26.010 disagreed. They did. The Supreme Court overruled 00:39:26.010 --> 00:39:28.969 them. They said that because this algorithm was 00:39:28.969 --> 00:39:31.130 part of a larger process that was physically 00:39:31.130 --> 00:39:33.670 transforming rubber from an uncured state to 00:39:33.670 --> 00:39:36.090 a cured state, because it was interacting with 00:39:36.090 --> 00:39:38.699 the real world in a tangible way. the overall 00:39:38.699 --> 00:39:41.639 process was patentable. So if my algorithm just 00:39:41.639 --> 00:39:43.679 sorts numbers on a computer screen, it's an abstract 00:39:43.679 --> 00:39:46.360 idea and hard to patent. But if my algorithm 00:39:46.360 --> 00:39:48.820 controls a robot arm that sorts physical apples 00:39:48.820 --> 00:39:51.579 into bins, I can patent the whole process. That's 00:39:51.579 --> 00:39:53.159 a good way of looking at it. Generally, yes. 00:39:53.679 --> 00:39:56.400 But it is still a hugely debated area of law. 00:39:56.760 --> 00:39:59.860 There's a lot of controversy. over software patents 00:39:59.860 --> 00:40:02.840 stifling innovation if someone patents a fundamental 00:40:02.840 --> 00:40:06.079 way of compressing video suddenly nobody else 00:40:06.079 --> 00:40:07.780 can stream movies without paying them a license 00:40:07.780 --> 00:40:11.000 fee it's a constant tension between protecting 00:40:11.000 --> 00:40:13.559 inventors and allowing the free flow of ideas 00:40:13.559 --> 00:40:16.119 needed for progress and speaking of progress 00:40:16.119 --> 00:40:18.820 we have to look at the horizon because there's 00:40:18.820 --> 00:40:20.980 a new kind of computer coming which means there's 00:40:20.980 --> 00:40:24.039 a new kind of algorithm on its way We are entering 00:40:24.039 --> 00:40:27.480 the era of quantum algorithms. You're a quantum 00:40:27.480 --> 00:40:29.659 leap. It's a whole new paradigm. We hear the 00:40:29.659 --> 00:40:31.960 buzzwords all the time. Quivets, superposition, 00:40:32.219 --> 00:40:35.760 entanglement. Yeah. But from a purely algorithmic 00:40:35.760 --> 00:40:37.940 standpoint, what actually changes? In a word. 00:40:38.349 --> 00:40:40.449 Everything. All the classical algorithms we've 00:40:40.449 --> 00:40:42.929 discussed, from Euclid to Google, are built on 00:40:42.929 --> 00:40:44.710 the principles of a Turing machine. They operate 00:40:44.710 --> 00:40:46.829 on bits. A bit can be a zero or it can be a one. 00:40:46.869 --> 00:40:49.269 That's it. Quantum algorithms run on quantum 00:40:49.269 --> 00:40:52.469 computers, which use qubits. And a qubit, because 00:40:52.469 --> 00:40:55.130 of the principle of superposition, can be a zero, 00:40:55.309 --> 00:40:58.730 a one, or. It can be in a state that is partly 00:40:58.730 --> 00:41:01.730 zero and partly one at the same time. This allows 00:41:01.730 --> 00:41:04.550 for a kind of massive parallelism that classical 00:41:04.550 --> 00:41:06.989 computers can only dream of. So what does that 00:41:06.989 --> 00:41:09.469 mean for problems? solving for our big O notation. 00:41:09.889 --> 00:41:12.769 It means that for certain specific types of problems, 00:41:12.929 --> 00:41:15.869 the complexity class can collapse. The most famous 00:41:15.869 --> 00:41:17.909 example, the one that keeps cryptographers up 00:41:17.909 --> 00:41:20.409 at night, is Shor's algorithm. And what does 00:41:20.409 --> 00:41:23.159 that do? Remember, we said that factoring a huge 00:41:23.159 --> 00:41:26.059 number into its prime components is an exponentially 00:41:26.059 --> 00:41:28.980 hard problem for classical computers, that it 00:41:28.980 --> 00:41:31.179 would take millions of years. That's the foundation 00:41:31.179 --> 00:41:33.860 of most of our current encryption. Right. Shor's 00:41:33.860 --> 00:41:36.320 algorithm, if you could run it on a large, stable 00:41:36.320 --> 00:41:39.300 quantum computer, could factor those huge numbers 00:41:39.300 --> 00:41:43.179 in hours, maybe minutes. It breaks RSA encryption 00:41:43.179 --> 00:41:45.739 wide open. So it basically breaks the Internet 00:41:45.739 --> 00:41:48.369 as we know it. It breaks a huge chunk of the 00:41:48.369 --> 00:41:50.369 security infrastructure of the Internet. Yes, 00:41:50.389 --> 00:41:53.289 it turns a classically intractable exponential 00:41:53.289 --> 00:41:57.110 problem into a manageable polynomial one. That 00:41:57.110 --> 00:41:59.409 is why organizations like NIST, the National 00:41:59.409 --> 00:42:01.710 Institute of Standards and Technology, are in 00:42:01.710 --> 00:42:04.110 a controlled panic. Well, they call it proactive 00:42:04.110 --> 00:42:07.730 preparation. Just in 2024, they released the 00:42:07.730 --> 00:42:11.510 first official standards for post -quantum cryptography. 00:42:11.690 --> 00:42:13.989 So they're already building new encryption algorithms 00:42:13.989 --> 00:42:16.590 that are designed to be hard even for quantum 00:42:16.590 --> 00:42:19.050 computers to solve. It's the next phase of the 00:42:19.050 --> 00:42:21.650 arms race, the code makers versus the code breakers. 00:42:21.969 --> 00:42:24.550 It's a race that started with Al -Kindi and frequency 00:42:24.550 --> 00:42:27.070 analysis in the ninth century. And it's continuing 00:42:27.070 --> 00:42:29.429 today with quantum physicists and cryptographers. 00:42:29.670 --> 00:42:31.889 It really is just one continuous line, isn't 00:42:31.889 --> 00:42:33.889 it? Yeah. So let's try and wrap this all up. 00:42:33.969 --> 00:42:35.710 We've gone on an incredible journey. We went 00:42:35.710 --> 00:42:38.610 from Sumerian clay tablets to Al -Khorizmi's 00:42:38.610 --> 00:42:41.590 name getting mangled to Ada Lovelace dreaming 00:42:41.590 --> 00:42:44.409 of computer music to Alan Turing's theoretical 00:42:44.409 --> 00:42:47.340 limits and now to quantum encryption. It's a 00:42:47.340 --> 00:42:49.639 history of human problem solving, really. It 00:42:49.639 --> 00:42:52.000 is. And we learned that algorithm isn't magic. 00:42:52.079 --> 00:42:54.940 It's a rigorous recipe. We learned that efficiency 00:42:54.940 --> 00:42:57.619 isn't about seconds. It's about scaling, about 00:42:57.619 --> 00:43:00.760 avoiding those O -N or O -tine traps. We've met 00:43:00.760 --> 00:43:03.780 the greedy algorithms, the divide and conquer 00:43:03.780 --> 00:43:06.079 ones, the cautious dynamic programming ones. 00:43:06.300 --> 00:43:09.139 It's a vast and fascinating ecosystem of thought. 00:43:09.400 --> 00:43:11.400 But I want to leave our listeners with that provocative 00:43:11.400 --> 00:43:12.860 thought you mentioned when we were prepping for 00:43:12.860 --> 00:43:14.980 this. We spent this whole time talking about 00:43:14.980 --> 00:43:19.619 deterministic algorithms. machines, logic, rigid 00:43:19.619 --> 00:43:22.719 rules. But nature has its own algorithms, doesn't 00:43:22.719 --> 00:43:25.139 it? Yes. And this is where the strict definition 00:43:25.139 --> 00:43:27.860 starts to blur and get really interesting. If 00:43:27.860 --> 00:43:30.400 you look at an ant colony foraging for food, 00:43:30.519 --> 00:43:32.860 there's no central leader. No single ant knows 00:43:32.860 --> 00:43:35.679 the map. But the colony as a whole runs a highly 00:43:35.679 --> 00:43:38.300 efficient search algorithm. It uses pheromone 00:43:38.300 --> 00:43:41.360 trails as a form of distributed memory to optimize 00:43:41.360 --> 00:43:43.659 the path to a food source. It is a distributed 00:43:43.659 --> 00:43:45.980 emergent biological algorithm. And what about 00:43:45.980 --> 00:43:48.539 our own brains? Our brain is a massive neural 00:43:48.539 --> 00:43:51.039 network. It doesn't run if -then code like a 00:43:51.039 --> 00:43:54.739 laptop. It learns. It recognizes patterns. It 00:43:54.739 --> 00:43:56.860 adjusts the weights and connections between its 00:43:56.860 --> 00:43:59.900 neurons based on experience. It is a constantly 00:43:59.900 --> 00:44:02.940 running adaptive learning algorithm. So in a 00:44:02.940 --> 00:44:05.340 way, we are building these silicon -based algorithms 00:44:05.340 --> 00:44:08.039 that are, in many cases, just trying to mimic 00:44:08.039 --> 00:44:10.260 the biological algorithms that created them in 00:44:10.260 --> 00:44:12.739 the first place. And we ourselves are the product 00:44:12.739 --> 00:44:15.920 of four billion years of the grandest algorithm 00:44:15.920 --> 00:44:19.510 of all. evolution by natural selection, a brute 00:44:19.510 --> 00:44:21.889 force iterative process that optimizes for one 00:44:21.889 --> 00:44:25.369 thing, survival and reproduction. So that leaves 00:44:25.369 --> 00:44:27.210 us with the final question for everyone to chew 00:44:27.210 --> 00:44:29.809 on. If a recipe is an algorithm and a bureaucracy 00:44:29.809 --> 00:44:32.650 is an algorithm and an ant colony is an algorithm, 00:44:32.829 --> 00:44:35.030 are you just running a very complex biological 00:44:35.030 --> 00:44:37.570 algorithm right now? Are we the programmers or 00:44:37.570 --> 00:44:39.670 are we just the code? That is a question that 00:44:39.670 --> 00:44:41.650 might not have a halting state. You could loop 00:44:41.650 --> 00:44:43.769 on that one for a good long while. I think I 00:44:43.769 --> 00:44:45.949 will. This has been a fantastic deep dive. Thank 00:44:45.949 --> 00:44:47.889 you so much. My pleasure. It was a lot of fun. 00:44:47.989 --> 00:44:48.670 See you next time.