Algorithm Kid

Fairly recently I started exchanging blog comments and Identi.ca notices with an English geek Steve Clark, who's interested in the social semantic web, Python, cryptography, etc. Steve recently wrote a blog entry entitled "Programming languages I have known", which I found interesting, mostly because Steve started programming in an era of computing that I was born just late enough to miss out on, but have always felt a sort of strange, artificial nostalgia for, like I should have been a part of it. Acoustic couplers, and all that.

I liked the idea of a blog entry that was autobiographical but still mainly technical in nature, and thought about writing my own version of "Programming languages I have known", but I realised that this would, in fact, be pretty boring. I don't know that many programming languages, the ones I do know are entirely mainstream and historically-uninteresting, and I taught myself comparatively late (I think I was 15 when I bought "Sam's Teach Yourself C in 24 Hours", which I just now found free online by Googling it). Then I thought about just writing something not on languages but on the various computers I'd used throughout my life, but that would be pretty standard and boring, too: My primary school had two BBC Micros, my household, two relatives and lots of my neighbourhood friends had Commodore 64s (one of these machines had a magnetic tape drive, which took cassettes of the same size as the old music cassettes, everybody else had 5.25 inch floppy drives), and then came the rise of the IBM PC.

Instead, I decided to write about two incidents I can remember from my primary school years in which I displayed a way of thinking which was in some sense algorithmic in nature - thinking like a computer programmer years before I wrote a single line of code, or at least wrote one that I actually understood.

The first of these concerns a game that one of my primary school classes would occasionally play. One student chooses a number between 1 and 100 and keeps it a secret. The rest of the class take turns attempting to guess the number, to which the first student must respond with either "higher" or "lower". The student who eventually guesses the correct number then gets to choose the next one, and the game repeats. In retrospect, it's amazing the kind of mindless and repetitive stuff that young kids will find fun. Anyway, I remember quite clearly the time we were playing this game when I realised that there was one clearly optimal strategy. I think I was around 11 or 12 years old at the time. The strategy I had developed was this: the first student to take a guess should guess 50. Depending on whether the response was "higher" or "lower", the next student should guess 25 or 75, and so on, with each student guessing the number in the middle of the not-yet-disqualified range of possible answers. If you have no prior knowledge about what the secret number is likely to be, this strategy is the best you can do, in the sense that it minimises the average number of guesses required to find the answer. A very similar method can be used to find the zeroes of a scalar function, though of course I had no idea about anything like that at the time (note that the method is not at all optimal for the zero finding problem). I remember that I figured this out by visualising the number line from 1 to 100 and realising that each guess ruled out either all the numbers to the left or the right of it, and observing that by guessing in the middle of the remaining range you were guaranteed to rule out half of it, whereas by guessing anywhere else there was always a chance of ruling out less than half of it. I became quite excited when I realised this and explained it to the rest of the class, assuming that they would concur and cooperate with the strategy. Ever future instance of the game would be over in less than 7 guesses (the logarithm of 100 to base 2 is 6.64)! However, nobody else seemed to believe me and in fact the class as a whole was quite hostile to the idea of any kind of systematic approach to the game. Looking back, I guess the algorithmic approach probably ruined whatever element of "fun" we must have seen in the game, but at the time I was baffled by this resistance.

The second incident happened earlier, I must have been between 8 and 10 if I correctly remember the way year levels were distributed amongst classrooms at my primary school. However, it's also less impressive of an insight. Around this time my classroom went through something of a football craze (note that Australian football is not the same as European football, which we call "soccer", nor American football, which we call "rugby". Actually, I'm not sure rugby and American football are the same, but who cares?). I never really got into this (I've never really got into following any kind of sports), but I remember being baffled by how little any of the other kids thought about the outcomes of football matches (I'm talking about matches in the national league, here, not lunch-time games) as being predictable from data. During this craze, a lot of kids collected football cards, and each card would have on the back all sorts of statistics about the corresponding player, things like the average number of points scored or marks taken per match. Kids would have huge folders full of these cards, each one slotted into a position in a plastic sleeve. They were veritable hand-held databases. And yet, given these databases, kids were making their decisions about which team to cheer for based on things like team loyalty or who was on a "winning streak" or simple gut instinct. I remember it being obvious to me at the time that the sensible thing to do was to assign some number of points to each team on the basis of the available statistics and to support whichever team had the most points. I never worked out an explicit scheme for doing this - presumably a team would get something like one point for each game it had won so far in the season, and one point for each average goal scored by each player who was participating in the match. I do remember realising it would be necessary to take off points for each participating player who had an injury. If I ever explained these ideas to anybody, I don't remember it. No doubt they would have gone down as well as the method of bisection did for guessing secret numbers, anyway. No doubt my plans for a point assignment system were rather simplistic, perhaps too simplistic to have worked very well if I'd put them into practice (I never did, because at that age I didn't have the computer skills to program it, and doing it by hand would have been tedious, especially since I didn't really care about the football anyway), but the point stands that I was aware by this age of the principle that numerical data about past events could be used to forecast future events. I have no idea where I got this idea, whether it was just intuition or if I generalised from an actual observation.

Although these are appropriate childhood stories for someone like me to be able to tell now, I don't actually understand why it is that I can remember them as clearly as I can. They must surely have been fairly inconsequential at the time. Can I remember these things so well because they were part of the birthing process of my now excessively algorithmic way of thinking, or is my distribution of childhood memories unbiased with regard to these sorts of things, and two of those memories just happened by chance to be like this because I thought that way a lot? Memory's a funny thing.