Speaker 1: Welcome to tech Stuff, a production from I Heart Radio.
Speaker 1: Hey there, and welcome to tech Stuff. I'm your host,
Speaker 1: Jonathan Strickland. I'm an executive producer with I Heart Radio.
Speaker 1: And how the tech are you. I'm not doing so
Speaker 1: great myself right now. I'm running a low fever. I'm
Speaker 1: hoping that I just have like a stomach bug or
Speaker 1: something and that it's not a second case of COVID,
Speaker 1: because I don't want to be that guy. Uh. And
Speaker 1: that's a good reminder that if you are in an
Speaker 1: area where the COVID numbers have not really slacked off,
Speaker 1: still a good idea to wear a mask, you know,
Speaker 1: limit your exposure to other folks. Seriously, this is no fun.
Speaker 1: You don't want to go through it if you can
Speaker 1: avoid it. So yeah, just you know, I care about
Speaker 1: you guys, so take care of yourself. Also, you know
Speaker 1: that means that I'm not really able to write a
Speaker 1: new episode because I can't read good when I got
Speaker 1: a fever. So we're gonna have a little bit of
Speaker 1: a rerun. I apologize for that. I wish I could
Speaker 1: avoid it, I really do. But I also feel like
Speaker 1: this is an episode that is timeless. It's one that
Speaker 1: is important. It's called what Is an Algorithm? Which originally
Speaker 1: published last year on July twenty one, And the reason
Speaker 1: why I think it's important is that a lot of
Speaker 1: people know the word algorithm, but they don't have a
Speaker 1: deeper appreciation of what that actually means. We almost just
Speaker 1: use it as a placeholder. It might as well be magic, right.
Speaker 1: The Facebook algorithm determines what you see and what you
Speaker 1: don't see, but that doesn't really explain what an algorithm is.
Speaker 1: So I hope that you find this episode interesting and
Speaker 1: if you would like to leave a suggestion for an
Speaker 1: episode topic for me in the future. There are a
Speaker 1: couple different ways of doing it. One is you can
Speaker 1: go over to the I Heart Radio podcast app, which
Speaker 1: is free. You can just navigate over to the tech
Speaker 1: stuff page and there is a little microphone icon which
Speaker 1: allows you to leave a talk back message up to
Speaker 1: thirty seconds in length, so you can always leave me
Speaker 1: a message if you like. You can indicate if I
Speaker 1: could use the audio in an upcoming episode, which would
Speaker 1: be a lot of fun. But I'm not gonna just
Speaker 1: assume that you're cool with that. You'll have to tell me.
Speaker 1: And um, A lot of people have been doing that.
Speaker 1: They've been leaving messages. It's been great. You've all been
Speaker 1: so kind and so enthusiastic, and I love it. Keep
Speaker 1: them coming. Also, if you don't want to use the app,
Speaker 1: I totally get it. You can always leave me a
Speaker 1: message on Twitter. The handle for the show is tech
Speaker 1: Stuff hs W. Now let's get to this episode that
Speaker 1: originally published July twenty one, two thousand twenty one. What
Speaker 1: is an algorithm? I frequently speak about algorithms on the show.
Speaker 1: I talked about them all the time, about Facebook's algorithm
Speaker 1: or YouTube's algorithm. We talk about search algorithms and recommendation
Speaker 1: algorithms and tons of others. But I haven't really spent
Speaker 1: a ton of time talking about what algorithms actually are.
Speaker 1: Like it kind of become shorthand for do not look
Speaker 1: behind the curtain, right, It doesn't really help you if
Speaker 1: you don't know more about it. Uh. I might go
Speaker 1: as far as to say it's a set of rules
Speaker 1: or instructions to carry out a task, but that's pretty
Speaker 1: reductive and it doesn't really help you understand what algorithms
Speaker 1: actually do. So today I thought we'd talk a little
Speaker 1: bit about algorithms and what they do in general, and
Speaker 1: then maybe chat about a few famous examples and some fun,
Speaker 1: little quirky stuff. So before I dive into this, we
Speaker 1: do need to establish a few things, and arguably the
Speaker 1: most important of those things is that I am not
Speaker 1: a mathematician. I am not a computer scientist. I'm a
Speaker 1: guy who loves tech, and I'm decent at research, and
Speaker 1: I do my best to communicate topics in an informative
Speaker 1: and you know, on a good day and entertaining way.
Speaker 1: So with that in mind, I fully admit that this
Speaker 1: is a subject that is outside of my narrow expertise,
Speaker 1: and so my descriptions and explanations will be from a
Speaker 1: very high level. Uh. And you might even be able
Speaker 1: to get something like this just by glancing at a
Speaker 1: pamphlet that's about a computer science introductory course. So for
Speaker 1: all you folks out there who are deep in the
Speaker 1: computer sciences, this is going to be like a children's
Speaker 1: story book for you, possibly one where you don't like
Speaker 1: de illustrations very much. Another thing that I need to
Speaker 1: establish is that algorithm itself is a very broad term,
Speaker 1: you know, in that sense, it's kind of like the
Speaker 1: word program or app or software, and that these words
Speaker 1: are categories that can have a wide variety of specific instances.
Speaker 1: For example, let's just take a look at software. If
Speaker 1: I'm talking about software, I could be talking about a
Speaker 1: very simple program that serves as a basic calculator that
Speaker 1: can add and subtract and divide and multiply. That could
Speaker 1: be a piece of software, be a very simple one.
Speaker 1: Or I might talk about something a little more complicated,
Speaker 1: like a word processing program. Or I could talk about
Speaker 1: an advanced three D shooter video game, or an incredibly
Speaker 1: complicated computer simulation program, or anything in between. All of
Speaker 1: those could fall into the realm of software well. Algorithms
Speaker 1: similarly come in a wide variety of functions and complexity.
Speaker 1: There are some that are elegant in their simplicity, and
Speaker 1: there are some that when I look at them written
Speaker 1: out in in what is clearly well defined terminology, uh,
Speaker 1: I'm just left wondering what the heck it is I
Speaker 1: just saw. They might as well be hieroglyphics to me.
Speaker 1: In other words, but let's start off by talking about
Speaker 1: the word algorithm itself. Now, unlike a lot of words
Speaker 1: that we use specifically in English, algorithm does not have
Speaker 1: its roots in Latin vocabulary. There are words in Latin
Speaker 1: that are like al gore and things like that, but
Speaker 1: that's not where algorithm comes from. Instead, it's a Latinized
Speaker 1: version of an Arabic name. Algorithm comes from algorithmic, which
Speaker 1: is the name that Latin scholars gave to a brilliant
Speaker 1: man named al Ka Ritzmy and my apologies for the
Speaker 1: butchering of the pronunciation of that name. No disrespect is intended.
Speaker 1: It's merely American ignorance anyway. This particular mathematician philosophers scholar
Speaker 1: served as a very important astronomer and librarian in Baghdad
Speaker 1: in the ninth century. His work in mathematics was truly foundational,
Speaker 1: so much so that we get the word algebra from
Speaker 1: a work that he published. He treated algebra as a
Speaker 1: distinct branch of mathematics, when before it was just kind
Speaker 1: of lumped in with other stuff. And he did a
Speaker 1: lot of work and showing how to work various types
Speaker 1: of equations and how to balance equations. And on a
Speaker 1: personal note, this was something that I used to love
Speaker 1: to do in my mathematics courses. I could really see
Speaker 1: the beauty in determining if two sides of an equation
Speaker 1: truly were equal. It was like an elegant puzzle, and
Speaker 1: I really love that. But again, just to be clear,
Speaker 1: my love of algebra and trigonometry is pretty much where
Speaker 1: math and I parted ways, because when calculus came along,
Speaker 1: I was I was pretty much done. So at that
Speaker 1: point it was it was beyond my ken as they say. Anyway,
Speaker 1: back to our Arabic scholar, he highlighted the importance and
Speaker 1: effectiveness of using a methodical approach towards the solution of problems,
Speaker 1: and that kind of gets at the heart of what
Speaker 1: our gorhythms actually are. The basic definition, which I kind
Speaker 1: of alluded to earlier is quote a process or set
Speaker 1: of rules to be followed in calculations or other problems
Speaker 1: solving operations, especially by a computer. End quote that's from
Speaker 1: Oxford Languages. But you know this can apply to all
Speaker 1: sorts of stuff. For example, if you've ever seen anyone
Speaker 1: who can solve Rubics cubes, those those puzzles that are
Speaker 1: in cube form where you've got all the little, uh
Speaker 1: different colors of squares and your job is to make
Speaker 1: each side of the cube the same color. Well, there
Speaker 1: are people who can solve Rubik's cubes in in a
Speaker 1: fraction of like, like less than a minute. It's it's
Speaker 1: amazing to watch them go. It's so fast and it's
Speaker 1: hard to keep up with what they're doing. They are
Speaker 1: essentially following algorithms, these processes that will get to a
Speaker 1: dependable and replicable outcome based on what you're doing. Um So,
Speaker 1: an algorithm is really just a way for us to
Speaker 1: problem solve. Let's say we have a particular outcome that
Speaker 1: we want to achieve. The algorithm is the recipe that
Speaker 1: we followed to go from whatever our starting condition is
Speaker 1: our starting state. In order to get to the outcome
Speaker 1: we want to our target state, it needs to be
Speaker 1: well defined. Algorithms have to be well defined because computers
Speaker 1: are not really capable of implementing vague instructions. It needs
Speaker 1: to have a pretty solid approach so that the computer,
Speaker 1: when following the algorithm quote unquote, knows exactly what to
Speaker 1: do based upon the current state of the problem. It
Speaker 1: also needs to be finite. Computers are not capable of
Speaker 1: handling infinite possibilities, so the algorithm has to work within
Speaker 1: certain parameters, and those parameters depend upon the nature of
Speaker 1: the problem you're trying to solve. And the equipment that
Speaker 1: you have to solve it with. So let's take a
Speaker 1: problem that computers typically struggle to achieve, and that is
Speaker 1: random number generation or r in G. Now you would
Speaker 1: think that creating a random number would be easy. I mean,
Speaker 1: we can do it just by throwing some dice for example, Right,
Speaker 1: you can throw a die and and whatever the number
Speaker 1: comes up, that's your random number. But computers have to
Speaker 1: follow specific instructions and execute operations that by definition need
Speaker 1: to have a predictable and replicable outcomes. So computers find
Speaker 1: random number generation really tricky. Typically, the best we can
Speaker 1: hope for when it comes down to this sort of
Speaker 1: thing is pseudo random numbers. So these are numbers that,
Speaker 1: to an extent, appear to be random, right Like, on
Speaker 1: casual observation, it looks like the computer is generating random numbers. However,
Speaker 1: if you were to really seriously dig down into the process,
Speaker 1: you might discover that they are not really really random
Speaker 1: at all. But we just need them to be random enough, right.
Speaker 1: We need it to be close enough to seeming to
Speaker 1: be random for it to fulfill the function we need
Speaker 1: if it's not truly random. For a lot of applications
Speaker 1: that ends up being, you know, negligible. On a related note,
Speaker 1: there are some types of mathematical problems that have many
Speaker 1: degrees of freedom lots of variables, for example. So a
Speaker 1: problem that does have a lot of variables could have
Speaker 1: a lot of potential solutions, and so it could be
Speaker 1: a challenge for computers to solve. We need algorithms to
Speaker 1: tackle these sorts of problems, to go at them in
Speaker 1: ways that go beyond deterministic computation, which I guess I
Speaker 1: should define that. So, deterministic computation refers to a process
Speaker 1: in which each successive state of an operation depends completely
Speaker 1: on the previous state. So what comes next always depends
Speaker 1: upon what came just before. And I'll give you an example.
Speaker 1: Let's say I give you a math problem, and I
Speaker 1: say you need to add these two numbers together. And
Speaker 1: let's say it's like, uh, five and six, and then
Speaker 1: from the sum of those numbers you have to subtract four. Well,
Speaker 1: you would first add those two numbers together, so five
Speaker 1: plus six you got eleven, and then you would subtract
Speaker 1: four from that number, and so eleven minus four equal seven.
Speaker 1: And this process is deterministic because I gave you those
Speaker 1: specific instructions that computers do really well with deterministic processes.
Speaker 1: These are pretty easy to follow. These sorts of processes
Speaker 1: are by their nature replicable. So in other words, if
Speaker 1: I ask you to do that same operation, if I
Speaker 1: tell you add five and six together and then subtract four,
Speaker 1: it doesn't matter how many times you are you do
Speaker 1: that that process, right, You're always going to come out
Speaker 1: with the same answer. It's always going to come back
Speaker 1: no matter what you do, You're gonna always of seven
Speaker 1: as your answer, just based on that same input. So
Speaker 1: there are a family of algorithms that collectively get the
Speaker 1: name Monte Carlo algorithms, and they're named after Monte Carlo,
Speaker 1: the area of Monaco that is famous for being the
Speaker 1: location of lots of high end casinos have been there.
Speaker 1: It's not really my jam, but it is pretty darn flashy.
Speaker 1: So the reason these algorithms get the name Monte Carlo
Speaker 1: algorithms is that, like gambling, they deal with an element
Speaker 1: of randomization. So gambling is called gambling because you're taking
Speaker 1: a risk. You're gambling, you're betting that you're gonna beat
Speaker 1: the odds in whichever game it is that you're playing.
Speaker 1: And that you're going to achieve an outcome that's favorable
Speaker 1: to you, which you experience as a payout. So, whether
Speaker 1: it's throwing dice or playing a card game, or placing
Speaker 1: bets at a roulette wheel or playing a slot machine,
Speaker 1: you are engaged in an activity in which there is
Speaker 1: some element of chance, at least in theory if the
Speaker 1: game is honest, and what you're hoping for is that
Speaker 1: chance lands in your favor. Similarly, Monte Carlo algorithms often
Speaker 1: focus on chance and risk assessments such as what are
Speaker 1: the odds that if I do this one thing, I'm
Speaker 1: gonna totally regret doing it later? But you know, more
Speaker 1: of the a computational problem and not a lifestyle choice. Well,
Speaker 1: back in ninet, scientists at the Los Alamos Scientific Laboratory,
Speaker 1: including John von Neumann, uh stand All Lam and Nick
Speaker 1: Metropolis propose what would become known as the Metropolis algorithm,
Speaker 1: one of the Monte Carlo algorithms, and the purpose of
Speaker 1: this algorithm was to approximate solutions two very complicated mathematical
Speaker 1: problems where going through a deterministic approach to find the
Speaker 1: definitive answer just wasn't feasible. So In other words, for
Speaker 1: certain complicated math problems, figuring out the quote unquote real
Speaker 1: answer would really just take too long, perhaps to the
Speaker 1: point where you would never get there within your lifetime.
Speaker 1: So you need a way to kind of get a
Speaker 1: ballpark solution that hopefully is closer to being correct than incorrect.
Speaker 1: Doesn't sound like the sort of thing that computers would
Speaker 1: be particularly good at doing right off the bat, right.
Speaker 1: In fact, the algorithm allows computers to mimic a randomized process,
Speaker 1: so it's not truly random, but it's random ish if
Speaker 1: you like, and it uses this to approximate a solution
Speaker 1: to whatever the problem is that you're trying to solve
Speaker 1: that falls into this category. I once saw a simulation
Speaker 1: of a randomized process using the Monte Carlo method that
Speaker 1: I thought was pretty nifty, and it was determining what
Speaker 1: is the value of pie. Let's say that you don't
Speaker 1: know the value of pie and you're just trying to
Speaker 1: figure it out. So and by the way, I mean
Speaker 1: pie is in p I not as in the delicious
Speaker 1: pie dessert treat. So here's the scenario. Imagine that you've
Speaker 1: got a table and the tables like, I don't know,
Speaker 1: three ft to a side, and positioned over this table
Speaker 1: is a robotic arm. And this robotic arm can pick
Speaker 1: up and drop large ball bearings onto the table, and
Speaker 1: the arm can just move over the entire region of
Speaker 1: the table, so it's got a three ft by three
Speaker 1: ft range of motion. And in on this table you
Speaker 1: set down two containers. You've got one that's that's a
Speaker 1: circular container and one that's square. And the square container
Speaker 1: measures six inches to a side. The radius of the
Speaker 1: circular container is also six inches, so that means it's
Speaker 1: got a twelve inch diameter. Right, So those are your containers,
Speaker 1: and you've got your situation with your your robot arm
Speaker 1: above this three ft square table. So the robotic arms
Speaker 1: job is to pick up ball bearings and then from
Speaker 1: a random que will drop that ball bearing somewhere above
Speaker 1: the table. So some of those balls are going to
Speaker 1: fall into the square container, some of them are going
Speaker 1: to fall into the round container, some of them are
Speaker 1: not going to fall in either. And if the process
Speaker 1: is truly random, meaning there's an equal chance that it
Speaker 1: will drop a ball bearing over any given point of
Speaker 1: that table, over time, we would expect to see more
Speaker 1: ball bearings fall into the round container because it has
Speaker 1: a greater area and there's more space for a ball
Speaker 1: bearing to fall into one of these. At the end
Speaker 1: of repeating this process many, many times, we should be
Speaker 1: able to take these two containers and then count the
Speaker 1: number of ball bearings in each of them. And if
Speaker 1: we divide the number of ball bearings in the circular
Speaker 1: container by the number of ball bearings that fell into
Speaker 1: the square container, we're gonna get results that should be
Speaker 1: really close to pie. And you might think, wait, why
Speaker 1: why would the number of ball bearings in one container
Speaker 1: versus another, and then dividing those why would you get pie? Well,
Speaker 1: if you have a process that is uniformly random across
Speaker 1: an area, like our hypothetical three ft square table, the
Speaker 1: probability that a dropped ball bearing will land in one
Speaker 1: of those two specific containers is proportional to that specific
Speaker 1: containers area or cross section. So then we just ask, all, right, well,
Speaker 1: how do we define area? Well, with the square, it's
Speaker 1: really simple, right. We take one side of a square
Speaker 1: in this case, it's six inches, and we multiply it
Speaker 1: by itself six times six. Because all sides of a
Speaker 1: square are equal, we know that the length and the
Speaker 1: width are each going to be six inches. We multiply
Speaker 1: those together. We get thirty six square inches. That is
Speaker 1: the area or cross section of our square container. But
Speaker 1: for our circular container, we take the radius, which again
Speaker 1: this case, the radius is six inches, and we square
Speaker 1: it and then we multiply that number by pie. So
Speaker 1: area for the circular container is six times six squared
Speaker 1: times pie. And if we divide the cross section of
Speaker 1: the circular container by the cross section of the square container,
Speaker 1: the two six squared you know, the two elements the
Speaker 1: squared elements cancel each other out, and so all we're
Speaker 1: left with is pie. So the end result is that
Speaker 1: when we count up these ball bearings that have landed
Speaker 1: randomly in these containers, that that difference, the division that
Speaker 1: we get that should be a close approximation of pie.
Speaker 1: Now it's not going to be precise. Chances are the
Speaker 1: number of ball bearings in the two containers will just
Speaker 1: get you close to pie. But it illustrates how a
Speaker 1: randomized process can help you get to a particular solution
Speaker 1: that might otherwise be difficult to ascertain. There are videos
Speaker 1: on YouTube that show this particular simulation. It's kind of
Speaker 1: a famous one. So you can actually watch and get
Speaker 1: kind of an understanding of what I said to you
Speaker 1: makes no sense whatsoever. There are other options for you
Speaker 1: to look into that might help, And that is a
Speaker 1: great example. But what are the actual algorithms that fall
Speaker 1: into the Monte Carlo methods spectrum? What are they used
Speaker 1: to do well? They can be used to simulate things
Speaker 1: like fluid dynamics, or cellular structures or the interaction of
Speaker 1: disordered materials. So in other words, these are all processes.
Speaker 1: They have a lot of potential variables at play, and
Speaker 1: you can think of variables as representing uncertainty, something that
Speaker 1: computers typically don't do well with. You know, from a
Speaker 1: general stance, computers excel at specific instances rather than potential instances.
Speaker 1: So algorithms like the Metropolis algor rhythm would lead computer
Speaker 1: scientists to develop methodologies to kind of work around the
Speaker 1: limitations of computers and leverage computational power and tackling very
Speaker 1: difficult problems in that way. In the Monte Carlo family
Speaker 1: of algorithms, we typically assume that the results we get
Speaker 1: are going to have a potential for being wrong, like
Speaker 1: there'll be a small percentage of error that we have
Speaker 1: to take into account, and so keeping that in mind,
Speaker 1: we need to frame results as being again approximations of
Speaker 1: an answer, rather than the definitive answer to whatever problem
Speaker 1: it is we're trying to solve. For me, this was
Speaker 1: one of those things that was very difficult to grasp
Speaker 1: for a long time because I was equating it to
Speaker 1: math class, where you're supposed to get the answer. Now,
Speaker 1: when we come back, we'll talk about a few more
Speaker 1: famous algorithms and what they do. But first let's take
Speaker 1: a quick break. Now. In our previous section, I talked
Speaker 1: about a family of algorithms that trace their history back
Speaker 1: to nineteen and so does the next one I want
Speaker 1: to talk about, which was created by George Dantzig, who
Speaker 1: worked for the Rand Corporation. And Danzig created a process
Speaker 1: that would lead to what we call linear programming. So
Speaker 1: at its most basic level, linear programming is about taking
Speaker 1: some function and maximizing or minimizing that function with regard
Speaker 1: to various constraints. But that is super vague, right, I mean,
Speaker 1: it's not terribly helpful. It feels like I'm talking in
Speaker 1: a circle. But this is one that's really important for say,
Speaker 1: business developers. So let's talk about a slightly more specific
Speaker 1: use case. Let's say that you are launching a business
Speaker 1: and you're trying to make some you know, big decisions
Speaker 1: as you're going to do this, and you're going to
Speaker 1: manufacture and sell a product of some sort, some physical thing. Now,
Speaker 1: your whole goal as a business is to make money
Speaker 1: from the work you do, and to do that, you
Speaker 1: need to figure out what your costs are going to
Speaker 1: be and how you cannot just offset these costs but
Speaker 1: make enough money to actually profit from it, so cover
Speaker 1: all your costs plus some extra. So in this case,
Speaker 1: what you're trying to do is figuring out how you
Speaker 1: can minimize costs and maximize profits. Right. The constraints come
Speaker 1: into play as you start to look at specifics, like
Speaker 1: maybe you're gonna partner with a fabrication company, and maybe
Speaker 1: you've actually got a few choices. You've got different companies
Speaker 1: that you could go with. Well, these choices could represent
Speaker 1: constraints in your approach. Perhaps one is more expensive than
Speaker 1: the others, but it can produce a greater volume of product,
Speaker 1: so you'd be able to get more product out to
Speaker 1: market in less time. Or maybe you've got one that's
Speaker 1: more expensive but it's also less likely to have fabrication errors,
Speaker 1: and errors can be both costly and time can assuming
Speaker 1: to address. So you have to quantify all these variables
Speaker 1: and use them as constraints to start figuring out your
Speaker 1: men maxing approach. Here, linear programming simply looks for the
Speaker 1: optimum value of a linear expression, and depending on the
Speaker 1: problem you're trying to solve, like maximizing profit versus minimizing costs,
Speaker 1: you're either looking for the highest value being optimum or
Speaker 1: the lowest value being optimum. Like with costs, you want
Speaker 1: that to be the lowest, and you have to look
Speaker 1: at what constraints are at play with any given expression.
Speaker 1: So Danzing's approach to linear programming, called the simplex method,
Speaker 1: was efficient and elegant and far more simplified than other
Speaker 1: methodologies attempting to kind of do the same thing around
Speaker 1: that time. But it also had some limitations, and that's
Speaker 1: because the real world isn't as simple as math tends
Speaker 1: to be. Like math tends to be pretty, you know,
Speaker 1: firm in the grand scheme of things in the world
Speaker 1: is a little more wibbly. Doubly, so, a linear programming
Speaker 1: solution only works if the various relationships between the different
Speaker 1: elements like the requirements and the restrictions and constraints that
Speaker 1: you've set up with this problem. It only works if
Speaker 1: all of those relationships are linear, or, in other words,
Speaker 1: for a given change in one variable, we see a
Speaker 1: given change in other variables. And that is super vague,
Speaker 1: So we're going to talk about two variables. Will reduce
Speaker 1: it down to that. So we'll use the classic X
Speaker 1: and Y as our variables. Those can stand in for
Speaker 1: all sorts of different values. And let's say that we
Speaker 1: see there's a relationship between X and Y, and that
Speaker 1: if the value of X changes from one to two,
Speaker 1: we then see that the value of Y goes from
Speaker 1: three to nine. Well, that doesn't tell us anything on
Speaker 1: its own, right, We just know that if x is one,
Speaker 1: y is three. If x is two, y is nine.
Speaker 1: If we then see that if x is three, then
Speaker 1: why is fifteen? And when x is four, why is
Speaker 1: twenty one? We start to see a linear relationship because
Speaker 1: each time X increases by one, why increases by six.
Speaker 1: The rate of increase for each variable is linear. It's
Speaker 1: it's not like the rate of increase doesn't change. So
Speaker 1: we've got this linear relationship here. We can contrast this
Speaker 1: with exponential relationships, in which we see not a constant increase,
Speaker 1: but a constant ratio in successive terms in one variable
Speaker 1: when you change another. So in this case, let's say
Speaker 1: that we find out then, when X is one, why
Speaker 1: is three? When X is two, why is nine? When
Speaker 1: X is three, why is twenties seven? Now we see
Speaker 1: that why is not increasing by six each time. We're
Speaker 1: seeing that the value of why is multiplied by three
Speaker 1: each time X goes up once. So we're seeing there's
Speaker 1: a constant ratio of change with why with regard to X.
Speaker 1: This gets into an exponential relationship. So when someone describes
Speaker 1: something is having exponential growth, what this is supposed to
Speaker 1: mean is that you should see a rate of growth
Speaker 1: that is increasing by some exponent for given unit of time.
Speaker 1: So it's not just that the thing is growing. In fact,
Speaker 1: it's not even that the thing is growing quickly. It's
Speaker 1: that the thing is growing faster as time goes on,
Speaker 1: so that you would say today it's growing, you know,
Speaker 1: say twice as fast as it was growing yesterday, and
Speaker 1: tomorrow it will grow twice as fast as it was
Speaker 1: growing today. And a lot of people use this phrase incorrectly.
Speaker 1: We often really just mean yo, that thing is growing
Speaker 1: wicked fast, but we don't necessarily mean yo, that thing
Speaker 1: is growing wicked fast, and the rate of growth increases
Speaker 1: by a constant amount over time, So you know, it's
Speaker 1: it's an important distinction to make. Anyway, that was a
Speaker 1: bit of a tangent to say that linear programming works
Speaker 1: if the relationships between all the variables is in fact linear.
Speaker 1: But if if it's not, If the relationship, say is
Speaker 1: exponential or logarithmic or anything like that, linear programming doesn't apply.
Speaker 1: And the real world is pretty darn complicated. So linear
Speaker 1: programming relies on sort of kind of dumbing down what's
Speaker 1: really going on in the real world. Two. Again, more
Speaker 1: of an approximation, and the solution that you arrive at
Speaker 1: might not be the ideal solution, but it might be
Speaker 1: good enough, depending upon what it is you're trying to do.
Speaker 1: Another limitation of linear programming is that as you add
Speaker 1: more variables to a problem, This is specific to the
Speaker 1: simplex method. As you add more variables, well, it grows
Speaker 1: more difficult to lay out in a linear fashion. You're
Speaker 1: you're adding more uncertainty, and the methodology has trouble dealing
Speaker 1: with additional uncertainty. Perhaps ironically, the complexity of the linear
Speaker 1: function would grow exponentially as more variables joined a problem.
Speaker 1: So this process would be unsuitable for certain subsets of
Speaker 1: computational problems because they just would get so complex that
Speaker 1: even the most advanced computers in the world wouldn't be
Speaker 1: able to handle them. Later on, other mathematicians would propose
Speaker 1: algorithms that could compensate for this particular limitation of the
Speaker 1: simplex method. For example, there are polynomial time algorithms. We're
Speaker 1: gonna leave that for the time being, because ain't no
Speaker 1: way I'm going to get that right anyway. I wanted
Speaker 1: to talk about those two algorithms, in particular, the Metropolis
Speaker 1: algorithm and the simplex method, because they are the foundation
Speaker 1: for a lot of work that's been done in computer science.
Speaker 1: But let's get some really basic ideas in with the
Speaker 1: next one. Let's talk about sorting. Sorting is all about
Speaker 1: arranging a list of things in order with regard to
Speaker 1: some specific feature of those things. That seems pretty basic, right,
Speaker 1: I Mean, there's a real world example that I think
Speaker 1: most of us have had in the past, which is
Speaker 1: that let's say you're looking at an online store and
Speaker 1: you're searching for a specific product or specific type of product.
Speaker 1: Let's say it's a blender, because I had to do
Speaker 1: this recently, right, So you go to some online store
Speaker 1: and you're searching for blenders and you get results, Well,
Speaker 1: you might actually want to sort those results by a
Speaker 1: specific way. Maybe you want to sort it by price,
Speaker 1: and you want to go low to high because you
Speaker 1: have a specific budget, so you just want to look at,
Speaker 1: you know, blenders that are an x price or less.
Speaker 1: Maybe you want to sort it by high price too
Speaker 1: low because maybe you're a fat cat tycoon type and
Speaker 1: you're just thinking, I want whatever is the most expensive.
Speaker 1: Or maybe you want to sort the results by customer
Speaker 1: review because we know rice and quality don't always go
Speaker 1: hand in hand. Maybe you just want to look at
Speaker 1: all the blenders in alphabetical order, or maybe you want
Speaker 1: to look at them in a reverse alphabetical order. You
Speaker 1: do you. Sorting is one of those most basic functions
Speaker 1: and heavily studied concepts within computer science, so much so
Speaker 1: that a lot of programming language libraries have sorting functions
Speaker 1: built into them. But it's still one of those things
Speaker 1: that people look at to see if there are better
Speaker 1: ways to sort various types of data, particularly as you
Speaker 1: get into a larger number of of sortable features um
Speaker 1: and it becomes really important. So let's take Google's search
Speaker 1: algorithm for example. Now, that name suggests that the algorithm
Speaker 1: we're talking about is related to the process of searching
Speaker 1: the web for pages that relate to a given search query,
Speaker 1: and in fact, Google does have a search algorithm that
Speaker 1: does this. But most of the time I hear people
Speaker 1: talking about the search algorithm, they actually mean that the
Speaker 1: algorithm that Google relies upon to determine what the order
Speaker 1: of search results are going to be that a person
Speaker 1: sees when they search for, you know, whatever it might be.
Speaker 1: This is critically important because multiple studies have shown that
Speaker 1: most people never bother to go beyond the first page
Speaker 1: of search results, which means that Google really needs to
Speaker 1: do its best to make sure that the most relevant
Speaker 1: results to any given search query show up toward the
Speaker 1: top of this list, because most people are never going
Speaker 1: to bother going any further than that. And if those
Speaker 1: people decide that Google search results just aren't any good,
Speaker 1: they could conceivably use some other search engine. And let
Speaker 1: me tell you. Google hates that idea. So Google's goal
Speaker 1: is to present to users search results that are most
Speaker 1: likely going to meet whatever their needs are based on
Speaker 1: their search criteria. And way back in the day, Google
Speaker 1: relied pretty much solely on an algorithm called page rank,
Speaker 1: and from what I understand, Google still relies on page rink,
Speaker 1: but also makes use of several other algorithms to augment
Speaker 1: page drink. But the page rank algorithm would take a
Speaker 1: ton of stuff into account in the process of determining
Speaker 1: where within a list of search results any given example
Speaker 1: should appear. So let's say that I'm searching for blenders
Speaker 1: on Google for some reason, and the search algorithm has
Speaker 1: gone out and indexed a ton of web pages that
Speaker 1: deal with blenders. Let's say that one of those results
Speaker 1: is in a blog post that isn't that old, it's
Speaker 1: fairly recent, but from a mostly unknown source, and very
Speaker 1: few other documents are linking into this blog. Well, chances
Speaker 1: are that search result would appear really far down on
Speaker 1: the list, probably pages and pages and pages down on
Speaker 1: the results. But then let's say that there's another web
Speaker 1: page that belongs to an established entity, one that has
Speaker 1: a good reputation that's been around for a while, and
Speaker 1: there are a ton of other pages that link to
Speaker 1: this particular website, well, that one would probably rank fairly
Speaker 1: high on the list. So the page rank algorithm essentially
Speaker 1: assigns a score to each search result, and the value
Speaker 1: of that score depends upon lots of stuff I mentioned,
Speaker 1: as well as tons of other variables, and these variables
Speaker 1: can either boost a score higher or it can knock
Speaker 1: some points off. And then page rank would take all
Speaker 1: these different search results and order them based upon those scores.
Speaker 1: Essentially really oversimplifying here, but the idea was that the
Speaker 1: more reliable and therefore real event results would likely be
Speaker 1: the ones that were the most popular, So all those
Speaker 1: links that aimed at a page would count for a lot.
Speaker 1: If you happen to run the definitive page on blenders
Speaker 1: and everyone was linking to you, that would boost your
Speaker 1: page links score significantly. Now, clearly, just because something is
Speaker 1: popular doesn't necessarily mean it's the most relevant or valuable thing,
Speaker 1: but it's generally more true than it isn't true. It
Speaker 1: might not always be the absolute best result, but it
Speaker 1: might be reliably relevant, and that was what was important
Speaker 1: to Google and to Google's users. Again, it just needs
Speaker 1: to be good enough. So the page rank algorithm was
Speaker 1: using a pretty complex sorting method to determine which results
Speaker 1: should be the most visible. You can, of course, page
Speaker 1: through search results. You don't have to go with whichever
Speaker 1: one's are on page one, And in theory, if you
Speaker 1: keep on scrolling through, going to page after page after
Speaker 1: page of search results, then over time you should see
Speaker 1: that the results you're getting are not as relevant as
Speaker 1: those that appeared earlier on the list, assuming everything is
Speaker 1: working properly. Again, this doesn't always happen, but generally it's oh,
Speaker 1: it holds true, and yeah, I'm drastically oversimplifying. You could
Speaker 1: teach an entire computer science course on the page rink
Speaker 1: algorithm and how it works. We're not going to do that.
Speaker 1: I would just get it wrong anyway. Speaking of search, however,
Speaker 1: let's talk about a much simpler form of search that's
Speaker 1: based on a basic algorithm, and this is called binary search.
Speaker 1: This is a process that's meant to decrease the amount
Speaker 1: of time it takes to search for a specific value
Speaker 1: within a sordid array of values. Alright, so let's say
Speaker 1: that you've got a really big array or list of
Speaker 1: entries right, and it's massive, and you're searching for a
Speaker 1: specific target that has a specific value associated with it,
Speaker 1: and a computer could go through this list item by item,
Speaker 1: comparing it with your target right and look to see
Speaker 1: if there's a match. If there's not a match, you
Speaker 1: can go to the next item on the list and
Speaker 1: do that. But if you're talking about a truly huge list,
Speaker 1: this could take ages because if it happens to be
Speaker 1: at the bottom of that list, you have to wait
Speaker 1: for the computer to go through every single other entry
Speaker 1: before it gets there. So a binary search cuts this short.
Speaker 1: It takes a value that's in the middle of the array,
Speaker 1: so like halfway down the list. Essentially it just pulls
Speaker 1: that value and it compares it against your target, the
Speaker 1: thing that you're searching for. And if the array is
Speaker 1: a hundred thousand trees long, it's essentially looking at entry
Speaker 1: number fifty thousand and one. It compares this to your search.
Speaker 1: And let's say the value target of your of your
Speaker 1: search query is lower than the entry that appeared at
Speaker 1: fifty thousand and one. Well, now the binary search just
Speaker 1: tosses everything that's fifty and one or higher on the
Speaker 1: list because the values are only going to go up
Speaker 1: from there, so it can get rid of half the list.
Speaker 1: Right there, You're left with fifty thousand items in this array,
Speaker 1: and the algorithm repeats this process. It goes for an
Speaker 1: entry smack dab in the middle of the array, compares
Speaker 1: it to the target. If the target's value is lower
Speaker 1: than the middle entry of this array, then you you
Speaker 1: dump everything that's at a higher number than that if
Speaker 1: it's lower or its higher. Rather, if the target value
Speaker 1: is higher than the middle entry, then you would get
Speaker 1: rid of all the previous ones, like one through twenty
Speaker 1: five thousand. For example, Let's say that you know your
Speaker 1: your target value is higher than the middle entry of
Speaker 1: twenty and one. It's gonna dump everything from one to
Speaker 1: thousand and start over again and half it again again.
Speaker 1: I'm kind of oversimplifying here, but the idea of binary
Speaker 1: search is that rather than go through every single entry,
Speaker 1: it keeps cutting this array in half, comparing it with
Speaker 1: the target, and doing it again, which reduces the number
Speaker 1: of times it takes to find the specific answer. Uh.
Speaker 1: You might have thought of the like the the experiment
Speaker 1: where you think about you're given two pennies on day
Speaker 1: one and the next day, you're given four pennies or
Speaker 1: cents if you prefer two cents. The next day you
Speaker 1: get four cents. The next day you get eight cents,
Speaker 1: and it doubles, and pretty quickly you see how that
Speaker 1: doubling can actually start to amount to what we would consider,
Speaker 1: you know, like quote unquote real money, same sort of thing.
Speaker 1: By by having an array over and over again, you
Speaker 1: very quickly whittle down the stuff you have to go
Speaker 1: through and it speeds up the process of searching for
Speaker 1: a specific value within a huge UH data list. Binary
Speaker 1: search is just one form of search for for various
Speaker 1: data constructs. There are lots of others. For example, there's
Speaker 1: depth first search and breadth first search. I won't get
Speaker 1: too deep into this but because it gets really technical,
Speaker 1: but I can describe what's what's happening here from a
Speaker 1: high level. So these search functions are used for data
Speaker 1: structures that are that consists of nodes. And this is
Speaker 1: easier to understand if we use an analogy, and I
Speaker 1: want you to think of a choose your own adventure
Speaker 1: book in case you're not familiar with those. These are
Speaker 1: books where you would read a page and at the
Speaker 1: end of the page, you would actually be given a choice,
Speaker 1: like you could choose what the character you're reading about
Speaker 1: would do next. So you might get to the end
Speaker 1: of the first page of like a mystery book, and
Speaker 1: the instruction might say, if you want your protagonists to
Speaker 1: go down the hall, turn to page eight. If you
Speaker 1: want her to shut a door and walk away, turn
Speaker 1: to page twenty three, and you would make your choice,
Speaker 1: turn to that page and continue the story that way.
Speaker 1: And so the story branches, and you've got these branching pathways. Well.
Speaker 1: Depth first and breadth first searches explore nodes in different ways.
Speaker 1: A depth first search follows each branched path all the
Speaker 1: way down from start to the end of that one branch,
Speaker 1: before moving on to look at a different branch. So
Speaker 1: in our example, would the Choose your Own Adventure book,
Speaker 1: a depth first search would go to page eight to
Speaker 1: follow your protagonists down the hall. Then whatever the options
Speaker 1: were at the end of that, it would go with
Speaker 1: the first option, continue and doing this all the time
Speaker 1: until you get to the end of that pathway. Then
Speaker 1: it would come back up to the next most recent branch,
Speaker 1: follow that all the way to the end, and so
Speaker 1: on until it had searched through every possible pathway in
Speaker 1: this this uh this graph, that's what we would call it.
Speaker 1: Breath search instead progresses equally across all possible paths. So
Speaker 1: breath search would mean that you would go to page eight,
Speaker 1: and let's say at the end of page eight, it
Speaker 1: says you can then turn to page seventeen or page
Speaker 1: fifty two to make your next choice. But instead of
Speaker 1: continuing down that pathway, you back up to your starting
Speaker 1: position and then you go down to page twenty three.
Speaker 1: You know, the other option where you would close the
Speaker 1: door and walk away. You would read that maybe at
Speaker 1: the end of that page it says you can choose
Speaker 1: to either go to page three or to page forty six. Well,
Speaker 1: then you would go back to your your first branch.
Speaker 1: You would go down the list of pages seventeen and
Speaker 1: fifty two and three and forty six, maybe those all
Speaker 1: end in different choices. You would then do all of
Speaker 1: those across the board. Next you're you're searching across the
Speaker 1: width of the graph the breadth of it. Both are
Speaker 1: valid forms of searching, and the method used typically depends
Speaker 1: upon the type of data being searched and what you're
Speaker 1: trying to do. We've got a lot more to cover
Speaker 1: with algorithms, but I feel like I'm gonna have to
Speaker 1: give you guys a break, So let's do that really quick,
Speaker 1: and I'll just give you a very short example following,
Speaker 1: and then we'll pick up back up with algorithms again
Speaker 1: in a future episode. But first let's take this quick break,
Speaker 1: all right. I know I've waxed poetic about algorithms so
Speaker 1: much so that this episode is running longer than I anticipated.
Speaker 1: I have a whole extra section to talk about with algorithms,
Speaker 1: including things that are related to algorithms but aren't necessarily
Speaker 1: specifically algorithms, stuff like hashing and Markov models and things
Speaker 1: of that nature. But I want to finish up with
Speaker 1: one that I think is kind of fun. And this
Speaker 1: is called the Doomsday rule. And to be be fair,
Speaker 1: this is not just a computational algorithm. This is something
Speaker 1: that you can do in your head if you learn
Speaker 1: the rule. I'm not saying I could do it. I
Speaker 1: haven't really committed this to a memory process yet, but
Speaker 1: it is possible. And the Doomsday rule sounds pretty ominous, however, right.
Speaker 1: I mean, it's basically to figure out what day of
Speaker 1: the week any given date is So if you were
Speaker 1: an expert with the doomsday rule and I asked you, hey,
Speaker 1: what day of the week does June five fall on?
Speaker 1: You could use that rule and say, oh, that's gonna
Speaker 1: be a Thursday. That also, by the way, happens to
Speaker 1: be the day I'll turn fifty. Yikes, man, we're coming
Speaker 1: up on that one. All right, So where did this
Speaker 1: rule come from? And what the heck is this doomsday
Speaker 1: stuff about? Well, the doomsday thing is kind of just
Speaker 1: a cheeky name, and there's all these different ways we
Speaker 1: could describe that. But during any given year, there are
Speaker 1: certain dates that will always share the same day of
Speaker 1: the week, which is no big surprise, right. I mean,
Speaker 1: you might notice that Christmas, that is December, falls on
Speaker 1: the same day of the week as New Year's Day
Speaker 1: for the following year that happened, you know, January one.
Speaker 1: It always is that way. But with the doomsday rule,
Speaker 1: the dates for that are called doomsdays. Are things like
Speaker 1: April four or four four, June six that's six six,
Speaker 1: August eight that's eight eight, and you know, so on
Speaker 1: like October tenth, that's ten ten. The anchor day are
Speaker 1: called these are anchor days. They're called doomsdays, um they
Speaker 1: change with each year or with leap years. The anchor
Speaker 1: day actually leaps a year, but once you know that day,
Speaker 1: you know it's the same for all of those dates.
Speaker 1: So for one, as I record this, this year's doomsday
Speaker 1: is or anchor day is a Sunday. So that means
Speaker 1: every Doomsday is going to be a Sunday. So I'm
Speaker 1: recording this in July with our next doomsday being on
Speaker 1: August eight, so that means August eight should be a Sunday.
Speaker 1: And if you look at the calendar, you'll see that yes,
Speaker 1: August day is a Sunday. That means that October ten
Speaker 1: should be a Sunday, that December twelve should be a Sunday.
Speaker 1: So the doomsday rule involves a little bit more than
Speaker 1: just this, but not much more. And this means that
Speaker 1: if you learn the doomsday rule and you have a
Speaker 1: general idea of what the anchor day is for each year,
Speaker 1: you can calculate what in what day of the week
Speaker 1: any given date will fall on, including past years. The
Speaker 1: guy who came up with this was a mathematician named
Speaker 1: John Conway, and reportedly he could give you an answer
Speaker 1: in less than two seconds if you gave him a date,
Speaker 1: he could tell you what day of the week it
Speaker 1: was going to fall on in two seconds or less. Sadly,
Speaker 1: he passed away last year at the age of eighty
Speaker 1: two after he contracted COVID nineteen. But that doomsday rule
Speaker 1: is one that I think is super cool. I've seen
Speaker 1: people who can do this where you give them a
Speaker 1: date and they're just able to tell you what day
Speaker 1: of the week that falls on, and you can go
Speaker 1: and check it and sure enough they're right. Well, this
Speaker 1: is one process where you can do that. It's not
Speaker 1: the only one, by the way, there are other algorithms
Speaker 1: that also can help you determine what day of the
Speaker 1: week a specific date will fall on. But the doomsday
Speaker 1: rule is is one that works. And again I don't
Speaker 1: have it, um. I don't have an expertise in this.
Speaker 1: I haven't practiced it at all, so I can't do it.
Speaker 1: If you came up to me and say, hey, Jonathan
Speaker 1: May first, nineteen, what day of the week was that,
Speaker 1: I'd be like, I don't know. Probably really a it's
Speaker 1: probably a fine day. I don't I don't know because
Speaker 1: I haven't done this yet. But I think it's really cool.
Speaker 1: I gets. It illustrates how for certain types of problems
Speaker 1: you can come up with a mathematical approach to solving
Speaker 1: those problems, and it just is applicable for all problems
Speaker 1: that fall into that category. And that's really the elegant
Speaker 1: and cool thing about algorithms. Also the other cool things
Speaker 1: that people are coming up with new ones all the time,
Speaker 1: and they might be trying to refine earlier algorithms to
Speaker 1: make them even more efficient and effective, or they might
Speaker 1: be trying to come up with all new algorithms to
Speaker 1: take advantage of emerging technology stuff like quantum computing. I
Speaker 1: hope you enjoyed that episode. Like I said, it originally
Speaker 1: published last year in two thousand twenty one, and hopefully
Speaker 1: tomorrow I'll be back in shape and I'll be able
Speaker 1: to do another news episode. We'll have to wait and see.
Speaker 1: Like I said, I'm really hoping that this is just
Speaker 1: a stomach bug thing that I'm dealing with and not
Speaker 1: like round two of COVID. I do have a test
Speaker 1: that literally I think just arrived at my door, so
Speaker 1: I will check and make sure, because obviously I want
Speaker 1: to be responsible and safe for all of my fellow
Speaker 1: human beings. Out there. I hope all of you are
Speaker 1: well and staying safe and healthy, and that you're having
Speaker 1: a great summer so far. Uh you know, I plan
Speaker 1: on having a great summer once I feel better. For now,
Speaker 1: I'm just having a kind of grouchy summer because that's
Speaker 1: I mean, that's my go to mood for pretty much
Speaker 1: any situation, but particularly when I'm not feeling well. Anyway,
Speaker 1: take care and I will talk to you again really soon.
Speaker 1: Text Stuff is an I Heart Radio production. For more
Speaker 1: podcasts from my Heart Radio, visit the i Heart Radio app,
Speaker 1: Apple Podcasts, or wherever you listen to your favorite shows.