Dave and Virg's Adventures in Pittsburgh: May 2009

This spring I was 1 of 7 instructors teaching our introductory programming CS1 course. None of the students are CS majors. The course is taken by about two-thirds of all CMU undergraduates. Nearly all are there because the course is required by their department. On the plus side, this means that students have low expectations, and there's a real opportunity to get them excited about programming. The vast majority of the students have never seen even the simplest program before (although, sadly, many think they have programming experience because they've used HTML).

I lost all my fall CAs (course assistants), so I hired 7 students from my fall course to help me teach in the spring. I wanted to be actively involved in the classroom all 4 days of the week, instead of leaving recitations to my CAs. And with a full teaching load this term, after teaching 9 classes a week in the fall, I was now teaching 16 in the spring, which cut into my preparation time. (I also sat in on a colleague's CS0 course 4 days a week.) On a typical week, I introduced new material on a Monday and had students work on the week's programming assignment during class on Wednesday, Thursday, and Friday, interrupting them only to give a 20-minute quiz each Wednesday. Assignments were due Monday nights, so I spent Monday evenings helping students in the lab.

I created most of my materials from scratch, so this was an exhausting but more rewarding semester. And with so much class time, and creating a new assignment, quiz, and lecture every week, it was almost as intense as teaching high school.

The Plan

In shaping the course, I set out to teach as little Java as possible, covering only the essentials and postponing any syntactic shortcuts. This way, students could master the fundamental concepts and focus on how to use them effectively, instead of getting lost in punctuation. I also tried to plan each week around some compelling programming project. There's no point in introducing a new construct unless it lets students build something new and meaningful. Plus, if students are going to have to program for several hours a week, they ought to have something cool to show for their efforts.

One of the great debates in CS education is when to teach object-oriented programming. I wasn't exposed to the object paradigm until my sophomore year of college, when I had already been programming for a long time. The order that I learned makes a lot of sense to me--starting with functions and data, and then learning how an object-oriented language lets you bundle functions and data together. But, since Java is, unfortunately, the language du jour for intro programming courses, and Java is deeply object-oriented, most Java teachers have their students using objects early in the course.

The U. Washington lecturers took a different approach. They wanted to use Java in their first few CS courses, but to keep objects out of CS1. So, they have their students declare everything as "static," essentially bypassing Java's object-oriented mechanism. This is what I decided to do in my course, and I'm very pleased with how it turned out. I'll definitely teach Java this way again, and I'm increasingly finding myself opposed to object-oriented programming in an introductory course.

In the past, I've begun my introductory Java courses using a rich object-oriented problem-solving framework called Karel J. Robot, in which students program a virtual robot to solve simple tasks. This means that students are writing interesting graphical programs on day 1, instead of writing boring programs to print "Hello World!", calculate sales tax, etc. Karel comes with a beautiful mini curriculum, that's designed so that, after each topic, students are almost begging to learn the next topic. For example, the robot can initially only move forward one step, or turn 90 degrees to the left. Students quickly discover they can make the robot turn right by turning left 3 times. But after a day of doing this, students can't wait to learn how to define the word "right" to mean "turn left 3 times." Unfortunately, Karel J. Robot is object-oriented, but luckily it was easy to build my own non-object-oriented framework based on it.

A screenshot of my robot framework. Yes, I spent hours trying to draw a robot before settling on this simple but endearing design, which I think is part Wall-E and part Fluffy.

Another beautiful thing about the Karel curriculum, is that it presents the language just a little at a time. Each time a new construct is introduced, the grammar is explicitly presented to students (much like MIT's extinct 6.001 SICP course). I did my best to stick with this plan, even testing students on both grammar and evaluation rules. Next semester I plan to do even more of this.

Finally, on the recommendation of one of my course assistants, I had my students use a development environment called DrJava. I like it because (a) you don't need to deal with all the nonsense of making projects/workspaces/etc., and (b) you can execute instructions, one at a time, in the interactions pane at the bottom of the screen.

Weeks 1 - 3: Traditional Robots

From the beginning of my course, students could immediately open my framework in DrJava, and start typing instructions like:

Robot.load("maze.txt");
Robot.move();
Robot.turnLeft();
Robot.makeDark();
Robot.makeLight();

After another day, they were defining their own instructions, like:

public static void turnRight()
{
Robot.turnLeft();
Robot.turnLeft();
Robot.turnLeft();
}

Students used my robot framework to write methods in week 1, use ifs in week 2, and implement loops in week 3.

Week 4: Towers of Hanoi

Transitioning from the Karel curriculum to the rest of Java, especially variables, is always pretty rocky. So, this time I developed some problems where we could use variables and integers in my robot framework, culminating in one of the most original assignments in the course. Without recursion, data structures, or even parameters, we implemented the classic "Towers of Hanoi."

The 3 pedestals on the right are the "Towers of Hanoi." The first pedestal is used for scratch work, and the second stores the list of work left to do, which in this case is to "move 7 girders from tower 1 to tower 2."

Unfortunately, only those students who made it through the extra credit got to see their robot solve the "Towers of Hanoi." The final program took about 5 minutes to run, but was absolutely mesmerizing to watch.

Week 5: Bait and Switch

The next week I used the robot to introduce parameters, and I think the assignment was very clever. First, students created a library called RoboPlot, with functions instructing the robot to set the color (light/dark) at a particular row and column, etc. Next, the students implemented 1-dimensional cellular automata, using only the functions from RoboPlot (and no references to the robot). This ran excruciatingly slow. Then, students downloaded a file I created called FastPlot, which had all the same function names as RoboPlot, but ran much faster. Slowly, it began to dawn on students that there wasn't a robot inside FastPlot, and by the time they realized, they'd already been programming without the robot for several exercises.

a cellular automata rule, which generates a seemingly random pattern

Week 6: Classes Are Hard. OOPs.

And that was the end of the robot and procedural programming. At this point, I introduced object-oriented programming, having the students create their own objects. This was not a good idea. There's so much syntax involved in creating and using objects, that it would definitely have been better if we spent a week or two using objects before we tried creating our own. Next time.

Week 7: Media Computation

When we did start using objects, I revealed that my framework could do a lot more than control a robot. I had the students use my framework objects to manipulate images, inspired by the media computation curriculum created at Georgia Tech. The students really came alive when we started manipulating photos, and they were full of ideas. Here are some examples of the effects we implemented in the assignment:

Week 8: Bejeweled

Halfway into the course, I flew down to the SIGCSE conference in Chattanooga, where I had a good time catching up with old friends and getting to know some of my CMU colleagues better. I spent the rest of my spring break putting together a programming assignment based on the classic (but copyrighted) game of Bejeweled.

Not only does my framework let you set the color of a cell, but you can also place little images in it. And you can call a method to determine if a cell has been clicked, or a key has been pressed (without having to implement a listener). It was a big win to use the same graphical user interface framework for many assignments, so that I didn't have to introduce a new set of objects each time.

I introduced this material in my favorite lecture of the semester. I started by placing a picture of a duck in an empty cell. In one section, a girl in the back row said, "Oh, I just love ducks!" to which I responded wryly, "Then you're going to love this lesson..." I showed students how to make the program print "Quack" when you click on the duck. Then I asked innocently, what else could the program do when you click on a duck? "Kill it!" students answered with enthusiasm, and we went on to program a simplified version of the classic Nintendo Duck Hunt game. We called ours "Ducky Slayer."

Week 9: Spelling Out Everything

Next we learned about strings, and implemented the same word games I used in my AP class. The experience really drove home the difference between teaching groups of 15 high school kids, where all coding is done in the classroom with me, vs. teaching 95 college kids who didn't want to take a programming course and who do most of their work at night, when I can't help them. As a high school teacher, I could cut up an assignment into fewer, larger parts, and if someone was stuck, I was there to give a hint. With 95 students working in their dorms, you can't be there to give a hint, or clarify a vague instruction. So, rather than leave lots of beginning programming students stuck and frustrated, I erred on the side of giving away too much in my assignments, and with this particular one, I probably didn't give away enough. With all the explanations and examples, the assignment was still many times longer than the one I had used with my AP students.

Week 10: Tetris

For the next week, I substantially modified my classic Tetris assignment. It was a big hit with the students, but I'm not sure how effective it was in teaching arrays.

Week 11: Golf Solitaire

Next I had to teach collections of objects, so I wanted to make a card game with lots of collections of cards. I like implementing solitaire games, since you can play them without a friend and without writing an AI player. I've used the classic Klondike solitaire game in my AP class before, and it's a pretty big assignment, because there are so many rules. I read through the rules of a bunch of other solitaire games, before settling on one called Golf Solitaire, which I later found to be quite addictive.

We used my framework again for this assignment, this time with pictures of cards.

CMU's CS1 is probably the only Java course in the world that insists on having students use fixed-size arrays to implement resizable lists of objects. (The rest of the world uses Java's built-in ArrayList object, which does everything you'd ever want to do with arrays, and with more consistent syntax.)

Our Pile object represented a collection of cards.

Week 12: Chars

The AP course brilliantly omitted Java's char data type, since anything you would ever want to do with characters can be done using strings. But our CS1 course insists on teaching students to use chars. Furthermore, since characters are stored internally as integers (e.g. 'A' is 65), Java lets directly perform integer arithmetic on characters. And unfortunately, our final exam tests this.

So, I had students write code to encrypt messages using a Vigenère cipher. At the end of the assignment, I told them I had used the word "char" itself to encrypt a message, and I showed them the encrypted message. Many of my students successfully decrypted it, to find it asked them to use another word to decrypt another message. When that message was decrypted, it told students they could win a prize if they were the first in their section to send me an email with a word meaning "to burn or scorch by incomplete combustion." So my inbox was full of emails with subject line "char," and a couple with subject line "singe," etc. And the prize? Magnetic chars for your fridge. Students got a real kick out of my clever ending to an otherwise dumb assignment.

Week 13: The Kevin Bacon Game

For the final assignment, I wanted to do something that involved searching through large amounts of data. I downloaded movie data from IMDB, and spent countless hours paring down hundreds of megs to the the 100 or 1000 most popular actors and movies. In the end, the assignment provided tons of practice with collections, but was a bit too long, and even with my step-by-step instructions for implementing a breadth-first search at the end of the assignment, it proved to be too abstract for most students.

one of many diagrams and examples I added to the assignment, as it became increasingly clear that students didn't understand the algorithm

Reflections

The common final exam given to students of all 7 instructors, reflects the bias of a more traditional curriculum, in which program execution begins from a "main" method (not from DrJava's interaction pane), and output is printed text (not graphics). So, in my last lesson of the term, I amused myself by teaching students to write the "Hello World!" program that would traditionally be introduced on day 1.

I gave surveys at the end of the class. Here's what I learned:

82% thought the class was well paced (although I felt it moved too fast).
87% liked having so much time to work in class.
Lectures sometimes went too quickly (a consequence of giving students time to work).
Weekly quizzes were a necessary evil, and preferable to occasional exams.
Favorite assignments were Tetris (89%), Media Computation (81%), Bejeweled (74%), and the first 3 weeks of robot tasks (63%).
Homework took about 4.5 hours per week (outside of class).
Help was very available, and my course assistants were great!
34% plan to take a follow-on CS course.

That still left the question of whether I had adequately prepared my students for the final. Thankfully, my final exam average of 80.1% was quite respectable (especially with my low drop rate). Incidentally, there was a large range of final exam averages across instructors--a recurring phenomenon that isn't well understood.

Before I taught the course, a few instructors claimed that the entire course content could be taught with weeks to spare, and several instructors found at least some time to teach more advanced programming concepts, like inheritance, sorting, etc. I decided I would spend my extra time teaching big CS ideas, like: How do computers work? How does the Internet work? How is data represented by ones and zeroes?

Wisely, though, I decided to front-load my course with programming skills, and ultimately found there was no time leftover for the big ideas. Although the content can be "taught" in just 20 lectures, with 35 class days to spare, students can only learn the material so fast. And even with my pared down curriculum, I still felt I was pushing them to learn faster than they were comfortable.

What could we cut from the course to make room for big ideas? The language-specific stuff: characters, arrays (instead of ArrayLists), object-oriented programming, and declared types. Without all that, we might find a month to explore the big ideas. I'm pushing to make the course objectives flexible enough to let us move in this direction.

I'm teaching the course again next semester, but in the new Gates building (where my new office will be). We'll only have computers in the classroom 1 day a week instead of 4, so I need to change my course substantially. Also, we're now limited to half as much help from course assistants. All this means that students will have much less time to work in class, and much less help outside. It also means programming assignments will need to be a little shorter, giving students less practice. And with less support and greater anonymity, students are bound to cheat more. In the end, there's no question that students will be less prepared for the final.