Introducing Greedy

[00:00:03]
>> Bianca: We're moving on, guys, divide and conquer. Recursive, break it up into sub-problems.
>> Bianca: Greedy algorithms.
>> Bianca: Greedy algorithms, where do I wanna start with this? So a greedy algorithm is just like it sounds, it takes the short-sighted,
>> Bianca: Solution. Given a decision, it's going to do the one that looks like the best decision at that time, without considering the big picture.

[00:00:36]
So you can think like a toddler. If you say, hey, give you one Oreo now or two Oreos later, they're probably gonna take the one Oreo now kind of situation. Let's see, usually people teach greedy algorithms like this, but we're not gonna talk about it like that. We're only gonna talk about how greedy algorithms always make the locally optimal choice.

[00:00:59]
And actually, this is kinda the inspiration for this whole series, and this is a MIT computer science class. And this is one of the classes I took just online, the open courseware, to learn data structures and algorithms earlier in my career. And it's very, very academic, and so this is kind of a response to that.

[00:01:23]
It's a less academic version, we're just talking about the practical stuff, we're making estimations, insofar as it matters to you, here and now. Maybe one day you'll become a PhD student, and you'll be writing white papers and algorithms, and that's really cool. But this is a good place to start and build up your base knowledge before you take a course like this, where you have a bunch of mathematical symbols.

[00:01:50]
For something that's, at its core, very simple, which is, given a choice, they're always gonna make the locally optimal one without considering the big picture. So if we have a map like this, and say we are trying to get from city a to city g, and these roads between them have different distances.

[00:02:10]
So we have, between a and c, we have a road of three miles, and a and b, a road of five miles. Those of you who have taken a data structures class before, this may look familiar. This is a weighted graph, but let's just talk about it in terms of it being a map.

[00:02:24]
If we were doing a greedy algorithm, starting at a, we would say, what is the locally optimal solution, assuming that we want it to be the shortest path? We're gonna say three, right, so then we're here. And we're gonna keep making these decisions based on the locally optimal solution, which is gonna be four and then two and then three and then four again.

[00:02:46]
And so we come up with this path which, at the end of the day, is gonna be 16 miles or 16 units, whatever it is. It's a solution, but is it the best solution? No, we can see with our eyes that this one's a better solution, 12 miles instead of 16.

[00:03:07]
However, so this is one thing that I'm like, hm, greedy algorithms kind of suck, and this is one of the reasons. However, there is a time and a place for greedy algorithms, and that's when your data set is so big that you can't think of all the different scenarios because it's just computationally too much.

[00:03:27]
And so it's better to have a solution than no solution at all. And so that's when a greedy algorithm is good. And we'll talk a lot about greedy algorithms when we get to graph theory on part four of this four-part series.
>> Bianca: So we'll get more into that, but let's jump into a greedy prompt.