Teaching Computer Science
Anyway – I want to share some of the things I did for anyone who teaches any sort of computer science-esque course and so I can remember these things when I (hopefully) return next year. To my knowledge, there isn’t much of a presence of computer science resources in the blogotwittersphere – the only other blogger I know of who does a programming course is Dan Anderson (but I could be, and probably am, wrong). So, if you’re potentially teaching a computer science/programming course in the future, maybe this post can give you some ideas. And I get to look back at this a year from now, which will be fun.
Graph Theory Activity: This was super fun: when we started graph theory, I took my class (15 students) outside with a big ball of yarn which I made by wrapping yarn around a tennis ball. I told half the class to toss the yarn to each other in a circle, but you had to hold onto a portion of the yarn when you threw it. And just like that, they were making a graph. After everyone had the yarn and a few people had it at least twice, I told them to stop, then directed the other half of the class to represent this situation on a big piece of poster board. I told them to use circles to represent the people and lines to represent the yarn – the rest was up to them. It was awesome! One group drew all the vertices, then each person in the group picked a vertex to be responsible for and draw all of the connecting edges – another group kept track of where the yarn was being thrown and traced the path of the yarn to generate the graph. Graph vocabulary sprung up naturally – ‘adjacent’, ‘incident’, ‘neighbor’, ‘vertex’, ‘edge’, ‘traverse’.
We made a few graphs and brought them back to the classroom and used these as the basis for most of our graph theory discussion. A lot of graph theory theorems became obvious too – for example, in an undirected graph, the total degree of the graph has to be even and is twice the number of edges. A lot of graph theory ideas became easier to introduce – directed graphs represent which person threw to which other person; self-loops represent someone throwing it to themselves; an isolated vertex represents someone who never received the ball; planar graphs represent graphs where you can position yourself so the yarn never crosses over itself (which is helpful for avoiding knots). I had the students add weights to the edges in the following way: if two people have an edge connecting them, they find the number of letters in their first names, add them together, then make that the edge weight (so if Sam and Jenny were neighbors, the edge between them would have a weight of 3 + 5 = 8). Then we talked about cool problems that you can use graph theory to solve – my goal was to get them to add ‘turn the problem into a graph’ as one of their problem-solving strategies, but it’s hard to measure how successful I was since I didn’t have much time to follow-up on this.
Also, the Park School in Baltimore developed their own curriculum which includes a whole section on Graph Theory. The problems in that section were invaluable – I used several of them with my students while teaching and it worked wonderfully.
Note for next year: Be conscious of the process of ‘undoing’ the yarn activity – the first time I did it this year, the yarn crumpled into a giant knot that we never fully undid – we had to cut the yarn and work with a smaller ball. Luckily, the problem of untying knots has a little bit of a connection to graph theory, so it turned into a discussion of how we could use a graph to undo this knot.
Sorting Algorithm Activity: The last thing I want to remember for next year is how I introduced sorting algorithms. This was the only lesson I tested on a group of friends before teaching it this year and I’m glad I did because it’s (1) complex, and (2) awesome.
The Setup: Each student has a deck of cards and a partner. One person is designated the dealer – they are the only ones allowed to touch the deck of cards. The other person is designated the sorter – they are the person who must tell the dealer what to do in order to sort the cards in ascending order. Each round, the dealer deals out 10 cards and the sorter must tell the dealer how to sort them. The only command the sorter can give is to swap two cards – ie: “Swap the king and the 2”, or “Swap the first and last card”. The dealer must keep track of the number of swaps (s)he makes.
First Round: Sort the deck of cards in ascending order. Each pair switches roles at least once. Once everyone’s become familiar with the roles, ask the class: What do you think is the least number of possible swaps? What would that deck look like? What about the most possible swaps? What would that deck look like?
Second Round: The sorter may no longer identify the cards by their values. Instead, they must use the cards position where the ‘first’ position is position 0 and the last position is position 9. The sorter will tend to say things like ‘Swap 0 and 5’. After a few rounds like this, tell students to keep track of what they’re doing – do they have a strategy? What is it?
Third Round: Here’s where things get complicated/awesome: The sorter may not look at the cards. Only the dealer can see the deck. However, the sorter may now ask the dealer yes or no questions, but they must also keep track of the questions they ask. The sorter can also write down information/draw pictures/whatever they want to help them keep track of the cards. Before starting this round, let them play one more round looking at the deck so they can get a strategy in mind, then tell the sorter to face the opposite direction and go for it.
What to expect: Some may start with questions about specific cards (ie: ‘Is there a king on the board?’), but then realize these questions are inefficient. They’ll then start to ask comparison questions (ie: ‘Is card 0 less than card 1?’). However, they will get tricked up by asking ‘less than’ instead of ‘less than or equal to’ (which means they’ll get confused by [1, 1, 1, 2, 2, …]) and you will have to tell their dealer not to say anything. The number of questions will be far greater than the number of swaps (which makes sense, since the number of swaps grows linearly while the number of comparisons grows quadratically). Many will try to find the minimum card and move it to the beginning (or vice-versa w/maximum card). Some will describe a ‘brute-force’ method of comparing adjacent cards and swapping them until they end up in the right spot (which, depending on their implementation, is either BubbleSort of InsertionSort).
Once a few groups have finished or have at least developed a working strategy, tell the class to stop and the sorter can look at their cards. Discuss if the picture they had in their mind matched what was actually on the deck. Tell the class about the ‘less than’ versus ‘less than or equal to’ optimization. Ask for strategies and write them on the board. Ask how many swaps and questions people had gotten to – write those on the board.
Possible Fourth Round: I skipped this round when I did this activity, but the next extension of this is that the sorter is not allowed to ask ‘Is the deck sorted?’ – in other words, sorter has to say confidently ‘The deck is sorted now’.
Next Steps: Give handouts of psuedocode for BubbleSort, SelectionSort, and InsertionSort. Each pair works together and implements those sorts, then regroup and compare the sorts to the strategies we listed on the board – try to map the strategies to some of the standard sorting algorithms (ie: find the minimum and swap with spot 0 -> SelectionSort). What is the least number of questions you could need? What would that deck look like? What is the most number of questions you would need? What would that deck look like? Really cool observation: If you can see the deck, the configuration of the worst-case deck is different than if you can’t see the deck. The former is of the form [2, 3, 4, 5, 6, 7, 8, 9, 10, 1], while the latter is [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. After that, we talked about asymptotic analysis (which I called algorithmic analysis) and how to look for the worst-case possibilities.
So… that was an awesome activity. One of those moments where, as a product of the activity and discussion, the students came up with pretty much everything we were going to talk about. I just had to facilitate and give them names.