I run a course on Data Structures and Algorithms.
The first week of the course introduces students to the ideas of complexity and big O notation, and I wasn’t happy with the existing worksheets used in the practical classes. The questions needed to be better at getting across the idea of time complexity to undergraduates with a wide range of abilities.
I had a vague idea of what I wanted to do: I wanted some algorithms that the students could follow by physically acting them out in the practical session, and then afterwards we could discuss the complexity of the algorithms. I hoped that the “learning by doing” approach would help them to understand and remember the complexity ideas better (i.e. what educational researchers would call experiential learning).
I looked around the web for inspiration, and I came across this web page which presents some course notes for “CS367 Introduction to Data Structures” at the University of Wisconsin (instructor Sally Peterson, web notes hosted by Rebecca Hasti). It had this algorithm suggestion:
“Consider the following three algorithms for determining whether anyone in the room has the same birthday as you.
Algorithm 1: You say your birthday, and ask whether anyone in the room has the same birthday. If anyone does have the same birthday, they answer yes.
Algorithm 2: You tell the first person your birthday, and ask if they have the same birthday; if they say no, you tell the second person your birthday and ask whether they have the same birthday; etc, for each person in the room.
Algorithm 3: You only ask questions of person 1, who only asks questions of person 2, who only asks questions of person 3, etc. You tell person 1 your birthday, and ask if they have the same
birthday; if they say no, you ask them to find out about person 2. Person 1 asks person 2 and tells you the answer. If it is no, you ask person 1 to find out about person 3. Person 1 asks person 2 to find out about person 3, etc.”
This was a nice idea for an algorithm to act out, but it didn’t quite suit my purposes. I wanted to discuss the complexities for all three versions. Once the students have identified their tutor’s birthday from the first run of the algorithm, it seems a bit pointless to run another version of the algorithm to find out something you already know. In addition, this would require people to reveal their birthdays, a fairly personal piece of information often used for identity checks (or students would have temporarily have to pretend to have a different birthday). Rather than do birthdays, I had a different idea: the photo identification algorithm:
The purpose of this exercise is to look at the time complexities of three different algorithms to solve the same problem. The problem is to identify whether any student in the room knows who is in the photo, and if so, who is it?
- Algorithm 1
- Tutor asks first student, then asks second student, then asks third student etc.
- Algorithm 2
- Tutor asks first student. If the identity is not known, the tutor passes the photo to the first student and asks them to ask the second student. The information is passed back to the tutor. If not known, the tutor asks the first student to ask the second student to ask the third student… etc.
- Algorithm 3
- The tutor holds up a photo. All students in the room immediately either speak the name of the person in the photo (if identified) or shake their head otherwise.
These algorithms don’t require personal information and you can run them as many times as you have photos printed out to show them. I chose photos of celebrities that were very well-known in some circles, but not others, as I didn’t want the algorithms to terminate too soon. I chose Benazir Bhutto (twice Prime Minister of Pakistan):
and Stephen Colbert (US comedian ubiquitous in the US but mostly unknown in the UK):
For the third photo, I had the idea of creating a comedy moment, where the practical tutor shows the photo to the students and it is a photo of the practical tutor in some kind of comic style, like in comedy glasses and moustache. I thought this might make it fun and more memorable for the students. So I sent round an email to the department:
Does anyone have a comedy glasses/noses/moustache kind of thing that they could bring in and I could borrow for a few hours?
(Don’t ask. The short answer is that it’s for a practical class to help explain Big O notation to [...] students.)
In the end I went round the practical tutors who were going to be giving the practical sessions, taking photos of them in a silly jimmy hat (scottish tartan beret with red pom pom and ginger fake wig). All of them looked suitably amusing, except mine! Mine looked too sensible, not nearly comedic enough:
So I donned a fake moustache instead. No I am not posting a picture of that.
Things I learnt as a result:
- The students (and tutors) did indeed seem to find the practical class more memorable, and fun too.
- In a practical room, you can hear the peals of laughter from the neighbouring lab.
- The student grapevine circulates rumours of comedy tutors extremely quickly. Attendance the following week was up!
- When you send round an email asking for comedy glasses and moustache, all of a sudden you have an instant conversation topic with people you meet in the corridors, who will all want to know what on earth is going on in your practical classes, and can they watch?
- I have a lot of colleagues who are good sports and not afraid to make fools of themselves for the cause of explaining algorithms concepts.
- If one of your colleagues looks unexpectedly hilarious in such a getup then he or she may not be too happy if you fall about laughing for half an hour…
- … but it will make your day!
- My departmental colleagues are very kind and if you laugh for half an hour straight they will offer to fetch you some oxygen.
- Everyone will suddenly develop a keen interest in being emailed photos of your colleagues wearing silly hats and/or moustaches.
- Giving your colleagues your solemn assurance that you are NOT sending electronic copies of the photos to anyone is very important.
