Algorithms + Data Structures = Programs - Episode 218: Algorithms (by Louridas)

Episode Date: January 24, 2025

In this episode, Conor and Bryce chat about a new algorithm book that Bryce picked up.Link to Episode 218 on WebsiteDiscuss this episode, leave a comment, or ask a question (on GitHub)SocialsADSP: The... Podcast: TwitterConor Hoekstra: Twitter | BlueSky | MastodonBryce Adelstein LelbachShow NotesDate Generated: 2025-01-22Date Released: 2025-01-24Algorithms by Panos LouridasElements of ProgrammingC++98 std::reverseFlood FillIntro Song InfoMiss You by Sarah Jansen https://soundcloud.com/sarahjansenmusicCreative Commons — Attribution 3.0 Unported — CC BY 3.0Free Download / Stream: http://bit.ly/l-miss-youMusic promoted by Audio Library https://youtu.be/iYYxnasvfx8

Transcript
Discussion (0)
Starting point is 00:00:00 What is an algorithm? What would you say an algorithm is? What is an algorithm? It's like a set of operations, a routine procedure for calculating something. Yeah, so that's the definition that they give here. They give it as a way to do things. And it's an interesting definition here where he defines it as an algorithm is like a set of steps that you can follow with pen and paper. Welcome to ADSP The Podcast, episode 218, recorded on January 22nd, 2025. My name is Connor, and today with my co-host Bryce, we chat about a book that he recently purchased in London called Algorithms. You've got fake snow behind you, but there's also, I imagine, real snow.
Starting point is 00:01:05 It is minus 14, feels like minus 21. Let's get that in Fahrenheit for you folks. Now even I know that that's minus 6 Fahrenheit. Yeah, that is rough. That is an extreme cold warning in Toronto.
Starting point is 00:01:25 Yeah. Yeah, it's extreme cold warning in Toronto. Yeah. Yeah, it's pretty cold here. Funny thing. So I think, yeah, so I spent a few years living in Louisiana when I worked at LSU. And I remember one time there was like a frost at LSU. It was like February or something. And there was, you know was going to be frost and maybe some ice. And they shut down the university for like two days because there was a concern that there could be black ice on some of the stairs and that the LSU students wouldn't know
Starting point is 00:01:58 how to handle that. And so, it was just best just to shut down the whole place. And I don't know if they actually got 11 inches, but Louisiana has been hit with like a ton of snow. They have like, I think like eight inches in New Orleans. And New Orleans, folks, New Orleans has eight inches of snow. Like, what is this weird world we live in right now? Oh, man. But I just, I'm thinking about my old boss Hartmut who, he really, you know, one of the main reasons he moved to Louisiana was the weather. Like he doesn't want to be cold. He likes that it's nice and warm there. Maybe it gets a little too warm, but I'm just thinking like the last day, like last day like god that poor guy like i you know
Starting point is 00:02:46 i don't even know if he owns anything other than shorts anymore and uh and it's got to be brutal there thoughts go out to those in louisiana and anywhere warm that is not i mean it's pretty cold for toronto but uh it's not atypical that once or twice a year it drops down this low. So you said it is negative 11 here Celsius, and it feels like, well, it says it feels like that, but I think it feels like negative 14. I think it feels closer to negative 20. Yeah, I mean, I haven't gone outside yet today, but I try to minimize. I'm hoping I won't have to. Yeah.
Starting point is 00:03:33 Yeah, in the last couple of days, trying to stay indoors is a good play. Just go to the gym. Don't run outside these days. Yeah. I don't even have to go far to the gym. It's just I have the Bowflex Max trainer right there. Looks like a Transformers robot or whatever you call those things. It's really good when I'm not lazy. So how have you been?
Starting point is 00:03:59 I've been good. How about you? 2025? 2025. New year. New year. Yeah, I'm good. Been busy at work i've actually well you're gonna you're gonna be shocked the listeners gonna be shocked i have not one but two programming books that are like here that i've been reading this morning one of them is just called i want to say that's programming pearls but i can't actually read it because it's white text on beige um it's this one is just called algorithms this one i i i texted you about this like i got this in november when i was on the way back i want to say it was like a month or two
Starting point is 00:04:39 ago yeah but then this is just um elements programming. Oh, elements of programming. It has a very yellow cover, and then it has silver text on the yellow cover. I'm not sure that I agree with that cover design. But yeah, I've been reading them. And some interesting things. Some interesting things. Share with us the interesting things that have been accumulated from these two books link oh in the show notes folks perfect we don't have affiliate links if you click on them you're i mean eop is for free so yeah not if you want this copy this
Starting point is 00:05:18 ironically speaking of hartman kaiser this this book was given to me by my mentor, my guru, Hartmut Kaiser, for my must have been 20th birthday. It was the first birthday that I was there in Louisiana. And he just came up to my desk and he gave it to me and he said, here, happy birthday. And that is how I acquired my hard copy of Elements of Programming. It wasn't wrapped or anything. It was just here. You need this. is how I acquired my hard copy of Elements of Programming. It wasn't wrapped or anything. It was just here. You need this.
Starting point is 00:05:51 So this is that copy? You made it sound like you picked up both of these books for the last couple of months. No, no, no, this is that copy. I think that it is very hard to get this copy of EOP. I do not think that this has been in print for some long period of time yeah i think that this has not been in print for a while all right so one book recently acquired another book anciently yes yes i think this is also a first edition yes it does appear to be a first edition one of my many randomly valuable uh programming. So I opened up the other book to the exact page that I wanted.
Starting point is 00:06:30 So this book, it's called Algorithms. I got it at, I went to this, we had like an eight-hour layover in London. And so my girlfriend, Ramona, not liking to just spend time in airports waiting. She was like, let's go into the city and do something. And so we went into this little – Was this Heathrow? Yeah, this was Heathrow. We went into this little museum in, I think it was Hyde Park.
Starting point is 00:07:01 Let me go to – let me go find London here on Google Maps. Yeah, it was Hyde Park, and there's this little museum called the Serpentine Gallery. And they had this exhibit on artificial intelligence, of course. They had this music that was composed by various neural nets. It was just like a small exhibit. It took like 15, 20 minutes to go through it. But then they had a bookshop and I had both Ramona and my mother with me. And so, of course, we had to spend as much time in the museum bookshop because they both love a good museum bookshop.
Starting point is 00:07:46 And I saw this book, Algorithms, and I thought, hey, we have a podcast on algorithms. Maybe I should pick this up. And it had on the cover, I don't know if you can see, the algorithm for GCD. And so I thought, OK, maybe this is interesting. But I figured picking this up not at a tech conference or something, I figured that this book was going to be something that was meant for more of a mass audience. And that is in fact the case. I think it's meant to explain to people who maybe don't have as much of a CS background or who aren't programmers what algorithms are. I think it's very structured towards our current age. The chapters are,
Starting point is 00:08:41 chapter one is what is an algorithm, chapter two is graphs, then chapter three is searching, chapter four is sorting, chapter five is page rank, and chapter six is deep learning. So very, very topical. And it's interesting because the first chapter like handles like talks about the idea that we're now in the algorithmic age, that we're past the computer age. Computers are not taken for granted and it's all about the algorithmic age, that we're past the computer age. Computers are not taken for granted and it's all about the algorithm. And it talks about this idea that people are starting to treat the algorithms like they're a higher power. You know, you talk about like, oh, well, the algorithm decided this, like it's some magical thing. And I feel like that does kind of reflect
Starting point is 00:09:20 how some folks view technology these days. But it's interesting because it's both approachable, I think, to anyone, but also dives pretty deep into some pretty advanced topics. And I certainly think you need some background in math to be able to read this book and not be lost. But in the chapter one on what is an algorithm, I came across two interesting things. The first, and this is a quiz for you, I guess, Connor, do you know the origin of the word algorithm? Vaguely, yeah. I'm not going to know the exact origin, but it's from the Middle East.
Starting point is 00:10:05 If I had to guess, we're going to go and say Persian. You are correct. It comes from the name of Muhammad Ibn Musa al-Kawazim. Al-Ashima. Do you know the name of the guy that Algorithm was named after? Yeah, it's a Persian guy. It's a Karazmi or something like that. She said the same thing I said. Yeah, it's a Persian guy. It's a car resume or something. She said the same thing I said.
Starting point is 00:10:25 Yeah, he's a Persian guy. So she didn't know the name either, which means let's go. And my fiance is like a history buff. She listened to, I want to say, all of that history podcast, correct? Yeah, but that doesn't make you a history buff. It does. I also took informal courses. All right.
Starting point is 00:10:44 We'll find you another history question later. Get ready. His name is hard to say. His name is hard to say. She says she does actually know it. Oh, it is. It's hard to say.
Starting point is 00:10:51 I just tried to pronounce it and I'm sure I did it very poorly, so I'm not going to try it again. But anyways, this dude, Al-Khawazimi,
Starting point is 00:11:03 Al-Khawazimi, we're going to go with that. This dude was circa like 780 to 850 Persian scholar. Worked in fields of mathematics, astronomy, geography. The term algebra comes from the Arabic title of his most influential work. And the translation of this title is pretty great, which is the Compendus Book on Calculation by Completion and Balancing. And I just think that's a great book name. And I hope it's as good in the original Arabic as it is in the translation. And his name was Latinized to Algorismos. And then that in combination with the Greek word for number, which is Arithmos, sort of evolved into the term algorithm. But algorithm originally just meant
Starting point is 00:12:06 like doing decimal arithmetic. And it's only in like the last 200 years or so that it's come to mean what the second thing that I found interesting about this chapter is. It's come to mean what an algorithm is. And the second interesting thing is, what is an algorithm? What would you say interesting thing is, what is an algorithm?
Starting point is 00:12:25 What would you say an algorithm is? What is an algorithm? It's like a set of operations, a routine procedure for calculating something. Yeah, so that's the definition that they give here. They give it as a way to do things. And it's an interesting definition here where he defines it as an algorithm is like a set of steps that you can follow with pen and paper. And they repeat that a couple times. And he sort of makes the claim, the author of this book somewhere here, that an algorithm is something that you can carry out ourselves.
Starting point is 00:13:08 And I'm not certain what exactly he means by that or why that's significant. Because I suppose he means something that like you can manually and just that computers can do it faster. I think it makes it's like a layman's olive branch, right? Because if you think of the first algorithms we learned, at least the ones that I consider, it's long division and long multiplication when you're in, I don't know, we'll say grade three, but times may have changed for those that are born after the millennia, the turn of the millennia. They might teach it sooner because that's what happens in the education system. So I guess it depends on where in the world you are.
Starting point is 00:13:58 But I distinctly remember learning, yeah, long form multiplication and long form division. And it's just like a set of operations. You multiply the first digit in the second number with everything in the first, and then you, you know, add a zero for the second line. It's just a set of instructions. And I remember too, being in math club for the like one month that existed at DP Todd secondary and Prince George, shout out to Prince George I remember at one point we learned the algorithm for hand calculating square roots and I thought that was very cool because up until that point up until that 30 minute lunch session or whatever I thought that was like a incalculable thing by hand because they didn't teach it in school like
Starting point is 00:14:44 you just oh you go to your calculator and you hit the square root button. But there was, there is actually like a set of steps where you converge into the, you know, square root of some number. And I thought that was fantastic that this thing that was impenetrable and only a button on a calculator, I could now do by hand and in your head if you so desired as a party trick at some point. So, I mean, I do think it's kind of, do I agree? It's something you can do by hand?
Starting point is 00:15:10 Not really. But I think, I looked up this series. It is the MIT Press Essential Knowledge Series. And there's a bunch of other books with the topics like deep learning, data science, and machine learning, revised and updated edition, cryptography. So I think this is kind of the academic version of your airport books. You know, the Malcolm Gladwell, bite size, catchy titles, usually half of them are self improvement, you know, atomic habits, stuff like that.
Starting point is 00:15:42 This is like your science slash academic versions of those kinds of books that you're going to find, which it's unsurprising that they describe algorithms in this kind of fashion, right? They're not targeting people that work at NVIDIA. They're targeting people that might also, in the same, you know, fell swoop, pick up Atomic Habits.
Starting point is 00:16:02 And there's got to be a little bridge from there to walk over from Atomic Habits to algorithms. I agree. I think that that is the essence of the target of this book. But so then a little later in the chapter, he says a couple of things that I resonate with. He says the only way to truly understand an algorithm is to perform it by hand. We must be able to execute the algorithm in the
Starting point is 00:16:30 same way the computer would execute a program that implements it. And I find this interesting because when I'm implementing an algorithm or coming up with an algorithm, I usually will first write it out by hand and I will first work through some problem by hand. Usually like, you know, in like a smaller problem than what I would actually, you know, solve on a computer. Like, I was recently, the summed area table algorithm that we talked about on previous episodes, or I recently wrote a softmax implementation. And in both cases, I did what I always do, which is I picked some trivial, small problem size, and I sort of worked out on paper and also in Excel. I find myself increasingly using Excel to do this.
Starting point is 00:17:36 I used to just do it in paper and Notepad, but Excel makes it easier to work with these sorts of multidimensional problems where, you know, I wrote out my test problems and then I sort of imagined here's the series of steps that I would need to take to get to the solution. Or in the case of something like Softmax, I can look up online, like it's not like I'm creating some new thing. I have, you know, the code. I see this as the code of like what this does, but I want to understand like how does it actually work and to understand that so that I can explain it to other people, right? Because if I want to use it in a talk, then I need to be able
Starting point is 00:18:17 to explain why are we doing each step of this thing. And so, by going through and me manually doing each step and being able to look at each step, I can sort of develop the intuition for how does this thing work. yourself manually, or maybe you, you write some code and print it out at each stage, but you look at like, how does this work for some small problem? And that's sort of, to me, it's like what he's talking about of being able to execute by hand. Is that, is that what you do when you start playing around with some new problem? I don't, it depends on the complexity of the problem. And I'm also, I am also have the difficulty of just going to wait for my lovely fiance. Finish using the microwave and slamming doors. She needs to eat breakfast though, folks.
Starting point is 00:19:15 Maybe I'll just leave all that in there. I love you, sweetie. I love you. Get that croissant. I hope, I hope we're not microwaving a croissant though. That seems like that's some sort of French food crime. I mean, it's not a fancy croissant, and it is indeed being microwaved. That seems like it's some sort of French food crime.
Starting point is 00:19:35 I don't know. Our listeners in France, let us know. Quebec. The other France. The Quebecois. Yeah. Let us know if we violated some kind of um yeah well you can hear it you can hear it beeping we might as well just wait because she's about to open the uh fun fun fun fun fact
Starting point is 00:19:54 fun fact my dad was visiting us last week and we were talking about family history and my dad's side my dad was adopted um but he mentioned something that I think I'd known, but hadn't remembered, which is that his biological father is a French Canadian, making me one fourth French Canadian, which I would say explains a lot about my personality, my general love for Montreal just many of my haughtiness not your love for Montreal bagels though you are first and foremost a New York bagel no I'm kind of a convert
Starting point is 00:20:35 really wow I posted to social media but we did this Montreal bagel making class when we were up there before we went to Morocco. And it was a lot of fun. And they were very, very good bagels. I ate like four of them.
Starting point is 00:20:50 All right. Well, you heard it here first, folks. Definitely not going to upset anyone on the internet. Former lover of New York bagels, Bryce Adelstein-Lelbeck, has now converted and does think that Montreal bagels are superior. I mean, Montreal in general, just for food is, you know, the best. Like that's why you go to Montreal for the food. It is true.
Starting point is 00:21:10 They do have Felix and Norton cookies. I'll leave it at that, folks. Pink truck by the waterfront. Next time you're there. We went to this restaurant, Candide, and they had this preparation of spinach that was the best spinach i've ever had i don't know what they did to these spinach leaves but i could have literally eat nothing but that spinach for the rest of my life wow and you could be like popeye okay all right so back to anyways back back to algorithms the question was do i jot things out uh by pen and paper and i was saying that i suffer
Starting point is 00:21:49 from the problem of having been so far removed from the first time that i had to understand or visualize a problem my first thought was that uh i definitely did not need to go and implement stood reverse to be convinced that swapping the last and first elements one at a time and incrementing and decrementing two pointers until they converge yeah works like that seems simple enough that I automatically would be like yeah that's how it works but is that actually how I felt because I would also say the same thing about one of my favorite algorithms, flood fill. But I remember the very first time I didn't learn a flood fill. I just organically implemented it in a qualifier for an ICPC collegiate
Starting point is 00:22:40 programming contest. When I was at SFU, there was free pizza. And it had this sort of graph or matrix problem where you had to go from point A to point B. And I didn't know how to do it, but I just thought, I guess if you recursively start at your starting point and then add the number one, and then if you have some queue where you just basically, you know, recursively search the four adjacent elements from each square and you keep a cache to ones you've already visited, that should work. I wasn't convinced that it would work
Starting point is 00:23:13 because it's a recursive solution and kind of hard to wrap your head around the first time you implement or think about it. But then I implemented it, it worked. And I was like, ah, my idea worked. So there's an example of something I wasn't sure worked. But once again, I did not do this by hand and paper. I just implemented the algorithm. Then you look at the, you know, you just output the matrix of numbers at the end of the day that is a zero for where you started and incrementing numbers for the flood fill path. My point being is that sometimes paper and pen helps, but a lot of times I just implement it on the computer. But I feel like that's, I don't know, like a 21st century equivalent of pen and paper. But yeah, I don't know.
Starting point is 00:23:53 I do even today like start off on pen and paper more than you might think. And I think I've done this since the beginning of my career. Sometimes it'll be like on Notepad or in excel like i said but i think i very often will start off um before i even write any code i'll start off just thinking through it um and i think part of that is that i've i've found that if i start coding before i think through it um i i'm more likely to lead myself down the wrong path and then get like tunnel vision but give me a little more background on this flood fill what is the flood fill problem? I mean it's got it's own Wikipedia page I'm sure
Starting point is 00:24:36 if we will link it in the show notes but as soon as you see the animation yeah I'm looking right now it's basically just a recursive exploration of a 2d array or matrix where you have a starting position this actually animation is not great and i believe they call it flood fill because it's the algorithm when you're in windows paint or some equivalent paint program and you hit that fill button and you need to fill a square, it does this algorithm when basically saturating
Starting point is 00:25:10 a space and I guess in that example you're just changing one pixel color to another pixel color and it goes and basically you start at an origin point and then you have either four or eight directions depending on how you're allowed
Starting point is 00:25:26 to traverse if you're allowed to traverse diagonally uh it's eight if you're only allowed to traverse orthogonally it's up down left right and you start at uh it's usually you have a secondary matrix which is the size of your original and you set everything to uh either zero or negative one or something like that then Then you assign your origin point, the value zero, and then you put in a queue all the four orthogonal places that you can visit. And then once you're done putting those in the queue, you're in some kind of while loop. You pop off the queue, the first element,
Starting point is 00:26:01 and then you assign that one plus the previous value. So along with the coordinates of the position that you've stored in the queue the first element and then you assign that one plus the previous value so along with the coordinates of the position that you've stored in the queue you also need to assign the previous value that you were coming from and so then if you're starting at zero the next four spots will all get the value one and you just do that recursively and you have to make sure either with a cache or by just checking when I'm now at the second point and I'm checking the four orthogonal elements that I'm going to visit, you have to make sure that they haven't already been visited. And in certain algorithms, you actually do need to check. And if so, if you found a
Starting point is 00:26:35 shorter path, you might need to assign a minimum value. In the classic case, you don't need to do that because you know that the way that the algorithm works, you're always going to end up visiting elements in the shortest way possible. And then you just do that to completion. So the cache is to avoid having to do it redundantly. Yeah, but the way that I would do it, like I said, if you set everything to negative one, you can always just check, make sure that I'm only exploring elements that currently their value is negative one.
Starting point is 00:27:02 And then as soon as it gets assigned a value that's positive or zero in the case of your origin, you know that you'll never visit it again. Be sure to check these show notes either in your podcast app or at ADSP the podcast.com for links to anything we mentioned in today's episode, as well as a link to a get up discussion where you can leave thoughts, comments and questions. Thanks for listening. We hope you enjoyed and have a great day.

There aren't comments yet for this episode. Click on any sentence in the transcript to leave a comment.