A-mazing we will go.

Have been goofing around a lot lately with recursion, cellular automata, and Pygame.  Working with students to develop a floor-plan generator for dungeons and mazes has led to some fun programs.  The image above is from a Python program that creates a depth-first search maze, and then attempts to solve it using a slightly different algorithm.  The beginning square is the far upper left, and the ending is the far lower right.  White corridors have never been visited.  The pink ones were visited but led to dead ends.  The green path, however, is the correct solution.

Currently working on a version that goes beyond mazes to dungeon-like floor plans.  The program will print out the data to a text file to be used by other programs and other languages.

Is there something in-between?

Lately we have been goofing around a LOT with Cellular Automata and Agent-Based simulations.  Of course we're working on the Genetic Algorithms cases study, but some students have asked about other applications of these really interesting parts of computational science.

So today I was reading Cities and Complexity and came to the part where they shift from strict rule-based, deterministic cellular automata simulations, to simulations that include random elements.  I immediately remembered something that I had thought of a while back while working on some of Wolfram's one-dimensional CA studies (and then, for some reason, I completely forgot about it again until this morning).  Here's the thought:

When we think of a typical CA simulation, we use a single set of rules, like, say, Rule 110 for the one-dimensional CA that Wolfram had studied.  That rule is a strict one-to-one mapping of situation to response, so there is NO randomness at all. 

Naturally, one gets curious about what adding random elements would do to the patterns.  But then I thought of something else, and it really got me to thinking about determinism and randomness.  Let me just show you what I was thinking:

Rule 30 from Wolfram is the base 10 name for this binary mapping:

0 0 0 1 1 1 1 0

Now of course that tells each cell what to do (whether to be "on" or "off" in the next phase) for each of the eight possible situations it could be in. 

So, if we wanted to, we could randomize it by replacing one of those digits with a coin flip (f):

0 0 f 1 1 1 1 0

Here, in the third digit from the left, we have switched from "always turn off" to "turn off with a 50% chance. "  By that we mean something like, "flip a coin, dude, and heads you are on, tails you are off."

But then I remembered something I had toyed around with when thinking up some AI patterns and state machine stuff for a simple game I was working on.  What if, instead of something like "choose 1 80% of the time, chose 0 the other 20%" was handled differently?  What if we instead put an array of numbers into that particular position, with a string of results in it:

0 0 [ 1 1 1 1 0 ] 1 1 1 1 0

Now, instead of an 80% CHANCE of choosing 1, we simply tell the agent that she should respond with the number in the array--and she should increment by one each successive turn.  Meaning, using the example above, when the 3rd position in the array first comes up, she chooses 1.  She does that the 2nd, 3rd, and 4th time, also.  However, the fifth time she chooses 0.  After that she simply loops around and starts over at the beginning.  So you can see that she will choose 1 exactly 80% of the time, but there's no chance involved.  It's completely deterministic, and yet it takes the whole question of one-dimensional CA to a whole new level of, well, complexity.  Or does it?  I really haven't had much time to think about this in detail, but it seems strangely different than randomness. 

I guess what it really makes me think about is how attractive the finite set of 256 rules that Wolfram studied seemed to me at first.  How ... cozy it seemed that the structure was so, well, structured.  Now I'm thinking that there's an infinity of rules--all strictly deterministic--that could be looked at for good ol' one-dimensional CA. 

Time to hit the books....

Coding During the Big Game

I hope the above image somehow leads to a Superbowl win for the Green Bay Packers.  I mean, here I am, after wrestling with some objective-c code for the last hour or so, and I cross my fingers, hit "build" and ... it worked!  

Maybe today is just a day for Wisconsin to rule the world.  Watched the Badgers blow out Michigan State this morning, my code just compiled cleanly, and now it's up to the Pack to win the Big One....

Go Pack!

New For Skyline Next Semester: Screencasts!

In the past I underestimated how important the multi-media aspects of a computer are to teaching computer science.  Whereas in the past it seemed like the instruction in my lab was happening in human space, all the programming was done on the screen.  Those lines are starting to blur, though, as more and more instruction can be done via the computers themselves. 

In the past Linux was easily my preferred programming environment--still is.  However, I'm a teacher, and I need to do more than just write code.  I never imagined the Mac lab to be so far ahead of anything else I've ever used when it comes to making my teaching more effective. 

This coming Spring students and I will be making screencasts for future students (and for present students that need a review)--ranging from the basics of programming (how to use the unix terminal, text editors, etc), to other particular skills.  I can think of no more efficient way to capture knowledge than to just record examples in realtime. 

Let's Do Something Fun This Year: Genetic Algorithms!

I have to admit--the new Computer Science lab has made teaching Computer Science so much easier that I rarely feel the need to complain about things.  Sadly, I also blog a lot LESS than I used to.  And that is unfortunate, because our school is quickly becoming a top-notch Computer Science high school.  The more we end up actually doing, however, the less we seem to document it.  That irony stings a bit.


Heck, even using something as innocent as the Apple Remote Desktop has caused me to rely less on Google and the web in general.  Why upload assignments to our class website when I can just click and drag it onto their desktops?  Also, I can improvise stuff on the fly and share it immediately with my students.

Still, there's something to be said for documenting the great things that we do in education.  So what the heck, might as well share one of those things here.  This year Skyline Computer Science students and members of the Skyline Programming Club are working on two major projects that I am very proud of.

The first is PyKata.  PyKata aims to be an open place for teachers and students to practice writing functions in Python.  Of course we were inspired by JavaBat, and we only hope to make PyKata challenging and fun.  This is a way for Skyline's graduating class of programmers to leave behind something for future programmers at Skyline to use for years to come--not to mention anyone else in the world that uses PyKata.

The second is something that occured to me and a few of my senior programmers: working together on a year-long, school-wide case study.  Since there was a lot of interest in a classic example by Melanie Mitchell, we are going to roll up our sleaves and do some old-school science work.  We are going to attempt to repeat her results--to confirm them.  We are then going to add our own style to her study and take it further.  Whereas Mitchell's study dealt with evolving robots efficient at picking up cans--we'd like to give it the Skyline touch and try evolving other types of bots.  Bots that make beautiful art, for instance.  You will see this project develop mostly during the Spring semester, but to get started, check out the project's main page now.

Okay, I'll admit....

Programming on a Mac is quite nice.  This year we got a brand new Mac lab (36 iMacs) for our Computer Science classes at Skyline.  Students love them.  They're built for programming.  Their ability for digital media integration is outstanding.  One of my students is currently working on programming the iSight cams to implement facial recognition. 

Best thing yet:  Haven't had to reboot any of these Macs during class.  :-)

The Simple Hello Instructor Assignment

I teach a full schedule of computer science courses, and one section of Geometry that utilizes Geogebra.  The very first assignment I give is exceedingly simple, but tells me more about a student than nearly any other type of icebreaker on the first day: I have them send me an email with a particular subject field (like, for example, "B5 hello"), and have them introduce themselves.

Working at a school progressive enough to use Google Apps Education is a dream come true.  I receive those emails and can do a subject search for the particular subject ("B5 hello").  I see how many students sent an email with that exact subject heading.  Then, I look around for the rest, that usually have slight differences like "B5hello," or "B5 Hello."  I give them credit, but we do discuss how syntax errors occur in text editors when you use "Print()" instead of "print()", for example.

Then I deal with the students that didn't send an email.  Many times there are English Language Learners, and getting a quick handle on their level of English development is pretty important. 

Of course you also quickly find out which students have not had their accounts set up for them yet, and so on....