Subversion in the classroom

Ok, not subversion, rather subversion, the version control system.

I've used subversion as a way for students to hand in their projects for years. I haven't used it with my intro classes as I think the learning curve is a little steep and the benefits few, but for A.P. and beyond (juniors and seniors) it's worked very well as a method of collection and I think it's good to get the kids in the habit of using versioning systems.

A versioning, or revision control system let's an individual frequently save versions of their files, in our case, on a central server.  One can easily go back to earlier versions as well as manage changes made by multiple developers. Once one's in the habit of using a revision control system, it can greatly improve  productivity.

For my classes, I would create a repository for a project, give the kids a little version control primer, and they would create projects in the repository.

There are usually a few bumps in the road.

At first the kids go kicking and screaming. They create the repository, and neglect it until the last minutes. I'd wake up on a project due date, check out the repository and seem maybe 4 out of 60 projects only to see them mystically appear as the closing time approached.

As we move through the year and work on more projects, things get better.

Students start to update their projects more frequently. Not as frequently as I like, partly because SVN gets really slow on our system, but it's still an improvement.  Invariably, it saves a student or two when they accidentally delete all their files. Also, when things become  a real mess, being able to go back a few versions is a godsend. A much better alternative than what they had to do in the past, which was restarting the entire project.



What I find really interesting is how wonderful a tool svn is from my point of view as an educator.

By looking at the log files, I can see who made changes and when. By looking at the diffs, I can look at the projects progress much as an english teacher might look at drafts.

 Version control for projects turns out to be a win across the board.

Recently, I've been using SVN for homeworks as well. Homework collection has always been difficult for me as I'm disorganized and forgetful. SVN has made things much easier. At the start of the semester, I made a homework repository for each student. They then check it out at home.

Whenever a student does a homework, he or she just names it according to our conventions (HW1-name, HW2-name, etc.), put it in their checked out repository, add the file(s) and commits. With tortoiseSVN under windows it's trivial.

This lets me easily see all of the homeworks for a student as well as all submissions for a specific assignment. Again it's an overall win.

Next semester I'm going to be experimenting with GIT as a replacement for SVN.

If you're looking for a way to collect and track assignments, I'd highly recommend using a revision control system.

Cold Weather Commuting

That's me with my trusty Bike Friday New World Tourist. Love the bike. Love riding. It's the fastest, most pleasant way to get around the city. My commute by bike, door to door is 12 minutes. Subway is 20 - 25. Walking about 45.

One certainly can't let winter weather get in the way.

I've got the body covered with my Assos Fugu jacket. With just a cheap long sleeve duofold shirt it's great to about 16 degrees. It feels a little boxy off the bike, but as soon as you're riding, it fits like a glove. Expensive, but well worth it.


My real problem has always been my hands. Especially on a short commute when I don't have time to generate body heat.

Most recently, I've been using Pearl Izumi Inferno Gloves. They're ok, but sub 20 degress, they don't do it, particularly since I like riding the hoods where I'm right up against cold metal.

Last year, my wife made a wonderful discovery....

Moose Mitts!!!! They velcro on over the handlebards. You stick your hands in when you ride.

This year, AMF Threadworks designed a set that fit on drop bars. Two weeks ago my set arrived!!!

Last week we were consistantly 20 degress or below in the mornings, I used these $10 hytrel gloves from campmor:

Along with my new moose mitts:

They were terrifice. My hands stayed wram and I have the benefit of being able to regulate temperature by pulling my hands up to the cross bar or out entirely.

If you ride in the cold, check out Moose Mitts!!!!

Towers of Hanoi

Closed out last week teaching the Towers of Hanoi. It's a wonderful topic. Not because it's so interesting in and of itself, but as a platform from which you can explore any number of interesting topics.

Many books appropriate for the AP (AB) curriculum mention the towers, but to my knowledge most only scratch the surface. I randomly grabbed two books that I consider good from the shelf before writing this. One that I actually use when I teach AP comp sci and another more appropriate for a follow up course. Both discuss the towers, but merely show a solution and talk about the run time a little.

So many possibilities left out.

I usually do these lessons with my sophomores but since many of my AP students (juniors) hadn't ever seened the problem, I felt it was worth covering.

By looking at a few small examples, 1 disk, two disks, three disks, four disks, it's easy to notice the symetry in the solutions ultimately leading the this short routine:

 1:  hanoi(n,src,dst,tmp) {
 2:    if (n==1)
 3:      System.out.println("Move from "+src+" to "+dst);
 4:    else
 5:    {
 6:      hanoi(n-1,src,tmp.dst);
 7:      hanoi(1,src,dst,tmp);
 8:      hanoi(n-1,tmp,dst,src);
 9:    }
10:  }  

Now, the fun can really start:

We want to talk about the correctness of our algorithm and also how many moves it will take, that is, the run time. First, we'll use inductive ideas to show our algorithm is correct. This "proof" (we do it somewhat informally) can be enlightening. As sophomores, the only proofs students have seen are those statement/reason things they do in math class. Here we can introduce them to the idea that proof is just an "irrefutable argument" and apply it in a more practical setting.

From there we look at run time, that is, how many moves will it take to solve the n disk problem. It's easy to see the pattern of T(N) = 2T(n-1)+1 . Students will usually see that we can rewrite this as T(N)=2^N-1 which we can also prove by induction.

Now we can see the ramifications of the run time. At 1 million moves per second, it works out to close to 600,000 years. This in and of itself is revealing, we can't just "get a faster computer." Here we can discuss Moore's Law and the physical limits on our computers, making sure to make appropriate reference to Grace Hopper and her nanosecond.

This leads to a discussion alternate approaches such as parallel processing, but that doesn't work if our problem can only be solved sequentially.

The rest of the class is used discussing other hard problems and other approaches including heuristics, probabalistic, randomized, and anything else that comes up.

So, there you have it. From this one simple problem we get to introduce students to:

• Alternate forms of proof (specificall induction)
  
• Intractable problems
  
• Unsolvable problem
  
• Moores law and the limits of our computing power
  
• Alternate approaches to computing  
  
  
  
  • Parallel programming
    
  • Protein based computers
    
  • Randomized algorithms
    
  • Probabalistic algorithms
    
  • Heuristics
  
  

Who is this man?

Who is this man?

I showed this to Devorah last night and she immediately said "Hey, that's the metal filing guy!!!" Yes, you got it -- Wooly Willy!!! Everybody's favorite party toy.

Why did this come up? Well, yesterday, Rick put this together at work. So much for any productivity after that.

It's amazing all the time sinks you can throw together with just a few lines of code and NetLogo.

Talking Shop

During my first few years teaching computer science, I frequently felt isolated. As pretty much the only CS guy I really didn't have any one to "talk shop" with. It's hard to bounce pedagogical ideas off of your colleagues when they teach subjects that are tangentially related, at best.

I now consider myself extremely fortunate that I have four terrific friends and colleagues teaching CS with me. Now we have the same advantage that other teachers have enjoyed for years.

Today I started one of my favorite topics in my AP classes, recursion. Our students have already done recursion during the scheme unit of our intro class so today was at some levels, a review. Most of the students were fine with the basic concepts, but I wanted to make sure they had a solid foundation before we moved to more advanced problems.

I realized even though I "got" recursion back when I was starting out as a CS student those many years ago, no one ever really explained how the call stack worked. When you're calling functions and methods all over the place, how does the system know to return to the right place at the right time. It was alluded to when we expanded a recursion:

fact(4) –> 4*fact(3) –> 3*fact(2) –> 2*fact(1) –> 1*fact(0) –> 1

but never in the general sense of function calls. I thought it might make sense to try to "demystify" the computer and explain how things really worked.

I outlined a basic memory layout, stack, heap, data segment and roughly defined a stack frame (storing parameters, local variables, and a return address). We then looked at a code snippet such as:

a()
{
  b();
  c();
}

b()
{
  c();
}

c()
{
}

main()
{
  a();
  b();
}

and traced through the stack. We then did this with a couple of simple recursive examples. Only time will tell if this was helpful, but I think it was worth the time.

What I particularly enjoyed was later that day when I was talking shop with my fellow AP teacher. He wasn't planning on explaining the stack in this kind of detail but he liked the idea and planned to use that part of my lesson. I look forward to hearing how it went.

I have likewise borrowed ideas from his and our other colleagues classes.

Any CS teachers out there, I'm sure we'd all love to hear classroom techniques that have and haven't worked.

First Day Back

First day back after a break is always hard. By the last day of vacation, I'm actually sleeping a little later and shifting the body clock back is rather harsh.

It's tough enough getting started again, but it's even worse when you're thrown a curve ball.

I got in at my usual 7:00, made my coffee, and started getting my lessons ready for the day. At about 7:30 we lost power in half of the room. Unfortunately, it was the half with the CS servers. The machines that provide log in and file services as well as svn, our web server, mail server, wiki and other services.

Now, on top of my teaching duties (four classes of 32 students and another of about 20), I basically run the computer services for our CS program. I used to do the whole network, but I stopped that a few years ago. I receive some help from colleagues, but it's still mostly me.

For our CS program we have two Linux labs of about 31 computers each (all running Linux) and a bunch of servers running the same.

After spending about 20 minutes to find the circuit breaker, most services came back up. Terror struck 10 minutes later when we saw that all of the students home directories had disappeared!!!!!

After a brief period of panic and a few stressful minutes of scouring file systems for evidence of the missing directories I found the problem. The answer, as with so many other problems, is that I was being an idiot. About a month earlier, I had installed a new drive for the student directories. I had mounted it, but neglected to change the fstab file. This is what happens when you have to do all your sysadmin work on live systems in brief periods of time between classes. When we lost power today, the old drive was mounted, not the new one. It's fixed now.

It would be nice if there we actually had people to run our systems, but since that's not going to happen, I've spend time over the years to try to make the whole thing somewhat do able. Using common tools such as NFS, NIS, Apache and the like help, and we've currently moved to using kvm for virtual machines so we can easily experiment with new systems and cleanly and have a one "machine" per service mentality, but system administration still can't really be done as a part time job.

Any one out there have any war stories or suggestions as part time sysadmins?

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.

Welcome

Over the past twenty years or so, I've mulled, discussed, and argued various aspects of education, computer science, and of course computer science education with friends, students, and colleagues.

This past summer, I had the privilege to get to meet and briefly work with comp sci educators from around the country and started to thing that there were other like minded people, but we didn't have a forum with which to communicate.

I also started to think that maybe some of the things I've discovered over the past twenty years might be useful to some one  if only it were available.

So, there you go. The plan is to regularly post about items of interest that I've come up  with ranging from pedagogical techniques,  to facilities management, to interesting class topics, to anything else that seems relevant. I'd imagine that some of my other interests, notably food, biking, and family will also creep in.

Hope others find this interesting and relevant.