Pretty sneaky, Sis

I've always lamented the fact that we don't have the time or structure to really teach our kids to program.

In their early classes, they learn syntax, algorithms, and  some ways of storing data and while they  will probably work on some larger projects as they study CS, kids seem to be mostly left on their own in terms of how to take a project from problem or idea to completion.

This frequently leads to poorly designed projects that are harder for the kids to write, debug, and modify. They end up with huge functions/methods no overall plan or design and everything's pretty much a mess

To try to address this, and having finished  most of the A.P. curriculum and not wanting to diverge from the other teachers, I figured we'd develop a class project before I gave the class time for their final projects.

I'm not a huge game person, but since they decompose well, we decided on writing connect 4 - a game that can be described as tic-tac-toe but with four in a row, on a larger board, and WITH GRAVITY!!!!!!

Actually, the choice of project didn't matter that much so long as it was the right size -- this was more about how we develop a program than about the actual program itself.

I started by giving my classes about ten or so minutes to talk among themselves to design the program -- no guidance was given. About seven minutes in, I asked them to reflect on whatever they were discussing - if they were discussing a data structure, why? If class design, why? What was so important about whatever they were discussing that made it their first order of business.

After a while, we started to share thoughts as a group. Most suggestions revolved around details -- how to you check for a winner, how do you make a move. This made sense - we've spent much of the term dealing with writing code fragments to do things and not too much time thinking about overall design.

This lead to a healthy discussion of looking at things from the top down as well as bottom up.

By the end of the class, we had identified the key classes we'd need (Board, Player, UI, Game Driver) and had some idea as to how they would relate to each other. By the next morning, we added a data structure for the board.

Over the next few days we filled in the missing pieces. We moved up and down levels of abstraction being careful to discuss why we designed things the way we did and adapting pieces as needed.

By the end of the project we were able to accomplish the following:

• Students saw how to have classes refer to each other - that is, the Player class had an instance variable to hold the board, while the Game class had instances for Players as well as the Board). 
• We were able to use different user interfaces for the program -- starting with simple console input and then moving to a GUI -- all we had to do was extend the UI class.
• Likewise, implementing a computer player (albeit a rather limited one) was trivial.
• I also tried to show frequent testing and the idea of developing one concept at a time.
• We discussed the idea that while design is important, there's a point where you can over design. Be aware of the scope of a project, what can generalize, and what shouldn't.
• With a good design, it was also trivialize to change things like game rules, how to move, board size. etc.

Based on preliminary feedback, I think the students have a much better ideas as to how to break down, design, and build up a project from design to implementation.

If any one's interested, the code is available here.

We'll see if it helps with the final projects, but I'm optimistic.  Spending time highlighting the design and development process while building a project can only help.

Anyone else have interesting mid-size projects they do with their classes?

Looking for interesting questions

For the winter break, I assigned this set of A exam questions (actually, just the three that don't deal with the case study) to my AP classes. I wanted to assign something that wasn't particularly heavy but I didn't want my students to forget everything over break.

As with most AP exam questions, they're long, wordy, and somewhat brain dead. They take a long time to read, but they frequently take you step by step through what they want you to do.

I remember the first time I really thought about this. It was back when the exam was given in Pascal. The curriculum required that classes cover one of the nlogn sorts but didn't specify which one. One of the free response questions literally walked the students, step by step, through the merge sort. Part one had them split an array in to two parts, part two had them write a routine that merged two sorted arrays (and explained step by step how to do it). You could get a perfect score and still know nothing about the algorithm, or even about writing a recursive routine (since the question told you exactly what to do).

I hate these types of questions. The exam tests coders, not computer scientists. Programming competition problems (such as from the USACO) are much more interesting, but from a beginners point of view they have their own problems. Beginners might not have enough tools to attack them, and at times they're all or nothing – they're not set up to develop a simple, working solution that you can then improve on.

So, I'm always looking for interesting questions for my students. Problems that a student can attack with a minimal skill set, but can be refined through analysis or upon studying more advanced techniques.

I guess the first problem of this nature that I usually do with my AP students, usually deals with counting frequencies of test student test scores, identifying students by their four digit ID number. Most students start by creating a huge list all the tests for all the students, but some, and soon all, realize that by using the ID number as an index into an array, they can solve this type of problem much more efficiently. Looking at this technique early also sets the stage for looking at topics such as radix sorting and hashing later on.

This weekend I stumbled upon this problem and we'll probably look at in in class some time this week. I like it because you can easily get a naive solution, but it lends it self to a step wise refinement that works well in the classroom.

A few years ago, I also discovered a wonderful article by David Ginat, titled "Effective binary perspectives in algorithmic problem solving" which you can get if you are an ACM member here.

Both the stuff in Ginat's piece and the bowling ball article are nice because they can be handled naively with brute force approaches using arrays, but with a little cleverness you can do much better.

Of course, as students progress through our classes, we have more flexibility as to types of questions. For example, once we do search and other recursive algorithms a few weeks from now, I can present problems that lead to dynamic programming solutions.

I'd love to hear any interesting accessible problems you've come across in your computing careers.