Where's Waldo - Text style

Ok, it's a word search.

We're always looking for interesting applications to build lessons around. Over the years, I've tried different things when teaching 2 dimensional arrays. Simple game boards, representing a crossword puzzle, tables of various sorts, etc.

This year, JonAlf, one of my amazingly talented colleagues, decided to go with building a word search. I decided to steal the idea. It's a great one.

I thought I'd use this post to go through the project and why I like it.

Ultimately, the students end up with a program that will generate an n by m word search filled with random words from a dictionary. We gave the kids a skeleton of the base class. The only actual code we had to supply was the method that loaded a dictionary file into memory. You can check out the assignment here and the finished code here (we updated the repository as the project developed).


The first part of the project are pretty mundane. The kids write a couple of constructors and toString. Basically just practice traversing a 2D array. The project starts to get interesting at part 2, when they write the methods that add words into the grid. First horizontally:



After they write the method to add words vertically, we can start to refine things. We notice that the routines are essentially the same. The only difference between adding a word horizontally and vertically is  what we add  to the row and column each time. For one, there is a delta column of + 1, for the other it's a delta row. Further, they realize that adding diagonal words just needs both deltas. This leads us to factoring out the common aspects of the code and writing something like:



All of a sudden, they've written one piece of code that can add words in 8 orientations.

After filling the rest of the grid with random letters, we turn our attention to building a random puzzle.

This part of the project involves using an ArrayList of words. Our students frequently mix up array and ArrayList notation early on so by having a project that uses both but in clearly delineated areas, the students can be more comfortable with each.

For this piece, the code is again straight forward. Students run a loop that gets a random word from our dictionary and tries to place it in our grid at a random location choosing one of our possible orientations randomly. We get to see another nice little refinement again when we move from the typical first take at building a random puzzle which uses a three (or more) way if statement to select how to add words:



to using our more general addWords method described above:




When we're all done, we had some time to project the word search on the board and fun was had by all.

Peter, another one of our CS teachers had a great suggestion that I think I'll try. Start a competition to have the students modify the program so that it generates as densely packed  a wordsearch  as possible (giving higher scores first for longer words, then number of words).

Between the way the project broke down, the topics covered and the little refinements, I really enjoyed working with my classes on this project -- I'm hoping they enjoyed it as well.

Reboot

A couple of weeks ago, I attended the K-12 workshop at the Grace Hopper Celebration of Women in Computing Conference. It was great to reconnect with some old friends, make some new ones, and talk shop for the weekend.

One result was that I promised to start blogging again.

I've got a number of ideas for posts lined up. Some on pedagogy, some technical, and some cultural. Hope you enjoy them.

Earlier today Ben Chun tweeted about this post: http://worrydream.com/SomeThoughtsOnTeaching/.  To summarize -- teachers should practice what they preach. In the post, Bret Victor wonders if there are calculus teachers who spend their evenings doing calculus.

I know a number of math teachers who spend a considerable amount of their free time working on problems and refining their math skills, I also know many who don't.

I know wonderful, inspirational teachers in both camps. I've also known weak teachers that fall into both categories. Great teachers in both categories also spend large amounts of time working on how to best deliver instruction.

Before I started developing the computer science program at Stuyvesant, there were one or two sections of A.P. Computer Science. They were taught by a terrific teacher -- one of my mentors and role models, but he was a math guy and not passionate about CS. When I took over, the enrollment immediately shot up. Not because I was any great shakes, and Dave, the previous teacher was legendary. Rather, the students knew I loved CS. Part of that love was that I enjoy solving problems with computers, coding and what have you. The students can tell.

The fact that I code is a byproduct of my passion and part of the whole package that defines me as a teacher and a person. Whatever success I achieve is a result of this package. It's something I enjoy, and it also keeps me current with the field.

I've seen "naturals" who are just great teachers and get by without a passion for their subjects. More often than not, there's a ceiling in terms of what they can give their students either in terms of content, or more importantly, in terms of inspiration. Some times the ceiling is high enough that there isn't a problem.

Over the years, my "practice" has taken different shapes. Early on, while my students were working on USACO problems. I figured I had better be able to represent, so I started doing them. Later on, I would write systems to support my teaching.

More recently, I've been lucky enough to be surrounded by a number of like minded educators. We frequently share little projects we work on.

This semester, I've been taking the Stanford on line AI and ML classes -- both have been lots of fun.

This is just what I do and who I am and it is reflected in how I teach.

Of course, time and job constraints make coding difficult during the school year. With ~150 students, lesson planning, grading, and ancillary responsibilities take their tolls.

So, I guess I'm an example of what Bret Victor was talking about. I'm not sure I fully agree with his thesis, but it seems to work for me.

What's Next

Just a short follow up on the last post.

In thinking about how I frequently programs, once I have a plan, I work on one part of the project, and then ask myself "what's next?" That is, what is the next step towards completion.

It reminded me about a guest speaker we had a about a year and a half ago at one of our "professional development" days. For the past two years, our school has had "writing across the curriculum" as one of it's goals. While it's a laudable idea, I find the rationale for this goal to be poorly communicated to our faculty and the implementation weak at best.

Regardless, the guest speaker, William Zinsser, made a few good points.

The most important reason for most of us to write is to convey ideas or arguments. In short, communication. Many students have problems organizing and ordering their thoughts and as a result, their writing is all over the place. Zinsser simplified it to the following:

1. What does the audience know?
2. What do they need to know next?

That drives your next sentence. You continue this 1-2 punch until you've communicated your ideas.

This makes loads of sense, but here I was 40 years old and it was the first time I heard writing explained this way. What really struck me, however was that this concept wasn't new at all. Every ninth or tenth grader goes through this process time and time again.

Think about geometric proof. We have some given information and a conclusion we wish to prove. At each step along the way its:

1. What do we know so far?
2. What's the next step to get us closer to the conclusion?

Same idea.

The same can be said for program development.

Of course this makes tremendous sense since all thee things: writing, proof, and programming, are methods of communication.

Just something to think about.

They teach programming, don't they?

One evening, many years ago, when I was in college, I had an epiphany. Maybe not as enlightening as the epiphany I had while watching "The Mummy Returns"  many years later, but that's a story for another day.

While working on some class project, I realized that soon, within a couple of  years, I'd be working for a real company and I'd actually have to write code that REALLY works. Not just something that gets past the grader, or answers all the test cases. Something well designed, well written, maintainable, and reliable.  Scary thought.

I've thought about this a lot since I started teaching computer science. We teach programming languages, algorithms, and assign projects. Maybe the students hear something like "comment your code," or "use good variable names," but we never really give them the tools to take a project from description to completion.

Too often young programmers rush to the keyboards and write copious amounts of code without any plan and with little discipline. In short they do everything they can to set themselves up for a difficult road ahead.

There are probably a number of reasons for this. When we teach introductory  programming, assignments are so short and simple that we can't easily model good programming techniques, and if we do, it's difficult to get students to "buy in" since it's hard for them to see the value. As complexity increases, we're faced with limited time to actually cover the prescribed course content, leaving little room for a protracted unit on "program development."

I'm certainly not going to be so bold as to say that I have the answer to the problem, but I've tried some things to help address it.

We'll take a few class days to take a project from beginning to end. Something that can be done incrementally but isn't particularly difficult.

This semester, I attempted this with my AP students. We wrote a series of text filters in Java. I lifted the topic from Kernighan and Plauger's "Software Tools." We wrote versions of character count, word count, detabbing a file, run length encoding and a simple version of tr. Nothing too heavy, but it allowed us to focus on the development piece rather than coming up with clever algorithms and data structures (which is what the rest of the class is for). The problem may be a little contrived, but I hope the benefits outweighed any issues with the choice of problem.

We start by talking about the importance of understanding the problem, which includes finding out what "the client" wants and not making our own assumptions. Some times, I try to leave a little ambiguity to give us a platform to discuss the "what the client wants" issue.

From there comes design, which might be mixed with writing some code to make sure we understand certain aspects of the problem and the environment we'll be working in.

Once we have a design and a plan we can start incremental development. This is what I think is most important for the youngsters. I try to model and emphasize the idea of coding one "concept" at a time. Frequently testing that concept and only moving on once it's completed.

I'll also talk about things that have worked for me along the way. I always like to put consistent comment blocks at the top of my functions, trying to keep functions a "screen length" or shorter, my preferences for naming, indentation, etc. Of course, I'm careful to emphasize that my way works for me, but it's just one approach. I try to present alternatives when possible.

Other ideas I try to emphasize is actually reading ones code and having others read it. Last semester I experimented with "pair programming" and while I have no idea how good it is as a professional development technique, I like it from a pedagogical point of view.

I think presenting these ideas while actually developing the project helps to drive in the concepts.

I'd like to think adding units like this helps to develop stronger programmers. Any teachers out there -- your thoughts?







In an unrelated note, yesterday was valentines day. We don't really do anything to celebrate it, but in anticipation of her new loom, Devorah had to clear off some room in the apartment. She stumbled upon love letters sent between my parents back in the fifties. If you'd like a small taste of the past, you can see here post on squidknits here.

Although we have gained all this immediacy with the electronics age, it sometimes feels that somethings been lost.

Subversion for Homework part II and the start of the new term

Starting the new semester tomorrow and I've got a whole bunch of interesting topics to blog about. Some about pedagogy, some technical, and some that I can't really catagorize.

For now, though, just a brief follow up on using Subversion for homework collection.

The basic model used in New York City for teacher improvement and evaluation is the official "observation." Either your supervisor or the principal sits in on one of your classes. Afterwards you meet and discuss the lesson and a report is written up. Basically, there are two possible outcomes: satisfactory or unsatisfactory.

Untenured teachers are generally observed three times a semester. Tenured teachers, once a year.

In all cases, this system is severely flawed. The supervisor sees a 40 minute snapshot out of context and is supposed to evaluate the teacher and make recommendations for teacher improvement. It's generally of limited value at best.

Because of this, years ago, I started to ask my students to evaluate me. For quite some time now, I've used a custom written web app that allows students to complete long questionnaires over a period of weeks. The system allows me to know who submitted an evaluation while maintaining anonymity.

I've found these evaluations to be incredibly valuable and I've used them to try to improve my classes and my teaching over the years.

Having just wrapped the semester, I've gone through my students responses and the vast majority liked using subversion for homework. As I figured, some felt that it was a little confusing at first and there was a learning curve but most felt it was either as good as any other method and many said it was superior.

This combined with the fact that it makes me more efficient confirms that it's a win.

It was also interesting that I had hardly any suggestions for alternative ways of collecting homework.

Recently, I've been using Git for my personal development work and I'm planning on experimenting with it in one of my classes, so we'll see how that goes.

Now, on to the new semester!!!!!

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
  
  

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.