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