Another episode of the podcast is live here…
Transcript
hello. And welcome to how to teach computer science. The podcast. This is episode eight. What is an algorithm, I’ll be answering that question and many more with the help of today’s special guest.
Dave: Craig’s always like, Dave, say less, say less.
Alan: Yeah, get to the point. Good grief. You’re a teacher, man. Explain things concisely.
Dave: The thing is, I don’t know about you, but things fire off in my head. So I’m talking about one thing, but the multi core processor in my head is already processing something else, and I can’t help myself. I have to then talk about the next thing that’s popped in my head.
Alan: Yeah
My name’s Alan Harrison, and I wrote the books how to teach computer science and how to learn computer science available in online bookstores. Please do go and buy my books or leave a review. If you’ve already bought them. Details at HTTCS dot online. That’s the initials of how to teach computer science. HTTCS dot online. Oh, so I had a bit of trouble earlier. I’ve got a new laptop and the music app wouldn’t stop playing someone like you. Then I realized it was A Dell.
How does the CPU get to work? On an instruction cycle. And talking of work? When I was teaching an English teacher, asked me to round up his 28 glue sticks. So I said 30. Never ask a computing teacher for help. After I recovered, he said, can you pop to the stationery store and get me two rolls of sellotape? And if they’ve got glue sticks, get me two more. They had glue sticks. So of course I returned with four rolls of sellotape. Hey, I don’t make the rules. I just follow algorithms. My wife called and said “while you’re at the shops, get some milk and well, I’m banned from the co-op now.
We’re talking algorithms today and who better to talk to than the co-author of essential algorithms and data structures, a vital resource for teaching or learning a level computer science. Let’s hear what happened when I met Dave Hilliard.
Alan: I’m delighted to invite onto the podcast today a chap that a lot of you will be familiar with as one half of Craig and Dave. It is, in fact, the Dave half. Welcome to the podcast, Dave Hilliard.
How are you?
Dave: I’m good, thanks very much Alan. Thank you for inviting me, it’s a, it’s a real privilege to be a part of this amazing set of pods that you’re producing, I’m listening avidly to them all, I love it.
Alan: Oh good you’re the one, yeah, you’re the listener. Um, I’m keeping an eye on the stats. I think I’ve had like 600 listeners across the five pods now, which is nice. It’s quite a niche podcast really, isn’t it? Computer science teachers, there aren’t that many of us and there’s fewer every week.
Dave: It very much is a little bit niche. You’re absolutely right. And it’s a shame really, because you and I are both so passionate about computer science.
and the teaching and learning of computer science. And it just feels like the audience is so small which is a shame. If we were doing silly dances, then we’d have a, a huge audience.
Alan: Possibly. There’s always the Hungarian dancer videos on YouTube to teach sorting and searching or cert, certing and sorting, as I often say in the classroom.
Dave: The quicksort, certainly, and maybe we’ll get on to that a little bit later because, yeah, the Hungarian dance to teach the quicksort, there’s, there’s some controversy there.
Alan: Ah, wait, is it not right? Ah, quicksort, don’t get me started on quicksort because The question is,
Dave: is it a
Alan: quicksort,
Dave: you see? people say, oh, that Hungarian dance, that’s not a quicksort.
Alan: Oh, right. I tend to put it on to introduce the topic and I show bubble sort and I don’t bother with all the others. It’s just, oh, sir, put the Hungarian dancers on again. Yeah, I’ll just do the bubble sort one. If anyone’s listening and haven’t got a clue what we’re talking about, just search Hungarian dancers bubble sort or something on YouTube and you’ll find what we’re talking about.
So. That’s the topic for today really is the algorithms topic of the GCSE. So typical content would be computational thinking and then choosing an algorithm for a purpose and interpreting algorithms and then the standard algorithms that we’re talking about, bubble sort and linear search and binary search and stuff like that.
So one of my favorite topics to teach. I don’t know about you, Dave, do you enjoy teaching this topic?
Dave: I love it. I have to be honest. It’s one of the topics, that I find the students don’t look forward to. They think it’s difficult, algorithms, but I absolutely love it. I, for me, algorithms is like, it’s like art. When I look at an algorithm, it’s like other people, looking at a piece of art and you know you go to a gallery and people stare at this picture on the wall and they’re talking about the emotions and feelings that that piece of artwork is giving them and the messages that it’s sending to the audience and I’m just looking at some daubs of paint, to be honest, and thinking, I’m not really sure what, what in all this.
I can admire the artistry, but I don’t get that emotional connection. Whereas when I see algorithms, as sad as it sounds, I get that feeling. So I get it. I look at the code, I look at the approach and I I get a real appreciation for the efficiency or the inefficiency and those kinds of things.
Alan: Yeah. No, I’m I’m probably with you on that and if that makes us strange, so be it. We are algorithm geeks, that’s for certain. So, the art of designing an algorithm then, we normally call that computational thinking I’m obsessed with abstraction at the moment. how do we go about getting these concepts across to the learners then? How do we teach abstraction?
Dave: Yeah I like to have a bit of fun in my classroom and thinking about abstraction itself I get my students to make paper airplanes. I say to them today’s lesson is all about making paper airplanes. Come and grab some scrap paper. And I want you to make the best possible paper aeroplane that you can, and then we’re going to fly them across the classroom, and of course it’s absolute chaos, and the students absolutely love it, and I say we’ll get a bit more structure in here, let’s take our paper aeroplanes down to the main hall, and let’s fly them, and let’s see how how far we can fly them and whoever can fly the furthest with their aeroplane, they win.
And the students absolutely love it. And we then break it down and we say, what was important? Did, did you know, did I tell you that what was important is that your paper aeroplane had to travel the furthest? I didn’t tell you that initially, you might have assumed that, but maybe what I was looking for was the best design, the most unique paper aeroplane, the one with the most folds in it, for example.
And so we talk about what’s important. What was important with that paper airplane? And if it is a question of trying to get it to fly the furthest, then what are the characteristics of that paper airplane that make it do that? And is it important if I draw, for example, a cockpit and a pilot on the front?
Is it important if I draw something on the wings to make it look pretty. And so we use paper airplanes as a way of understanding what’s important and what’s not important. And because the students had so much fun with that, when we then say, okay, let’s look at this from an algorithm’s perspective, they’re in tune.
They get it. And they’re happy to learn something a bit deeper because they had some fun initially.
Alan: Yeah, yeah we, we use that phrase, don’t we? It’s ignoring the, unnecessary detail and focusing on the important detail. And I always, I remember when I first started to teach computer science and I picked up someone else’s resources and we had a photo of a cat, and a cartoon of a cat, and there you go, that’s abstraction. And I remember being just as bewildered as the children at that explanation, because we then went on, probably the next lesson, to write programs, and nobody really explained to me, so I couldn’t explain to the pupils, what the cartoon cat had to do with writing a program.
Dave: And, and that’s, and you have to start somewhere, don’t you? Yeah. And I, and I think for example, with that cat example, the other thing that I do with students is play catchphrase, right? And say, okay I’m going to put a picture up on the board a little bit at a time, and you’ve got to try and guess what that picture is and you can do it for example, in a number of ways with a picture that’s fully zoomed in. So the pixels are huge and then gradually kind of zoom it, zoom it out. So they start to see the picture. They enjoy that. Or you could have a picture of a cartoon cat, for example. And you’ve taken off the whiskers and you’ve taken off the ears and you gradually put them in one by one and you know you play catchphrase with the with the students they try and guess what that thing is so they understand about details and they understand what’s important and what isn’t but I know what you’re saying then there’s a conceptual leap between that And what it means in computer science, and of course it’s got lots of different meanings in computer science, but if we just pick one, it might be, for example, when you write a program and you save a file, you don’t know where that file is being saved on the computer.
the storage medium. You don’t know, for example, on a solid state drive, whereabouts in the chips was it saved? And it doesn’t matter. And if you don’t have a solid state drive and you have a hard drive instead, how did it move the drive arm to the place where it needed to be in order to write the data onto the platters in the right place?
It doesn’t matter, you didn’t need to know.
Alan: No, I totally get it and I think what I’m explaining there is I didn’t quite understand abstraction when I started to teach and so it’s important that teachers do. One of the examples I give is, is maps of course. We do maps, but to talk about different levels of abstraction you could, put up Google Earth on the board and go, there’s, there’s the earth with Europe there at the top. Is that a map of where we live? And the students will go, yes, that’s a map of where we live. And so you say to them show me how to get to the library then. And you can’t until you zoom in. So you go down a layer of abstraction but how do we get from that to, creating a program or a data structure to solve your problem. How do we make that leap?
Dave: It’s not straightforward, is it? But one example that I use is the game of snakes and ladders. They’ve all played snakes and ladders, as a child, and you could even play a bit of snakes and ladders to start with in the class if you want to have a bit of fun. I think, you’re hearing here that the message is have a bit of fun. And what you do is you put snakes and ladders on the board and you can have as many counters as you like.
In snakes and ladders, that’s the beauty of it because it doesn’t matter how many players there are in snakes and ladders. Lovely little bit of abstraction there, but what you can then do is say okay, so we’ve got we’ve got a board and we’ve got 100 squares 10 by 10 and And we’re going to put some ladders on there.
We’re going to put some snakes on there. You’re going to have loads of questions about does it matter how many squares there are? Does it matter how many ladders there are? Does it matter how many snakes there are? Does it matter how big the snakes and ladders are? And you can talk about the effect of changing those variables, if you like, on what it is you’re doing.
You haven’t gone anywhere near a program at this stage. And then you can say, okay, let’s think about moving the counters. This is where we get a bit deeper. Because if you’ve got a 10 by 10 grid, then when you get to square 10, you have to go up one and then start going back in the opposite direction. So those of you that know snakes and ladders, hopefully everybody, you start at the square zero in the bottom left, and then you travel sort of nine squares to the To the right.
Then you go up a square and then you travel nine squares to the left and you keep zigzagging up and down. And what I say to the students is, so what data structure could this be? And we start thinking about the relationship between that and a table of numbers and, oh, it looks a lot like a 2D array, doesn’t it?
A lot like a 2D array. I was like, yes, it does, but watch this because programming it with a 2D array is more complicated than it needs to be. What if. We actually unpacked that square into one long line, because at the end of the day, all you’ve got are squares from 0 to 100. So instead of seeing them as 10 by 10, why don’t you see them as 1 by 100?
Now what you’ve got is a 1D array. And that is significantly easier to program with. So I think you have to show the students through examples that they understand, have a little bit of fun, and then unpack those examples to explain to them how something that looks quite difficult could be made easier.
Alan: Absolutely. That’s a good example, and I’ll use that if I need to teach that again. Yeah, so it looks on the face of it like a 2D array. And yeah, what’s important about it is the numbers 1 to 100, and you travel from 1 towards 100, and it doesn’t matter that sort of it’s bent around.
Dave: You take a step further with that, Alan, and you say, OK how do we represent the ladders then? How can we put snakes and ladders onto this 1D array? And you say because you’re using the indexes to represent the square you’re on from 0 to 99, then what you do is you use the elements or the data of that index to say what it points to. For example, they all have zero, which means all the squares do nothing.
And then you might decide that square 47 takes you to square 2 because it’s a snake. Okay, so you store in element 47 the number 2. So what it tells you is where you’re going and then you do the same thing for the ladders and you can say to the students, so what’s the difference then between a snake and a ladder?
And they conclude there is no difference because ultimately what you’re doing is just storing a number of where one square takes you to another square and I say You see how beautiful this is when you take away the concept of a snake and a ladder and it just becomes a number. That’s abstraction.
Alan: Yeah, absolutely.
And then what you build on top of that is the algorithm that processes it and the main thing it needs to do is let’s say you roll a dice, so it needs to generate a random dice roll from one to six and move you, and then it needs to read the content of the cell it’s landed on. And then process that and it might have nothing in it, in which case you stay there or you read the number that you then have to move to, which if it’s lower than the current number is obviously a snake back on our board game.
And if it’s higher and then it was a ladder. And so you can play it with just text and you can say, oh, you’ve gone back to. Blah, blah, blah, because you went down a snake. So the program could determine whether that number is lower than the current index and say you’ve gone down a snake, or if that number is higher than the current index, it could say you’ve gone up a ladder and you’ve got a text version of snakes and ladders in barely any code, really.
Dave: Absolutely, absolutely, and that’s the secret right there, because Snakes and Ladders looks on the surface like a difficult program to create for, a GCSE student, for example, but in reality, and I’m talking about creating it from scratch, and they find that really daunting, but in reality, when you break it down with them and you go through those layers of abstraction that you’ve described, what you conclude is you have One array, which is the player’s positions.
On the board, you have another array, which is the board itself, and that’s it. The rest of it is just if statements, yeah. If you happen to be on square a hundred, you’ve won. And so the program is tiny in reality. Mm-Hmm. . And if you then code that with the students, and this is the thing that I, I’ve learned is if you code that with the students and you show them the thinking process as you go through, then they start to realize that the skill here was breaking the problem down. The skill here was understanding that that looks like an array. So let’s. Use an array. So really the art here is teaching the students what those fundamental
building blocks are and what they can do.
What is An array. What can it do? And then suddenly things become a lot easier.
Alan: Absolutely. So I, I made a a text adventure program, it’s still on my Repl. it if you go to Mr. A Harrison on Repl. it. And kids around the world stumble upon my text adventure and play it and send me messages and go, hey, I won. But it’s like, it’s a text adventure with about seven rooms, that’s pretty much it. But I wrote it to demonstrate this principle of data abstraction because the rooms are basically in a 2D array.
And separate from the gameplay. And this is important, I think, when you’re designing a program. If you take the snakes and ladders example a bit further, my text adventure game has basically got a list of lists in Python and Each row is a room and it’s just a list of a description of the room, things that are in the room and where you can move to from the room.
And each row is a room. And so I’ve got kids, in year 10 going, all right, and taking my text adventure and adding rooms to it and then wanting to add features like being able to fight is a common one. And so it’s that. Principle of abstraction. Abstracting away the data and then writing an algorithm that matches the data and that’s , basically it. Then you’ve got it cracked.
You make it sound so easy, Alan. How can it be, you know?
So, uh, lots of people cleverer than us have done this. And you know what I’m getting onto. One thing I tell my kids is that von Neumann, he of the architecture was the guy invented merge sort ’cause he needed to crunch a lot of numbers when he was calculating well how to build a nuclear weapon unfortunately. How do you get across to kids that these standard algorithms are important and, and, and where did they come from and why do we need to know them, first of all?
Dave: Yeah, that’s a challenge, uh, so just bring it back to their everyday experience, right? And say to them okay, when you’ve got list of tracks of music that you want to listen to and you want to put them into artist order, for example, how is a computer going to do that? If you’ve got a playlist of music and it to give you the next track, but although you’ve got random selected, you don’t want the chance of hearing the same track again.
So you don’t really want it to be random. How are you going to sort the list of songs that are available so that it puts them in an order that appears random, but you can’t get the same song again until you’ve listened to all the others, if you saw what I mean.
So I think firstly showing the students examples of where these things are actually required in real life helps to cement why it’s important. Otherwise it’s too abstract.
Now that we know why we want it, let’s all be songs, right? So what I want you to do is I want you to write down on a piece of paper the name of a song that you like. Alright. One I wouldn’t have heard of, because I, obviously I’m old and my, my music knowledge is uh, you know, stuck in history. So we have a bit of fun.
We have a bit of a laugh about my age and then we say right, okay. Write down the name of a song on a piece of paper, now and we do this in my classroom actually, but if your classroom is not very big, you might have to do it in the hall and say right, okay, I want you to come up and I want you to hold your piece of paper in front of you and you’ve just come up in a random order and I want to sort now these songs into alphabetical order and some students will have written the name of the same song and it doesn’t matter because that gives you a teaching point about sorting data that is the same.
But anyway, so you say we’re going to do this, okay. Let’s do it! And you just get them to do it. You haven’t taught them anything about algorithms. You just say, let’s sort these into order and just watch them do it. And uh, you know, eventually they’ll get there, but it’s a little bit slow. And you say to them right, what was your method?
What were you doing there? Oh, I don’t know. I was just looking at the name of somebody else’s piece of paper and deciding whether I was before them or after them, and so I was putting myself in the right position and looking at somebody else, and we didn’t really do it particularly methodically, but we got there in the right, good, OK.
So firstly, it would be better if this was a little bit more efficient and there was some logic and we were all following the same logic. That would help. The next thing that would help would be if we took some of the good ideas you had in there, like you compared your number to somebody else’s, that’s a good idea.
How can we decide which number you should compare your number to if we’re going to have a little bit more logic? Can you just break that down with them? And eventually you might arrive at an insertion sort or a bubble sort, but you don’t necessarily have to have that preconceived idea as long as you make sure that you focus on an algorithm that’s in the specification and don’t just do a different one and then you can play it out with them and say let’s put a little bit more logic in this, a little bit more logic in this.
And as the teacher, yeah. You’re gradually getting them to that bubble sort or their insertion sort, whichever was most likely the one that they were trying to describe. And they do it and they move it and then you do the algorithm again and you do it again and you say look how efficient it is when we’re all following the same instructions and the same logic and we’re moving just two people at a time.
This is working brilliantly. This, by the way, is called a bubble sort. Okay. So now you know how it works. Let’s get back down to our chairs. Now it’s taken you a whole lesson to do that, but it’s okay. You had some fun and they understand the reasons why. Then you can take the next level and you can say right, now what we’re going to do is I’m going to put some numbers on the board.
And you’re going to come up one by one. I’m going to give you the board pen one by one, and you’re going to come up and you’re going to show me what happens with those sets of numbers just one step at a time. So here’s the board pen, off you go. What are you going to do? I’m going to compare those two numbers.
Good. What are you going to do with them? Oh that one’s less than that one. So what do you need to do? I need to swap them. Good, swap them. Pass the pen to the next person. Come up, do it. Everybody’s watching, everybody’s involved. And then when someone gets stuck, so they’re a bit embarrassed, they’ve got the pen in the hand, they’re at the whiteboard, they can’t quite remember what’s happening next.
The rest of the class are telling them, I’m doing nothing. I’ve just sat back at this point. And the rest of the class say, Oh, you need to swap those two numbers. And they get over the slight embarrassment and they do it. And the more they watch and because they don’t want to be embarrassed, they are watching.
So that when they get to their turn, They know exactly what they’re doing because they don’t want that peer pressure. So I’m using a bit of psychology there. Once you’ve done that, do you know what? It’s easy to take the step of here’s a worksheet. Do that question.
Alan: And what I take from that is obviously they’re having fun in your classroom, so they want to be there, which is always handy, but you are, you’re using almost a semantic wave explanation there, which is, starting with an algorithm, going down into Low semantic gravity, which is the easy bit of, moving around the classroom and, and sorting yourself and then repacking it into what the concept really is. This was all about algorithms. It was about the bubble sort algorithm. But the bit in the middle. It’s fun and memorable and you can, I find when I do stuff like that, it’s not just yeah, I might have invested a whole lesson in that activity, but I’ll refer back to it for the next six weeks and I’ll go, do you remember when we did this?
And do you remember when you did that? And they will remember because it was a memorable exercise.
Dave: I think the worst thing that you can do is just stick a PowerPoint on the board and say, today we’re learning the bubble sort. This is how it works. Here’s some numbers. Now you compare the first two numbers. If this one’s less than this one, then swap them over. The students have just switched off. They’re never going to learn algorithms like that.
Alan: Yeah, absolutely. , So you need a Hungarian dancer video or you get them up doing the Hungarian dance. So go what do I do? I will get playing cards out to teach merge sort and things and it’s quite handy this because if I have just done a test on paper and I’ve got all the test papers in and they’re in random order and it’s handy for me if they’re in alphabetical order when I mark them because then I can just transfer the scores onto my mark sheet.
So I get the kids to sort the pile of test papers they’ve just handed in you. And I get the stopwatch out and go how quickly can you sort my test papers today? And then they’re like, alright, what if we split them up into different piles and and I go, yeah, merge sort that will do, you know,
Dave: Absolutely. So many other things you can spin off from that. ’cause you can say I’ve put the papers into two, and I want to sort that pile and that pile. And you might not be doing a merge sort. You might be doing two independent bubble sorts, for example, but you can say, is that still quicker?
And you can have that whole conversation about, multi core processors and concurrency and, what were the overheads of doing that? We’ve got one pile sorted and we’ve got another pile sorted, but they’re not sorted into one pile. Now, what are we going to do? Other ways of making that more efficient and loads of things.
Alan: Funny you should say, splitting into two piles and then each pile sorted maybe with an insertion sort. You’ve just described the built in sorting algorithm that’s in the Python implementation that we all use. It’s called TimSort after the developer, Tim somebody, I’ve forgotten his name, but it will break down an array into sub lists and insertionsort them and then merge sort them together. It’s a hybrid and a lot of Commercial sorting algorithms are hybrids these days
Dave: they are, and of course you can have that conversation about why would we want to do that, and this is A level, but you’re getting into efficiency and you’re talking about efficiency is also determined by the size of your data set, because guess what? If you only want to sort 10 items, fill your boots with a bubble sort.
Alan: Absolutely.
Dave: Because a quicksort will not be more efficient for you, so it’s about the size of the data set.
Alan: And about the nature of it, how sorted is it, and is it sorted upside down, for instance, and some algorithms are terrible at that. If it’s nearly sorted, a bubble sort is quite quick, it doesn’t have to do very much, but if it’s upside down, a bubble sort is terrible.
Dave: Absolutely, and even at GCSE you could have discussions about efficiency just with a bubble sort in the ways that you’ve described and even at a code level you can say what if you code the bubble sort with two for loops instead of a while loop and a for loop?
What would be the impact of that? And I would probably only do that with my most able students, the ones that, had a love of algorithms and they were really keen to learn and were going to go on to A level. I wouldn’t do it with everybody, but you can do that. You can go there. Even with simple algorithms, you can say what would happen if
Alan: Yeah the thing is, last summer OCR did ask a question about the nature of the loops in an insertion sort, didn’t they?
And the question was, I think, I should know this because I marked it for OCR, Why is the inner loop a while loop in an insertion sort? And. And that was, that did, let’s say did stump a lot of candidates and that was a tricky one because I think it, I don’t think OCR had asked a question that deep about sorting algorithms for some years.
Dave: No, it catches people out because in the specifications obviously it just says searching and sorting algorithms, bubble sort, insertion sort, and so you teach the algorithms, but. You don’t think about what’s the depth I need to teach us about, the implications of changing this and changing that.
So it can catch you out very easily. Another nice little activity is to just give them the code and say this is. The code for the algorithm that we’ve been having a bit of fun with. But we’re going to see how efficient it really is. So here’s a line of code that’s going to create an array of a million random numbers.
Okay, we’ll do that. I’ll give you that code. And then What I want us to do is I put a little counter variable in there. So every time it has to check something, it’s going to add one to a counter. So let’s just put that in then let’s run the program and actually see how many checks it made.
And they run the program and it made several thousand checks. Brilliant. Run it again. Several thousand checks, but they’ll notice that the might be different because as you say the nature of the data sets and if it was a random number or we can then sort the random numbers which you can do very easily in Python in one command.
So they can see the effect on the changing data set on the algorithm without actually having to do anything other than insert a single line of code. And I get mine to then for example, plot results on a chart in Excel. So I say here’s the code for the bubble sort. Here’s the code for the quick sort.
Again, this is A level. What I want you to do is create a data set of, of. Random numbers or ordered numbers, whatever, and then I want you to plot the efficiency on a chart for me, and so you conclude, you can conclude which is more efficient just by running the algorithms, and they really enjoy that.
Alan: Yeah, I’ve done that before. Yeah, so you you basically you’re wrapping the call to bubble sort or whatever in another loop and passing to it different sized arrays. Maybe a growing sized array from 10 to however many you feel your computer can deal with. If you’re running it locally, you’re alright. I’ve done this on Repl.
it Before and then I get kicked off, don’t I? Because I’ve used all my cycles for the free free account on repl. it. So yeah, you can if you’ve got a class that you think are capable of grasping that, then you can get them to, really measure the efficiency. Of algorithms and compare them. And I take it
Dave: Alan, I take it to the extremes as well, because I just love having fun with this stuff.
And I so I say to my students so we’ve studied the serious ones, right? If you call a bubble sort serious, but we’ve argued why it could be, right? Let me show you something really crazy. And I showed them the BOGO sort and the BOZO sort and I’m like, check this out guys, and you’ve got to be careful with that because the trouble with having fun is that sometimes the students latch onto and remember the bits that were not important.
Coming back to abstraction, they remember the things that are not important because they were funny. So you’ve got to be a bit careful with that. Yeah, with the right class it really works.
Alan: I was talking to Andy Colley a couple of weeks ago, and he likes to show his students the most ridiculous user interface competition every year. And these things, even though they’re bonkers, and obviously they’re designed by crazy geeks with a geeky sense of humor, rather like us, they do demonstrate some of the principles that we need to talk about. What’s the best way to understand efficiency? We’re probably writing the least efficient. code you could possibly write to demonstrate how bad it could be.
Dave: I say to my A level students as a bit of work, for outside the classroom that senior leaders like them to engage with, I say You need to contribute to my ministry of silly algorithms.
Yes.
So I want you to create a silly algorithm. I’m not going to define for you what silly really means. You need to deliver a silly algorithm. That’s good fun.
Alan: Absolutely. Well, What I haven’t done, Dave, and it’s only fair seeing as you’re giving me your time for free. I don’t, we, we have agreed that this is free, haven’t we?
Um, um, I haven’t asked you, what’s new in the land of Craig and Dave these days, Dave?
Dave: What’s new in the land of Craig and Dave? So we’ve got a video series on YouTube. From David Morgan, the lesson hacker.
Alan: Oh yes, loving them.
Dave: Yeah, so every week he’s taking a current affair in computing and trying to present it in five minutes in a fun and engaging way for young people. And then in the video description I’m creating, and I stole this idea from you Alan, I’m creating fertile questions in the video description so that teachers can use them to have discussions with their class. about the current affair in computing, but related to the specification. So that’s good, that’s happening.
Alan: Can I just say at that point, can I just give a hat tip to William Lau, who put Fertile Questions in his book five, six, seven years ago, and also Mark Enser, who wrote a blog for TES on it. That’s where I got it from, it wasn’t my idea, but thank you for picking that up.
Dave: Yeah, and SmartRevise just goes from strength to strength. There’ll be loads of new features coming out for that this year. So we’re spread thinly. We’ve got lots of other things that we would like to do.
But thank you for inviting me onto your podcast. I think the final thing I would say is that your book is great. How to teach computer science, I think, is excellent for teachers. How to learn computer science, I think, is essential reading for all students, and my recommendation would be get a class set, and I’m not just saying this because you’re the author, I genuinely mean it. Get a class set of these books, hand them out, that is your background reading.
Alan: That’s very kind of you to say.
Dave: If at A level you have to do scholarship work, you know, this work outside of the lessons, I’ll tell you what you should do. You should get the students to read a chapter at a certain period of time in the year and get them to present to the class something about that chapter.
And at a very basic level, it could just be a bullet point summary. At a more advanced level, it could be looking into the most recent bits of research or development in that area of study and anything in between really, but use that book as a way of engaging in the subject beyond the specification in a meaningful way.
Alan: No, that’s great. Thanks for the the support and listeners probably don’t know if they haven’t got the book that you did help a lot with that, Dave. Thank you. The, the how to learn book and thanks for basically proofreading it and writing a foreword for it because it was very kind of you. So yeah the other thing I wanted to pick up is You said you’ve listened to the previous podcasts. I just wondered what your reaction was to the story that I revealed to Harry and Anna last week. I can’t, I don’t think I’ve told you this, but I did get asked in the classroom, when we did that unscripted video together a couple of years ago, , and , my class at the time were very, Excited about this, about me doing a collab with Craig and Dave, as they called it.
Um, And they asked me questions about you. And one of the questions was, are Craig and Dave married, And, and of course I nodded along and went, yes, I think they are. And, and that caused a lot of consternation. Did you hear that last week?
Dave: I did. And and when you said the word collab in a kind of Slightly awkward way as I just did then.
Alan: I’m down with the kids.
Dave: I know you are. I noticed Harry’s little snigger at that point and I thought, yeah, that says everything to me. But yeah, people used to think that we were just the same person because all they heard was our voices on the YouTube videos. And actually on a video Craig’s voice and my voice sounded quite similar And so the students were convinced that we were just one person for a long period of time then of course once we revealed our faces, the rumour mill then went into, Oh, they must be partners. They must be together. Uh, No. Craig’s married to someone called Sam and I’m married to someone called Carol.
Alan: Okay. Well, I’m glad we cleared that up. Um, Good stuff. . Smart revise you mentioned. I’ve used it for ages it just keeps getting better. And you know it’s quite affordable. I wouldn’t teach without it. I do sound like an advert, but I couldn’t. I couldn’t teach GCSE and A level computer science without it these days, so go and check that out. That’s all the plugs for one day, I think.
Dave: I think so enough of that.
Alan: Enough, so it’s been lovely to talk to you. I’m just looking at our list here.
Oh, misconceptions. So just briefly then. while we’re on algorithms and computational thinking and so on, what misconceptions, do you see happening?
Dave: Yeah, I think one of the biggest ones for me, and it seems to catch teachers out as well, is the idea that when you’ve got an array, that the first index is always either the X or the Y when you look at a table of data. So is the first index the column or is it the row?
And it doesn’t matter. As long as you are consistent. It doesn’t matter whether it’s X comma Y or Y comma x, but it seems to catch everybody out I that the first one must be the row, or the first one must be the column.
Alan: I think it comes from Python learning, Python, which doesn’t really have arrays and populating a list of lists in Python. In the top of your code necessarily means you do it one way, not the other. And so you do students equals open square bracket. Then you open the second square bracket and do Dave comma computer science or whatever. Close the square bracket and so your students will be in rows in that list of lists in Python.
And so the first index would be a row I do try and fix this one so I will take that code and just order it differently so the student names are all across the top row and the data is on the next row and so on because there’s no reason why you wouldn’t do it that way.
Dave: The other misconception, coming back to algorithms, is the misconception that, for example, a binary search must always be better than a linear search. No, because if the item you’re looking for is the first item, in the data structure, then a linear search will, in that case, always outperform the binary search.
So that’s a misconception. And then leading on from that, the misconception that a linear search has to start from index zero. It could start in the opposite direction. And in fact, there is a version of the linear search that actually looks from both directions at the same time. There’s a misconception in computer science that there is a way of doing things.
Alan: Yeah.
Dave: And there isn’t. There are multiple ways of doing the same thing. It’s just some are better than others and some are better than others in different situations and it gets confusing.
Alan: So a standard algorithm is really a broad Concept, it’s a, it’s more like a family of algorithms that follow a certain pattern.
And the other thing that people ask me all the time is, when you do a binary search and you find the midpoint, do you have to go up or down if there’s an even number of. And I say do whatever, either way, but to code it, normally you’re going to use floor division, aren’t you? And go down, but it doesn’t actually matter because you’re going to find the item.
The only difference might be one or more fewer comparisons in one direction than the other, but that will all even out when you’ve got a million items to search that doesn’t actually matter.
Dave: Yeah, the other misconception is that in maths they might get taught, for example, the Hoare method of a quicksort at A level, and then in your class you teach them the Hungarian method. And they’re different and they say quicksort and you say no it’s a variation of a quicksort because you’ve also got the Lomuto method. And those are just three methods and you know what actually current research into quicksorts that are using multiple pivots and not just one. There are actually hundreds of quicksort algorithms.
And as soon as teachers and students realize that it’s eye opening that there is no right answer. And I think the thing that fascinates me the most at the moment is that the research in this area hasn’t stopped just because we’ve got these standard algorithms and we’re teaching bubble sorts and insertion sorts and quicksorts. There’s an assumption. And a misconception that the research has stopped. No, it hasn’t. And actually in quantum computing there’s active research right now in turning some of these searching algorithms into even more efficient algorithms than we’ve got at the moment.
Alan: Absolutely. If you are teaching A level, there are multiple Quicksort implementations. Learn one and make sure you can explain it really well and then tell your pupils that they might encounter other ones, but the basic principle of choosing a pivot and moving things either side of the pivot and then repeating that, Usually recursively, that’s a quicksort, but it can be implemented many different ways.
Dave: So you’ve done exam marking Alan, perhaps you can clear something up for us as well. Because there are so many different methods that you could take with some of these algorithms, the mark scheme will show a method, perhaps the most Obvious method that the exam board would perhaps like you to teach to avoid any confusion.
But what if a student actually gives their answer using a different but same family of algorithms? So for example, the mark scheme’s got a horror approach to a quicksort, but you see a Lamutu version as an examiner and you recognize that as a valid quicksort. What do you do?
Alan: I think so. First of all, I’ve only marked GCSE papers, but I’ve had the OCR training, yes, a valid implementation that answers the question will be given the marks. I think there’s quite a lot of leeway there. So if it solves the problem, that’s basically what we’re looking for.
Dave: And that’s the other misconception in teaching at the moment, that the mark scheme is the answer.
Alan: Yeah, yeah, it’s a tricky one. So I do support a lot of teachers, in my other jobs, I work as a PDL, a professional development lead for the NCCE, and I deliver training and so on.
And I do encounter this, and so if, The teachers listening to this, please try to understand the concepts that you’re teaching rather than teach for the surface level of understanding of passing the exam. That is, in that sentence, is like a whole lifetime of learning, but it is really important that, it’s why I wrote the books I wanted to get these, Conceptual understandings of computer science across to teachers and pupils rather than just, oh, trying to pass exams.
So, Yeah well, that was, that was brilliant. Thank you Dave for coming on and yeah, I knew, I knew we’d have a good chat about algorithms because you did, you wrote the book on it, talking of books, the, the, algorithms book available from craiganddave. org as well. So, um, So that was really good. So, uh, have you got any plans for Easter?
Dave: Um, no, if I’m 100 percent honest with you, I’m not sure I’ve thought that far ahead. Thinking ahead, oh
Alan: dear! Thinking ahead!
Dave: I’ve got to be honest, OK, because the community out there probably now thinking how Dave lives such a sad life. He’s there looking at algorithms as if they’re art and he’s got nothing planned for Easter. I did. in the February half term go to Jamaica, we had our sort of Easter break in, February.
Alan: Nice. . Well, we are tomorrow going to London to see Moulin Rouge, the musical.
Dave: The West end’s phenomenal, isn’t it? An amazing experience.
Alan: Yeah. Haven’t seen the musical yet. Love the film. Yeah. So looking forward to that. There’s another abstraction. How do you produce a film on stage? You know, how do you produce a book or a play on stage? Because you’ve got to abstract everything down to what will fit into the area of the stage. . This is me. All I could ever think of these days is abstraction. I was talking about Lord of the Rings with other Lord of the Rings fans recently, and we agreed that it was about the best series of movies that could be made from that book, but it was always going to fall desperately short because, I read Lord of the Rings and it probably took me, let’s say 30 hours. How can you make even nine hours of film out of what takes you 30 hours to read and even a minute’s reading could be an hour’s worth of movie .
Dave: The director has to decide what’s important and what’s not important at the end of the day. Which is a form of abstraction. There’s another example you
Alan: Um, Well, we got onto abstraction in movies and everything then, , just as I was winding up. So I think now I do have to wind up and it’s been lovely to talk to you, Dave. And no doubt, I’ll ask you back on to talk about something else in the future but thank you very much for coming on.
Dave: Thank you. It’s, uh, it’s been an honour. Thanks, Alan.
Alan: You’re welcome.
Dave: All right then, mate. Anyway, enjoy. Thanks, Alan. Bye. Cheers, mate. Bye.
That was another epic. I’m off now to drink 32 pints of milk. And read about the latest advances in computing. Because I’m just as much of a geek as Dave. Quantum computing scares me though. Apparently you can store information, not as binary digits or bits, but in quantum bits called cubits. What do I know about cubits? Very little.
How do you make a computing teacher happy? Give him arrays. Thanks to Andy Colley for that one, I did think he was going to say, don’t get his backup. but no it’s give him arrays. We don’t need much, just a bit more cache. Quick reminder that I don’t have any sponsors only you lovely people. So please. Go to my website, HTTCS to online and find out how to donate a little bit of cash. Buy me a coffee for three quid. That’d be very kind review my books on Amazon. You can use the discount code. HTTCS pod that’s HTTCSPOD on the website for the book, Johncattbookshop.com. That’s the publisher’s website, JohnCattBookshop.com. And you will get 20% off everything. Don’t forget there’s books by me, but also Mary Myatt, Tom Sherrington, Adam Boxer. And many, many more brilliant people. I will see you next week on the pod.
And until then have a good one.
How to Teach Computer Science 