00:00:00,500 --> 00:00:02,050 DAVID MALAN: --that's OK. So, surely then there are these bugs, and that's fine, and so think back-- Coming up is perhaps the algorithm that CS50 is known for, which I certainly inherited from some professors pass, but you pick up this here phone -- DOUG LLOYD: Yeah, you don't see those very often anymore. DAVID MALAN: They're really hard to find. In fact, we've had to circulate calls for donations online of phone books in towns that actually still print these things. DOUG LLOYD: And we've actually gotten several, so thank you to all the people who sustained the shipping of just pure paper to us. DAVID MALAN: I know, they're not even cheap to ship because they're so heavy. And the bigger the better too for the demonstration. But anyhow, if you just take a phone book, the goal here is to demonstrate through dividing and conquering, this perhaps the most intuitive of algorithms, but an algorithm that you might not necessarily call an algorithm because it really is just common sense to most people. And so what we're trying to do in this case I would argue is, capture again, some familiarity that students already have whether with binary on the one hand or now with algorithms on the other hand, and start to formalize their understanding of that so that they can leverage it in new contexts. DOUG LLOYD: And in this phone book we're looking for Mike Smith, who was actually the professor of CS50 when I took CS50 just before you took over in 2007, but the choice of Mike Smith is actually a strategic one. There's a reason behind-- of course it's that, but there's also a strategic reason behind why we choose to search for him in particular. DAVID MALAN: Well, S is just kind of nice, so if you search by last name it means I can do one flip to the right, do another flip to the right, claim to have gone slightly too far, such that I end up in the T section for instance, so that I can then double back to look for Smith. You don't want to pick like M, because then algorithm's over pretty fast. DOUG LLOYD: Right, it works right away. So it gives you a chance to explore all of the different-- although students have not yet encountered this term, conditional branches of the algorithm. DAVID MALAN: Yeah, exactly. But there's a lead up of course, we don't dive right into the intuition, instead I propose verbally, well, why don't I just look for Mike one page at a time. And it's a good question to ask, especially to make sure students are indeed following along, because invariably someone might think or say, no, that's incorrect. And here we have an opportunity to introduce the distinction right from the get go between correctness, or design, or quality of design, not to mention other axis along which you might evaluate some problem solving. But it's indeed correct to go one page at a time, but it's not correct of course to go two at a time because almost always there's one student who realizes, wait a minute, what if Mike is between two pages as you're going by two at a time. So that's a good opportunity too for a branch like, well, if you hit the page right after Smith double back one page. DOUG LLOYD: Right, you have a certain-- Yeah, you can handle that. DAVID MALAN: That's the best part too. Everyone's always so-- DOUG LLOYD: Oh, the dramatic toss? DAVID MALAN: --so impressed when I tear that phone book down that spine. 00:02:42,844 --> 00:02:44,760 DOUG LLOYD: I think actually a couple of years ago there was a piece of tape that ended up on the-- DAVID MALAN: Yeah, there have been some failure. It's unclear if that was malicious that year not, someone reinforced the phone book before I went on-- DOUG LLOYD: That's not fair. DAVID MALAN: --to lecture. I have struggled once in a while, but all the better, it makes for a funny demo. DOUG LLOYD: Do you practice before hand? DAVID MALAN: No we don't have enough phone books to practice. So it's usually fun to toss half the phone book at someone in the audience gently if they'd like to keep it. DOUG LLOYD: Yeah, that's a fun souvenir. DAVID MALAN: But this is the key point at the end, and you don't want to flip again, and again, and again, it will quickly become tedious. You want to end up with a theoretically one single page on which Mike either is or is not. At which point the algorithm ends. But there's an opportunity next, and you see the glimpse of it here on the screen, to also through this demo introduce pseudocode code because it's pretty intuitive to flip to the middle, keep flipping half, in half, in half, and tearing, but now start to slap some structure on that I think is a helpful exercise to bridge these worlds of just talking through intuitive problems, to formalizing some actual formative code. DOUG LLOYD: Right, expressing it in a language that students are familiar with, and even adopting, as we'll soon see, conventions of indentation to suggest what they might see later on down the road with C other programming languages that use indentation to demarcate different blocks of code, as we do there on line four. DAVID MALAN: And even here, it's a simple thing, but it's an opportunity to reinforce what we just talked about previously in so far as it's natural to start counting from zero, when you're using binary since all of your bits are zeros by perhaps initially, and so this is a nice subtle way of reinforcing that. Unfortunately it's a bit misleading too, because most every text editor these days just naturally starts numbering lines at 1, so I have sort of misgivings there, but I feel it's easier to just start from zero here rather than suddenly change tack just minutes after that particular demo. And this was actually a judgment call too, so for years have we used in step 7 and step 10 this go back to syntax, which is effectively go to in a lot of languages, but I'm OK with that because I think if you're numbering the lines it's super readable here, and even though we don't necessarily introduce formally the go to statement, and we don't encourage it in class, it's a very natural way of expressing a loop. DOUG LLOYD: Yeah, if you tried to use English to structure, I think those lines of code, lines 3 to 11 there is a loop, I think it would be a bit more convoluted. DAVID MALAN: Indeed.