▶︎ 0:01 Today, I want to continue to talk about computation. Again, computation is a concept that transcends any particular technology. Computation is really part of the mysteries of the universe. So in the first episode, our main focus was actually establishing limitations of computation, this idea that there are things that computers will fundamentally never be able to do, like for example, solve the halting problem. Today, I want to have a different emphasis. I really want to talk about positive applications of computation.
▶︎ 0:33 They can't do everything, but we all know from day-to-day life, they help us do a lot of useful stuff, and that's what I want to focus on today. I want to focus on the key concept of an algorithm. So you can think of an algorithm as really just a recipe for how to systematically achieve some goal or to solve some problem. If you watched episode one, when we talked about Turing machines having sets of rules, that set of rules was basically encoding an algorithm, a recipe for how to go about systematically solving some problem.
▶︎ 1:07 From recipes you're familiar with, for example, there may be a sequence of steps you're supposed to do in a row. There may be loops, so there may be a sequence of steps you should do over and over again. Maybe you're making a lasagna or making your baklava, and you have to go layer by layer, repeating the same steps. There's even conditionals, or if-then-else. Like, if the hamburger patties are frozen, you follow one set of instructions. If they're not, you follow some other set of instructions. And if you've ever done any kind of coding at all, you'll recognize all these things as stuff that maps quite directly into code that you would write, loops, if-then-else, and so on. So that's what I want you to have in mind when I talk about algorithms.
▶︎ 1:46 Now, the recipes that you follow in a kitchen, honestly, viewed as algorithms, not really super interesting, but it turns out that algorithms, including for very natural problems... We'll look at two today, one about arithmetic, one about networks. Algorithms, even for very natural problems, can sometimes be mind-bogglingly clever, and can exploit really unexpected algorithmic shortcuts, and that's proved the case over and over again over the history of computer science. So again, through two examples, I want to give you a taste of the creativity of algorithms and the creativity of algorithm designers today.
▶︎ 2:21 And while my main goal is to just appreciate a lot of the genius that we've seen in algorithm design over the years, lurking in the backstory is, if you think back to establishing limitations on what computers can do, what's possible with computation, again, the fact that algorithms can be so clever and even downright inscrutable and weird, and yet simultaneously useful, that is exactly why, and this'll be really obvious when we talk about the P versus NP problem later, that is exactly why it's so difficult to show limitations on computation. That is yet another reason why we should have so much admiration for Turing's work. He's showing limitations on something which is, in fact, very powerful. So with that, let's move to the two examples. First, I want to talk about an
▶︎ 3:12 example in arithmetic, and then the second example, like I said, will concern networks. We're gonna start with super basic problem. Literally, I'll give you two numbers, and I want you to multiply them. All of us learned how to do that at some point in grade school. Kinda seemed like that was the end of the story. Everything seemed super straightforward.
▶︎ 3:35 What I wanna tell you about today is a different method, Karatsuba's method for multiplying integers, which believe it or not, is fundamentally more efficient, fundamentally faster method, a completely different method of multiplying two numbers than the one that you learned back in grade school. So let me set the stage for you for Karatsuba's multiplication algorithm.
▶︎ 3:58 We wanna go back to the year 1960, and I guess just zooming out a little bit further, the mid-20th century, which is where we're kinda gonna be living mostly in today's episode, the mid-20th century was really a golden era for algorithm design. Computers all of a sudden were starting to become available, they were starting to be used more and more in high-value applications, and historically, not that many people had thought that hard about algorithms. So there were lots of gems out there waiting to be found, especially in the 1950s, 1960s. That's exactly where we are right here.
▶︎ 4:31 I want you to think about 1960. We're gonna be at Moscow State University, and we're gonna be interested in a seminar, research seminar run by a very famous mathematician, Andrei Kolmogorov. By this point, 1960, mechanical computers were indeed being used for lots of calculations, and Kolmogorov was one of the first mathematicians to really become obsessed with understanding, if we're gonna compute these things by computer, what is the best way to compute these things by computer? So for example, can we be more clever and compute some, complete some calculation in five minutes instead of 10 minutes? Or conversely, is some way of doing a computation, like for example, the way we learned how to multiply back in fourth grade, could that be the optimal, the best possible way of carrying out the computation? That was Kolmogorov's focus in the late '50s and early '60s.
▶︎ 5:27 At this time, he's running a weekly research seminar, and he asserted or he conjectured, he said, "You know, think about integer multiplication. We all learned how to do it. Seems like that should be the best way. We just need to prove mathematically that that's the best way to do it. There's nothing more clever than you can do than the sort of partial products that we all learned how to do when we were kids."
▶︎ 5:51 And there was one student in that seminar, Anatoly Karatsuba, who had exactly the right attitude you're supposed to have if you design algorithms for a living. If you meet professional algorithm designers, they are people who are very hard to please, certainly in terms of the research, often, honestly, more broadly in life. But they're sort of never content. Whenever you see any kind of solution to a problem, they're always like, "Eh, eh, could you do better? I'm not satisfied. I wanna do better."
▶︎ 6:20 And so Karatsuba brought that attitude to Kolmogorov's seminar. "Eh, yeah, if I wanted, I could just follow the traditional method of multiplying two integers, but can we do better? Is there a better way of doing it?" And sort of against prevailing intuition, what else would you do other than what we learned in third or fourth grade? So Karatsuba actually did find a fundamentally better method, which I will tell you about in a minute.
▶︎ 6:49 Karatsuba, in 1995, wrote an article which included a retrospective of those years in the early 1960s with Kolmogorov, and here's what he said. He was 23 years old at the time, and he has a weekly seminar, so Kolmogorov makes the conjecture one week, and I don't know what day of the week it was, let's say it was Monday. The following week, on Monday, Karatsuba comes with a solution. In a week's time, he disproved Kolmogorov's conjecture that there should be no better way to multiply numbers than what we learned in grade school.
▶︎ 7:18 Karatsuba reports Kolmogorov was very agitated because this contradicted his very plausible conjecture. At the next meeting of the seminar, the following Monday let's call it, Kolmogorov himself told the participants about my, meaning Karatsuba's, method. And at this point, the seminar was terminated. The seminar lost its purpose when Karatsuba showed that there was actually this even better way of doing multiplication than what Kolmogorov had conjectured should be optimal.
▶︎ 7:47 At this point, I hope you're wondering, how exactly does Karatsuba's method for multiplying integers work? Again, if you're like me, or like most people, your response is like, "What else could you do other than what we learned back when we were kids?" So let me tell you a little bit about that.
▶︎ 8:06 I'm going to do some arithmetic on the whiteboard. If I lose you in the details, doesn't matter. The point of this part of the episode is to get a visceral feel for the type of unexpected shortcuts that can be out there in nature, and which can be taken advantage of by clever algorithms, and by clever algorithm designers. That's what I want you to take away from the work we're going to do here on the board, just that these surprising shortcuts really do sometimes exist.
▶︎ 8:35 As a reference point, let's just remember, it's probably been a while for most of us, and most of us don't do that much multiplying by hand anymore, so what did we learn back when we were kids? How is it that you multiply two numbers together? Maybe you want to multiply five, six, seven, eight times one, two, three, four. So you write down what are known as partial products, so you multiply four times the top, then you do a shift, three times the top, another shift, two times the top, and then another shift, and then one times the top.
▶︎ 9:09 I'll spare you all of the details, but basically you wind up with the following, the first partial product's 22,712. Then you do a shift, the next partial product, 17,034, you do another shift, and then you get 11,356, and then the final shift, and now it's just five, six, seven, eight. And if you add up all the results, your four partial products, you get 7,006,652. That's what we mean by multiplying two numbers, and that was the algorithm that all of us learned in grade school.
▶︎ 9:54 Probably didn't even really think of it as an algorithm, it was just a bunch of steps that we followed to get to the result, but actually, if you think about it, that is an algorithm. And in general, if you look at it, you basically fill in this table, so we're multiplying two numbers together, each of which has four digits, and basically we fill up a table that's four rows and, ballpark, four columns, add up the results. So that's the amount of work involved.
▶︎ 10:18 As the number of digits grows, you're going to be filling up a table, so say you had 100 digits, those would be very big numbers obviously, but the same procedure works. If you're multiplying two numbers that have 100 digits each, you're going to have 100 partial products, so 100 rows, each with 100 or 101 numbers in it, all of which you're going to be adding up. So that is how we learned as kids to multiply two numbers. Now, what else could you do? What else could you do?
▶︎ 10:49 There's two ideas in Karatsuba's method. And the first idea at first is going to seem bizarre. You'd be like, "Why would you ever do that?" And it's not going to be obvious, the second idea will unlock the power of the first idea. So bear with me while I tell you about the first idea.
▶︎ 11:08 The first idea will be familiar to those of you that have studied programming. If you haven't, you may not have heard this, but the first idea is about recursion, which is, you solve a problem by first boiling it down to one or more smaller instances of the problem. Recursion. So there are examples in real life of recursion. Imagine you were trying to figure out how to run a tennis tournament. You had a bunch of tennis players and you wanted to arrange the matches to elect a champion. And if you only have one player, it's not a hard problem, they're the champion. If you only have two players, it's not a hard problem, they play a match and the winner's the champion.
▶︎ 11:51 But what if you're running a Grand Slam tournament? What if you have 128 players in your tennis tournament, how should you arrange things to eventually wind up with a champion? Well, one thing you could do is you could solve the problem recursively, which in this context means the following, I want to say, "Well, we have 128 players, let me try to reduce my problem to running a tennis tournament on a smaller number of players." How would you do that? You have a bunch of first round matches. You take your 128 players, you pair them up, that gives you 64 matches. You play those 64 matches. You're left with the 64 winners, and now you recursively run a tennis tournament on the 64 first round winners.
▶︎ 12:30 So that's what I mean by recursion. You have a big problem you want to solve, you're like, "Ugh, I don't know how I'm going to solve all of this at once, but let me just at least try to reduce it down to one or more smaller versions of the problem to make progress." So that is recursion and that is a very important tool in designing algorithms and programming more generally. So that's recursion.
▶︎ 12:52 But now maybe you're like, I see in the tennis tournament example how you'd reduce things down to a smaller set by playing matches. But if I ask you to multiply these two numbers, what does it mean to recursively do that? So I guess it would mean trying to multiply smaller numbers against each other, but what's smaller numbers? These are the numbers we're given. But in fact, you can have a recursive approach to multiplying two numbers.
▶︎ 13:21 And the way you would do it is you would break your numbers into their first and their second halves. So you would say, well, we were given two numbers that have four digits each. Let's think of each of those four-digit numbers as actually two different two-digit numbers. And let's see if we can reduce the multiplication of these two four-digit numbers to multiplications that involve only two-digit numbers. That is going to be our recursive approach to integer multiplication.
▶︎ 13:52 Again, this idea by itself is not going to be the full story. We're going to need a second idea, which I'll tell you about in a minute. In other words, let me change colors. Let's go with that idea. Let's think about how can we think of these four-digit numbers as really two pairs of two-digit numbers? So here's what we're going to do. We have 5,678. Let's think of that number as 5,600. So this is the first two digits, plus 78. I hope you'll agree that this number is the same thing as this number.
▶︎ 14:31 Similarly with the second number. This we want to multiply times 1,200. So that represents the first two digits of the second number, plus 34. At the moment, I just want you to agree that the answer of this expression in black is going to be the same as the answer of the product of these two numbers. It's literally just the same two numbers written in this expanded form.
▶︎ 15:01 Now to see where the recursion comes in, where we get smaller versions of the problem, we're going to go ahead and expand. I'm going to ask you to just remember how you expanded parenthetical expressions in high school. So what is this going to be? This is going to be 56 times 12. So that's this first term, times 10,000. I'm just going to group the zeros together for convenience. So that's this term times this term, then you have this term times this term. So 56 times 34 times 100.
▶︎ 15:39 Then you have the other cross term, 78 times 1,200. So that's 78 times 12, times 100. And then finally add the product of the two second terms, plus 78 times 34. And again, all I'm asking you to agree with right now is that the results of this computation in black is going to be the same as this product of these two blue numbers, just because they're literally exactly the same numbers, just expressed in a different form.
▶︎ 16:17 And so at this point, I hope you can see the idea of where recursion comes into play. To evaluate this expression in black, there's really only four non-trivial multiplications we need to worry about. When I say non-trivial, multiplying by 10,000 is very easy, you just stick four zeros at the end. Multiplying by 100 is very easy, you just stick two zeros at the end. The real multiplications, the ones that are going to require work, are the four different products circled in green.
▶︎ 16:55 So what did I say recursion was in general? You boil down your problem to one or more instances of smaller versions of the problem. That is what we have done. We had the problem of multiplying two numbers with four digits, we have boiled that problem down to multiplying four pairs of two-digit numbers. The numbers are smaller, there's more problems, but the numbers are smaller. Four instances of a smaller version of the problem. That is the hallmark of recursion.
▶︎ 17:22 So I've got to be honest with you, so far our progress has been very modest. Really all we've done so far is reorganize the exact same calculations we would do with the original grade school algorithm, just in a different order. So this recursive algorithm, as I've talked about it, is really no faster than what we would've done anyways with a grade school algorithm. So this brings us to idea number two.
▶︎ 17:50 Idea number two is identifying redundant work and reusing computation rather than redoing computation. Just to give you a sense where we're going, using this idea of reuse rather than redoing, we will actually be able to save one of these four multiplications. So we are going to be able to boil down the multiplication of two four-digit numbers to the multiplication of three, not four, three pairs of two-digit numbers. It is not obvious how to do that. That was Karatsuba's big second idea, so that's what I'm going to show you next. Where is the redundant computation and how do we reuse it?
▶︎ 18:34 The next step I'm going to do is I'm just going to group terms in where we left off. I'm going to take this black expression. You'll see there are two of the four. We have four terms. Two of the four terms are multiplied by 100, so let's just group those together. We just inherit the same first term involving the 10,000. But now, again, we group the second and third terms. So we have a 56 times 34, plus a 78 times a 12. Those both get multiplied by 100, and then we have the same fourth term as before. And again, all I'm asking you is to agree that whatever this number is, this is the same number. All I've done is taken the middle two terms and grouped them together.
▶︎ 19:23 And so now, here is the key, here is the really key insight. We want to evaluate this. The answer of this is the answer that we're looking for, so we want to know, what does this evaluate to? And the key observation is that we do not care, we do not care about the product of 56 and 34 per se. We do not care, for the purposes of evaluating this expression, the product of 78 and 12 per se. If you handed me on a silver platter their sum. So if you told me the answer to 56 times 34, plus 78 times 12, that's good enough for me. I can take it from there. I'm going to add two zeros to that number. I'm going to add it to this, I'm going to add it to this.
▶︎ 20:12 Up here, we were just assuming, really without justification, we were assuming that the only way to evaluate this expression was to separately compute 56 times 34, and separately compute 78 times 12. We don't necessarily need to do that. If we can somehow compute the sum of those two products, that's good enough. We don't need the products individually. That is actually the biggest idea in Karatsuba's multiplication.
▶︎ 20:40 But now of course you ask, "Well, how are we going to do that?" How would you know the answer to this without separately computing the two products? What else could you do? And this is where the clever spotting of opportunities for reuse come in. So what Karatsuba says is, he's like, "Look, we gotta compute 56 times 12 no matter what. We gotta compute 78 times 34 no matter what." Can we somehow piggyback on those two multiplications we know we have to do to somehow compute the last number that we need with only one more multiplication? And in fact, we can. And that's what I'm going to show you next.
▶︎ 21:25 So here's the big trick. How would you ever come up with this trick? Well, I think you'd have to have in mind you've already computed this, you've already computed this. You want to somehow compute this whole thing without computing these individually, and then you do some trial and error. You do some experimenting. After you do some experimenting, you get a eureka moment, which is the following.
▶︎ 21:48 Suppose we did the following calculation. Suppose we took 56 plus 78. Those are the first two terms. So the sum of the digits of the first number. And imagine we multiply this times 12 plus 34. So this is going to be, what? 134. This is gonna be 46. So imagine we multiply these two numbers together. Again, let's expand terms. What do you get?
▶︎ 22:19 You get a 56 times 12. That's interesting. That's something we already knew, we already knew we had to compute. We get a 78 times 34, which is also something we knew we had to compute. And then you get the cross terms, 78 times 12, plus 56 times 34. Which is exactly what we're looking for.
▶︎ 23:00 So what have we done? With one multiplication, only one multiplication, 134 times 46. With one multiplication only, we have computed a number which includes the one we care about, plus some distractions, 56 times 12 plus 78 times 34. But distractions the value of which we already know. We already have to compute 56 times 12. We already have to compute the product of 78 and 34. So if we subtract those out, we will be left with the amount in blue. Which is exactly what we wanted in the first place.
▶︎ 23:37 So you may have gotten a little lost along the way, so let me recap. I'm not gonna say anything new. I am just gonna now take our calculations and organize them in a direct fashion. So here is the alternative way to
▶︎ 24:04 Compute the product of 5,678 and 1,234. Step one: you compute one of the products we knew, we know we needed, 56 times 12. This comes from that first of the four terms when we expand the two expressions, and then we also know we needed the product of the second two pairs. Compute 78 times 34. And now, this was the tricky step, we compute the product of 134 times 46.
▶︎ 24:48 Again, remember where these numbers come from. This is 78 plus 56, and this is 34 plus 12, so this is the number we care about, 78 times 12 plus 56 times 34, with these two additional terms in there, so we subtract them out. We compute the result of the third multiplication, and we subtract out the results of the first two multiplications. I may as well say what these are. So this is going to be 672, 2,652, this is going to be 6164. After you subtract out the first two, you're going to be left with 2,840, and now we just add up the results.
▶︎ 25:50 Remember, this was the term where we needed to add on four zeros at the end, because this corresponds to the 5,600 and the 1,200. This is the term where we don't need to add any zeros at all, because that corresponds to the 78 and the 34, and this was the cross terms, where we need to add two zeros. So the final step is just compute 672 with four zeros, plus 2652 with no zeros, plus 2840 with two zeros, and if you carry that out, what do you get? Lo and behold, you get 7,006,652. So that is Karatsuba's method for integer multiplication.
▶︎ 26:41 Obviously, we've only verified that it works with one specific example, but I hope your intuition is very strong that there's literally nothing special about these numbers five, six, seven, eight, and one, two, three, four. You can use this exact same recipe, this exact same algorithm, to multiply any pair of numbers that you want. And this really is fundamentally faster, fundamentally more efficient than the algorithm we learned in grade school. That's not totally obvious, and I'm not going to prove it in detail, that's outside our scope, but the intuition is that by virtue of reuse, by virtue of observing that, in the expansion, there's really only three numbers that we care about, and in fact, we can get those three numbers with only three rather than four, only three multiplications, that is exactly the source of the extra efficiency of the algorithm. That is exactly why this improves over what we learned in grade school.
▶︎ 27:38 And this is not merely an academic algorithm. This really is faster. So for example, for those of you that know the programming language Python, the standard Python libraries, if you ask it to multiply large numbers together, if those numbers have 70 digits or more, the standard Python multiplication method will in fact use Karatsuba's method rather than the grade school method, that we all learned many, many years ago.
▶︎ 28:03 So if I had to summarize the genius in Karatsuba's method in just one sentence, I would say that it turns out there's actually redundant work in the grade school algorithm that we all learned as kids, and Karatsuba's genius was structuring the computation so that the redundant information became obvious, and was able to be instead reused across the three multiplications, rather than four.
▶︎ 28:29 Now, again, it's not a big deal if I lost you in the details here. The main thing to take away, I guess, a couple main takeaways. One takeaway is just to appreciate that remarkable algorithmic shortcuts exist in nature. Maybe not for every problem, we'll talk more about that later, but certainly for some problems, it turns out algorithms can be much, much, much more effective than you might have guessed. And again, always remember the flip side of that, which is if you're thinking about limits of computation, things that computers cannot do, one thing that's so terrifying about trying to sit down and prove limitations on algorithms is knowing examples like Karatsuba's method, where algorithms just seem much more unreasonably effective than you might have thought. Again, which should make us all the more appreciative of Turing's work showing limits of computation, for example, for the halting problem.
▶︎ 29:22 So something related to Karatsuba's method, which I'll just leave as extra credit, I don't want to do it in detail here, but if you find this intriguing, if you want your minds to be even more blown, you should really look into Strassen's algorithm for matrix multiplication. Some of you will remember what matrix multiplication is, some of you won't, that's fine. Super, super important practical problem. So modern machine learning algorithms, the bulk of the cycles that they are doing involves matrix multiplications. So really, literally today in 2026, a significant fraction of the computation being done right now is multiplying matrices.
▶︎ 29:59 So very fundamental problem, and there's a straightforward way of multiplying matrices, which is what you learn when you first learn matrices in college or high school, or whenever you see it, and it involves eight multiplications, and if you think I pulled Karatsuba's trick out of a hat to reduce the number of multiplications from four to three, you have got to look into Strassen's trick for reducing the number of multiplications from eight to seven. And when I talk about the intimidation of trying to prove limitations on algorithms because of the clever things that algorithms can do, I know of no better example of where that intimidation comes from than Strassen's algorithm for matrix multiplication. So next, I want to talk about our
▶︎ 30:44 Second example of an algorithm in today's episode, this time for a problem in networks. Very familiar problem. You gotta get from point A to point B. You ask your favorite map application to give you driving directions, hopefully the fastest route available from A to B. These days, we all take that technology for granted, but underpinning it are clever algorithms taking advantage of algorithmic shortcuts. So I wanna give you a feel for the nature of those shortcuts, in this second part of this episode.
▶︎ 31:17 We wanna get from point A to point B as quickly as possible and, to organize how we think about that, to organize the options, the routes, let's think about a network. So lemme draw an example network here on the whiteboard. I'm gonna draw a network, which in fact is near and dear to my heart. Ask me some other time if you wanna know why. But in this network, each of these arrows, which in this context is often called an edge, that represents, for example, a road, from one point to another. And the circles, those are sometimes called vertices. Those represent intersections. Those are where different roads meet.
▶︎ 32:02 The origin is A, you want to get to B. Let's have a very simple model of travel times in this network. Let's just say that I'm gonna annotate each of these edges with a number representing the travel time along that road in minutes to get from the start of the road to the end of the road. So let's say this one takes three minutes, this one takes four minutes, this one takes one minute, this one takes five minutes, and this one takes two minutes. And these are one-way streets, so you can only drive on the street in the direction of the arrow in this example.
▶︎ 32:41 You want to get from A to B, you wanna get there as quickly as possible. So how would you do that? Well, this is not a hard problem to solve just by inspection. If you look at it, there's only three ways to get from A to B that respects the one-wayness of all the streets. You can go over the top, you can go the northern route. So that would take three minutes plus four minutes. So that's seven minutes to go the northern route.
▶︎ 33:08 You could go the southern route. So that would be five minutes plus two minutes. So that would be again, seven minutes. So northern and southern routes are tied at seven minutes. And then there's the zigzag path, which has more hops. So there's more, the list of the driving directions is one step longer, but in terms of the travel time, actually you'll get there in three plus one plus two or six minutes. So the zigzag path is the quickest route from A to B, taking six minutes.
▶︎ 33:43 So what we just did, the way we determined the quickest or shortest path from A to B in this example is something known as exhaustive search,
▶︎ 33:54 Which is if you have a whole bunch of options like routes from A to B and you want to find the best option, like the one with the smallest travel time, one way you can solve that problem is by just going option by option and remembering the best one. That's what we just did. There were only three paths from A to B. We checked them all. The zigzag one was the best. So we were confident in proclaiming that the shortest route from A to B.
▶︎ 34:22 Exhaustive search you can think of as an algorithm. It's a pretty straightforward algorithm. Examine every option, remember the best one. And if there aren't that many options, like in this network, there were three options. That's actually simple enough for just humans to do by hand or by inspection. And so you could do this manually for, I don't know, dozens of options, maybe hundreds of options. But of course, then if you think about carrying out exhaustive search by computers, modern day computers looking through billions of options is generally not a big deal.
▶︎ 34:54 So you might think then you're like, well, exhaustive search, straightforward algorithm, computers can do billions of operations. Probably we're just done. I mean, probably just whatever problem that comes up in practice, like for example, driving to your relative's place in a different state, whatever. Just use the computer, look at all the options, remember the best one, end of story. But is that true? Can we be sure that actually in the problems that we solve in day-to-day life, like again, just how to drive to our relative's house, are we sure that there's only billions of options? Are we sure that there aren't maybe much, much, much more than that?
▶︎ 35:41 So to see what I mean, let me show you another example of a network. And it's a simple network. It's not going to be hard to figure out the best way to go from point A to point B, but it is going to suggest the limitations of the specific approach of exhaustive search. So we again want to go from A to B. And let's assume that in choosing a route from A to B, you just make four. Is this four? Yes. Four choices where you either take the northern route or the southern route, and each time you wind up back at the same place. So to get to the next stop, you can go north, you can go south. And there's just four consecutive decisions where you choose whether to go the northern route or the southern route. And for example, maybe these are the travel times.
▶︎ 36:54 Now, you look at this network and just like here, you're like, "I don't need a computer to figure out the shortest path from A to B." Here, you're saying, "I still don't need a computer to figure out the shortest path from A to B." You're like, "Obviously, I go north and then south and then north and then south again, for a total travel time of, what is it? I guess 16 minutes. Obviously, this is the best thing. Any deviation from the red route would just substitute a worse road for one of the ones you're already taking." Obvious.
▶︎ 37:32 However, let me point out, when you reasoned through this problem, you took advantage of an algorithmic shortcut. You did not reason about it through exhaustive search. In the network on the left, there were only three paths, three possible options. How many options are there to go from A to B? Well, two options for the first hop, multiplied by two options for the second hop, times two again, times two again. So number of paths from A to B, two times two times two times two, also known as two raised to the fourth power, also known as 16. That is how many different options you have. Because you have a independent binary choice, four different times.
▶︎ 38:34 Now, you took a shortcut. You were like, "I don't even need to think about any path that uses the two because I would just substitute the one and it would be better." So you just pruned in your mind anything that used the two, similarly you pruned in your mind anything that uses the four or the six or the eight, leaving you with a one, three, five, seven red path. But in your mind, you did an algorithm shortcut. You did not do exhaustive search through the 16 options. That's the first thing that I want you to notice.
▶︎ 39:04 Your response might be like, "Okay, but so what? It's a computer, so it goes through the 16 options. That's trivial for any modern computer to do. What's the big deal?" So it's a little bit wasteful. It's still going to complete in the blink of an eye. Well, imagine we had a longer whiteboard, we had one of those long rolls of tape we were talking about with Turing machines in episode number one, and I replicated these binary decisions a few more times. So in this network, the number of options was two to the four, or 16.
▶︎ 39:41 Imagine you had 10 of these, and again, think about driving to your relatives in a different state. There actually are potentially a large number of decision points on route from, I don't know, New York City to Cape Cod or something like that. Imagine there are not just four of these, but there were 10 binary decisions you had to make in a row. Now you wouldn't just have two, four twos multiplied against each other. You wouldn't have two to the four, you'd have two to the 16. Which is 1,024.
▶︎ 40:13 Tell us the, you know you're talking to a computer scientist when they just have all the powers of two automatically memorized. Definitely means it's a computer scientist. Among friends, 1,024, let's call this 1,000. That would be a pain as a human to go through. Obviously we could do it, a computer could definitely do it. I'm sorry, this is 10, two to the 10. Looks like a 16, not a 60, and that's also a zero.
▶︎ 40:38 What if it was 20? And again, it would not be that hard. I can literally, if I decreased my font size, I could write down this network on this whiteboard. It is not a big network. It's a relatively small network. Two to the 20, well, that's like 1,000 squared or a million. If you had 30 decisions to make, we're talking about a billion. 40 decisions to make, talking about a trillion. And a trillion starts getting significant, even for computers to do. I'm not saying it's impossible, but that you start feeling the pain a little bit at a trillion, for sure.
▶︎ 41:19 Imagine you're driving from the West Coast to the East Coast. Imagine you have, I don't know, let's say at least 265 different decisions to make. Going from, I don't know, Burlington to La Jolla. Two to the 265. Two to the 265. Exponential growth is a wild, wild thing. So many of us are first taught this lesson through the power of compounding, and this is another version of it. Exponential growth is really, really, really, really fast. Really fast, really fast. So much so that it defies human intuition.
▶︎ 42:02 265, and again, you can imagine writing down a network like this with 265 choices. It would not be hard. We could write it down, we could have it on this table, no problem. The number of different routes in that network, the number of options you would have to check if you were carrying out exhaustive search is, I'm not kidding, basically the number of estimated atoms in the known universe. Two to the 265 is the estimate for the number of atoms in the known universe.
▶︎ 42:35 So while exhaustive search would still be an algorithm in the sense of Turing, it would still be a recipe that if carried out to completion would indeed identify the shortest path. It is one that would defy our understanding of physical limitations. It is one that would not complete in our or anybody else's lifetime.
▶︎ 42:59 What's the takeaway? The takeaway is that exhaustive search looks pretty good if you're solving very small problems, like this or like this. If you're talking about problems of even medium size, again, problems that we regularly punch in to our favorite map application, the number of options that exhaustive search would have to consider is completely infeasible. Again, not just for today's technology but for technology a thousand years from now. The shortest path problem, while not undecidable in the sense of Turing, if you were stuck with only exhaustive search, if you could not unlock any algorithmic shortcuts, it would be, for all practical purposes, unsolvable.
▶︎ 43:45 Given that exhaustive search would be out of the question, totally infeasible, once the network you're talking about is even medium size, the obvious question you should have now is, well, how does my phone give me driving directions even for places on the other side of the country? Just thinking logically through it, you must be, I guess it's not doing exhaustive search. I guess it's doing something hopefully more clever than that. Indeed, on this network on the right, you already see that at least in this specific example, there's an algorithmic shortcut. Basically, you can just treat each of the four decisions independently. Take the shorter route in the first step, take the shorter road in the second step, in the third step, in the fourth step, boom, you're done.
▶︎ 44:29 You didn't have to look at all 16 of the options. But that's just one example. This is a very, very special network. So the question is, in general, suppose you have just messy road networks out there in the world that look nothing like this network on the right, could there in some general sense be an algorithmic shortcut that an algorithm could take advantage of to compute driving directions? Happily, the answer is yes and there are shortest path algorithms, like those driving your map application, that take advantage of those ideas.
▶︎ 45:02 One famous one, and to really be, the driving directions that you get from your phone use ideas on top of this, but the starting point would be something known as Dijkstra's algorithm. It's a famous algorithm for computing shortest paths, from the mid-1950s. Several other people came up with similar algorithms at roughly the same time, but usually it's called Dijkstra's algorithm after Edsger Dijkstra. I don't want to go through it in too much detail, but let me just give you a sense of it.
▶︎ 45:33 The idea, again, is clever reuse. You can already see this in this example. You could, if you wanted, enumerate over all 16 of the paths and assess each independently, but you'd be having a lot of redundant work. Different paths in general will share some of their edges and, in principle, there's no reason you should have to reassess those edges over and over and over again. That was exactly our clever shortcut in this example.
▶︎ 46:03 Let's just make a decision between these two edges once and for all, and never consider it again. We make the decision once and that's it. Make the decision once, that's it, and so on. We're reusing work. We're avoiding redundant work.
▶︎ 46:15 So how would you do that in general? At a high level, what you can think of Dijkstra's algorithm as doing, it's almost like you blow up a balloon around the origin. So you explore in all directions at once. You go out one minute's worth in all directions and see where you get. In one minute, you would get what? You would get a third of the way down this road and a fifth of the way down this road.
▶︎ 46:40 So you blow up your balloon a little bit in time space and you see how far you get in one minute. Then you do it again with two minutes. So now you'd be two thirds of the way down this road and 40% of the way down this road. That'd be the next step of Dijkstra's algorithm. Now you say, how far could I get in three minutes of driving? And so now you would get to the end of this road and 60% of the way down this one.
▶︎ 47:07 Then you'd say, well, what about with four minutes? Well, now actually with four minutes, I can reach this point. I can't reach this point on four minutes going this way, but I've discovered a way to get from the origin down to this intersection in four minutes by taking this edge, followed by this edge. So with four minutes, you're like, cool. I can get anywhere here or I could also go three minutes here and then a third of the way down this link here. So with four minutes, that's how far I can get.
▶︎ 47:36 With five minutes, I would then go halfway down this road. With two minutes, I would be 50% down this road as well. So that would be the five-minute bubble. And then with six minutes, you would say, oh, I can get all the way to B in six minutes and the way I discovered to do it was by taking the zigzag path.
▶︎ 47:55 So that's the way to think about Dijkstra's algorithm. You explore simultaneously without ever doing redundant work. You never reconsider things you've already considered. All you do is radiate outward in all directions. When you radiate far enough, you're going to pick up your destination and the shortest path from the origin to the destination will be revealed to you at that point.
▶︎ 48:17 Now, something that's not necessarily obvious just from this discussion is how you would organize this blowing up the balloon as a computer program. But if you took a course in algorithms, you would learn that happily you can organize all of this computation in a way which is very efficient, which is super fast. So Dijkstra's algorithm, again, you would add other ideas as well to get state-of-the-art driving directions, but this is the foundation on which modern algorithms would be built. So those are the two examples I really
▶︎ 48:46 wanted to tell you about today. Karatsuba's method, for multiplying integers, and then shortest path algorithms such as Dijkstra's algorithm. And again, the takeaway I want you to have is less narrowly about these two problems per se. And more broadly appreciating, first of all, algorithms are fantastically useful for problems that we want to solve every single day. And secondly, computers and the algorithms that run on them can be even more useful than you would have thought because, at least for many problems including the two we looked at today, there are shortcuts. Not easily seen, but that have been identified by very clever algorithm designers and taken advantage of in state of the art algorithms.
▶︎ 49:31 More generally, honestly I'm kind of jealous of the people working in algorithms in the 1940s, 1950s, 1960s, when computers were first becoming built, and their value was first becoming appreciated. There was so much cool work to do. There's still a ton of cool, cool work to do in algorithms and computer science more broadly, don't get me wrong. But man, it was greatest hit after greatest hit every year of the '50s, every year of the '60s, it just seemed like it was an awesome time to be in the area. For example, one of the highlights of the early era of algorithms would be the simplex method.
▶︎ 50:09 Invented, I don't know if you say invented, I don't know if you wanna say discovered, up to you. The simplex method for linear programming. That was discovered by George Dantzig. And even if you think you haven't heard of George Dantzig, I'll bet you have, because maybe you heard the inspirational story about the power of positive thinking.
▶︎ 50:31 It sounds apocryphal, but the way the story goes is a student walks in the class, they're five minutes late, they're kind of freaked out, there's this sage on the stage in this big auditorium and there are these math problems on the blackboard and the student assumes they must be homework. "Oh man, I missed what the professor said about the homework but let me just write down these problems and then I'll turn in my solutions." The student works on the problems and, "Man, for homework one, these are not that easy of problems. These are difficult." Three weeks later finally, the student goes to the professor and is like, "Professor, I'm sorry, I know I'm weeks late, but I finally solved homework one, here's my solution." The professor wasn't there, slipped it under the professor's door and the student went on with their life.
▶︎ 51:20 At midnight, student bam, bam, bam, on the dorm's door. It's the professor with the student's homework saying, "This wasn't homework. These are the two biggest open questions in this area of statistics." So the point being is if you don't know that something's supposed to be too hard, well, maybe it helps you actually do it. You probably thought this story was apocryphal. This story is actually about George Dantzig. This is George Dantzig's thesis from Berkeley, the Berkeley Stat Department, is literally the two problems that he solved in exactly this story.
▶︎ 51:54 That was 1939. Fast forward to the mid to late '40s, like '47. He's working I believe for the Air Force, working for the military right after World War II, and a superior challenges him to find some systematic way of doing military planning, like figuring out how much supplies to send to different places. And Dantzig comes up with something known as the simplex method for linear programming.
▶︎ 52:18 First of all, he discovered the abstraction of a linear program, which by itself is super useful, and then he discovered this fantastic algorithm for solving linear programs in practice extremely quickly, known as the simplex method. That's, I give you that as an example of one of the just utter gems. Literally still useful to this day. 80 years later, simplex method is still used all the time. Very powerful algorithm. That was an example of something that came out in the late '40s.
▶︎ 52:45 Another, maybe one more Dantzig story, just because it ties into a different character that's showed up in these lectures. We mentioned John von Neumann a little bit in episode one. Famous mathematician, one of the most famous mathematicians of the 20th century. Involved in the early computing efforts like the EDVAC and the ENIAC. And so Dantzig writes, in his memoirs, writes about meeting von Neumann, maybe for the first time, maybe for the only time, I don't quite remember. Again, around '47, '48, something like that.
▶︎ 53:19 And so Dantzig goes and meets von Neumann. Von Neumann's super famous at this point. So Dantzig's a bit nervous. Dantzig's young and he has this simplex method and he's trying to verify that it's new. Dantzig is worried that maybe someone else has already come up with a simplex method, let me tell it to the experts and see what they say. And so he goes to von Neumann and he starts with a motivation. He's like, "You know, imagine that you want to ship supplies from here to here," blah.
▶︎ 53:48 And von Neumann, just one of the things he's very famous for is just being unbelievably quick. He just does like a CPU that, or had a CPU that runs at like 100X the speed of any of the rest of us, including professional mathematicians by all accounts. And so he interrupts Dantzig and he's like, "Get to the point. You're wasting my time. What do you wanna know?" And so then Dantzig gets, he's kind of offended and he's like, "Okay, if you want the fast version." And then he goes to the whiteboard and he talks about linear programming, talks about the simplex method in like five minutes. Which is a very, very quick version of doing the simplex method. And so von Neumann listens to him and was like, "Oh, is that what you're talking about?"
▶︎ 54:28 And von Neumann didn't know the simplex method. The simplex method by all accounts really was discovered first by Dantzig. But the concept of linear programming that Dantzig had come up with was very closely related to the game theory that von Neumann was working on at that time. And in particular, von Neumann has a famous result from game theory known as the minimax theorem, which is about in a zero sum game the order of the players in some sense doesn't matter.
▶︎ 54:54 And so von Neumann there in real time absorbs Dantzig's version of linear programming, understands the simplex method, and then realizes in real time that the minimax theorem he's been working with corresponds to what we would now call the theory of linear programming duality, and that's something that Dantzig had not realized yet. So von Neumann pointed out, "Oh, for each of these linear programs, there's actually this dual linear program and there's all these amazing properties, like strong duality and elementary slackness," et cetera, et cetera. So told Dantzig all that in real time, and then the first papers about LP duality were co-written by Dantzig and von Neumann.
▶︎ 55:29 So this was the kind of stuff that was happening in that era, which just, man, to be a fly on the wall at any of these meetings would have been very, very special. But at least we get to read about the accounts from the people who were there.
▶︎ 55:44 It was a golden era for algorithms in the '40s, '50s, and '60s. More and more computational problems just started falling to the genius ideas of those early algorithm designers, simplex method, Dijkstra's algorithm, many other examples. But again, if you try to extrapolate, you might be, oh, well, eventually we'll just have clever algorithms for all possible problems. We'll be able to solve any problem that we want. But again, before any of this, before any of this era, we have Turing's 1936 paper.
▶︎ 56:14 From the day we were thinking about algorithms, we knew that they had limitations. We knew that there will be natural problems like the halting problem, which will never be solved by any mechanical procedure, never be, never be solved by any computer, no matter how good our technology. So we see this back and forth between what you can do with computation and what you can't do with computation.
▶︎ 56:36 What you might say next is like, "Okay, okay, I concede. The halting problem, I get it. It would be useful to have an algorithm for the halting problem. We're not gonna have one." But come on, let's think about day-to-day life. Driving directions. That's a good example. That's something I wanna solve in day-to-day life. Or, I don't know, organizing my daily schedule. Accommodating conflicts I might have with other people. Another example of a problem I wanna solve in everyday life.
▶︎ 57:03 Surely for these simple, natural problems, they should all be easily solved by a computer. It's only more technical problems, like the halting problem, which maybe elude computation. Everything else should be easy. But don't forget about the astronomical number of options that we saw in the shortest path problem. Already, if you need to make 265 independent decisions, the number of different options you have to consider is more than the number of atoms in the estimated number of atoms in the known universe. So exhaustive search is completely infeasible in problems of that size.
▶︎ 57:45 Now for the shortest path problem, it wasn't a big deal, because we found the algorithmic shortcut. That was what was taken advantage of by Dijkstra's algorithm and reusing work across all of the different possible options. So the question then is, are there always algorithmic shortcuts, like there are in the shortest path problem, for these natural problems which come up in our day-to-day life? Or conversely, could it be that some of those problems, that actually there is nothing better out there, other than exhaustively searching through all of the outcomes?
▶︎ 58:18 So for example, I told you some stories about George Dantzig, and he had the same experience. It was just problem after problem, he was knocking out. Simplex method was solving all kinds of stuff. There were other algorithms for problems like maximum flow. Tons of successes. But there was this other problem which Dantzig spent a lot of time on called the traveling salesperson problem, or TSP. And everything Dantzig threw at the TSP didn't seem to work. So the problem just resisted every single idea that he and all of his colleagues were having for algorithmic shortcuts.
▶︎ 58:56 So could it be then that there are simple examples like the traveling salesperson problem, which we'll talk more about next time, could it be that they both have an astronomical number of options and there is no really fundamentally superior version to sift through them other than exhaustive search? So that gets us to one of the deepest open questions in all of mathematics, certainly the deepest open question in computer science, P versus NP, which will be the subject of the next two episodes. Hope to see you there.