Skip to content

Teaching Computer Science

July 15, 2012

So here’s something fun: In addition to being a high-school math teacher during the school year, I moonlight as a computer science teacher at this summer camp. I just finished teaching one section of their Fundamentals of Computer Science course, which I describe as my entire undergraduate career in computer science condensed into 3 weeks. We covered number systems, logic gates & circuit design, graph theory, sorting algorithms & a conceptual understanding of asymptotic analysis, operating system algorithms & basic computer architecture, computer security & a few modern cryptosystem, and computer programming – I teach Python and Javascript with HTML5 so we can do graphics with the canvas element. I made a webpage for the course here

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.

Update 7/15: Michael Pershan quickly enlightened me about several other computer science / programming bloggers (and I’m incredibly glad that he did). You can find them in this comment.

Programming Resources: Here’s a zip file of all the handouts I give, the programs I assign, and a somewhat sporadic outline for how I introduce various programming topics: Click here! My favorite thing about Python is that you can jump right in and start making meaningful programs right away – you don’t have any ‘Before you can do anything, you need to do all these other things that you don’t understand’ lectures (stupid public static void main(String[] args)). I also love embedding interesting mathematical problems into my assignments (like the Collatz Conjecture, the Locker Problem, or the Palindromic Number Conjecture). This year was also the most successful year I’ve had with getting students to use what I call ‘bookkeeping’ or ‘state’ variables – extra variables used to organize the internal workings of your program. These are vital when working with strings since they’re immutable in Python and Javascript. In the past, it’s been a challenge to get the students to accept that you’re allowed to add extra things to your code, even if it’s not obvious in the program description that you need it. I think what changed is I made a bigger deal about these extra variables right at the beginning and gave them a specific name – “bookkeeper’ rather than ‘this extra variable we have’. From then on, whenever my students needed an extra variable to keep track of things, they consistently named them ‘bk’ or ‘bookkeeper’.

Also, when I transitioned from Python to Javascript, I gave the students a cut-up version of this handout – on the left side are statements in Python and on the right are statements in Javascript. I had them find the two statements that matched, tape them to an index card, then write on the index card what exactly the piece of code was doing (‘generating a random number between 1 and 6’, ‘printing the first and last letter of a string’). Seriously – matching/categorizing activities are awesome. In a half-hour, my kids were ready to dive into the dramatically different syntax of Javascript and they had created a nice little reference pack to use if they got stuck. I love compare/contrast discussions, and this one was a great one.

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.

Advertisements

From → Curriculum

7 Comments
  1. Awesome post, lots of resources for me to dig into. I teach an elective in Java at my school, though I’m not planning on blogging/working on my CS curriculum for another few weeks this summer.

    Here are some other bloggers who teach CS:
    Math Teacher Mambo
    Helene Martin
    Another CS teacher.
    Broken Airplane

    You mentioned Dan Anderson. Shawn Cornally teaches CS, along with everything else.

  2. I’m so happy to have found your blog!

    I’ve done what I call the “autonomous bubble sort”:

    Participants line up. They are to sort themselves by birthday. The rules are, you can only ask a person next to you your birthday. And after you do so, if the two of you are out of order, you may switch positions. Everybody in the line does this simultaneously.

    If you’ve already explored other sorting algorithms, (a) it will astound them how efficient this is, and (b) you can demonstrate the common-birthday problem 🙂 (c) it can prompt a good discussion of how this is different from the computers we usually code for.

  3. I envy you! I’d love to teach a computer science camp. If you’re teaching younger learners, you might want to check out Computer Science Unplugged: http://csunplugged.org/ . Get them outside and get their bodies moving!

  4. Hey there, I think your blog might be having
    browser compatibility issues. When I look at your blog
    in Ie, it looks fine but when opening in Internet Explorer, it has some overlapping.
    I just wanted to give you a quick heads up! Other then that, excellent
    blog!

Trackbacks & Pingbacks

  1. Mathblogging.org Weekly Picks « Mathblogging.org — the Blog

Collaborate

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: