The suggestion came from the top: “how about an article on HD video, HD TVs and all that?” When you get those kinds of suggestions, you don’t raise trivial issues like the fact you don’t even have a TV, let alone an HD TV. You File New in Word and get to work.

Yep, it’s true. We don’t have a telly. It goes back to the days when I first came to live in the States in 1993. I thought I’d only be here a couple of years. I was still paying the mortgage on my flat in London, so I wanted to save up and not blow it on an electronic behemoth that I couldn’t ship back (it wouldn’t have worked – different voltage) nor on the cable subscription to feed it. So, no TV in the Bucknall bachelor pad. Then when I started going out with Donna and it was obvious I was going to stay in the US, she was studying law for a JD and definitely didn’t want a TV. That absence has not made the heart grow fonder: nowadays it’s much easier to watch TV drama via Netflix or Amazon.

Nevertheless, writing about high definition video was quite fun in the end. I actually learned a lot about the whole television process, especially as it’s so different between the UK and the US. There were topics like interlacing, telecine, blur, bilinear interpolation, upscaling, and so on, to research and write up. And I’ll admit it feels good that I can now spot the comb effect from progressive scan on older shows converted to DVD and furthermore explain why it happens. Geek.

All in all, a great little article, even if I say so myself. I think the man on high was pleased with it too.

This article first appeared in issue 303, January 2011.

You can read the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are thirteen issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

A fun one this article: talking about digital recordings and how they’re saved for later playback. Especially CDs and MP3s.

I chat a bit about audio quality, particularly with regard to the fact that MP3s are always lossy compressed data. But then again, so are CDs lossy to a certain extent: they are sampled, admittedly at 44.1KHz (it’s roughly double the limit of human hearing, plus a bit more to help encode very high frequency sounds without losing too much definition). Studies have shown that people listening to 256Kbps MP3s and CDs can’t tell the difference. 128Kbps MP3s are equivalent to good FM radio, and anything less you start to notice the muddiness of the audio.

Funny story about me and MP3s: back in the day (starting in 2002) I used to use a Sony Clié NX70V as my PDA. It was a great little device and I bought lots of little apps for it (this was waaaaay before Apple’s AppStore, mind you, so you had to go looking for them) like MathU Pro, Ultrasoft Money, Acid Solitaire and so on. It also has a good little MP3 player, and for flights to and from Las Vegas (where I was working at the time) it was ideal. The battery wasn’t brilliant and used to die after about two hours, but that was OK for the trips I was making (and besides which I bought an external battery pack that used AA batteries for those really long flights). The only problem with the MP3 player was that it could only reliably play 96Kbps MP3s, so at the time I ripped all my CDs to that particular bit rate, which as I said above is a bit less than FM quality. I still haven’t re-ripped all those MP3s so half my MP3 collection is at 96Kbps and the more modern half at 256Kbps. Sigh. And now of course everything is indexed by iTunes and replacing them will mean I lose my play information. (Hmm, I wonder if there’s a software solution for swapping them out. . .)

Anyway, the article is a good lightweight layman’s introduction to MP3s and how they work. It was ideal for the Christmas issue.

This article first appeared in issue 302, Christmas 2010.

You can read the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are thirteen issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

On rereading this just now, I just had to laugh. Two reasons I suppose. First of all, the article is really about Markov chains (my original title was just that), and I spend just 3 paragraphs right at the end talking about speech recognition. I think my editor was a smidge too enthusiastic about the speech recognition part. Secondly I note that I talk about random walks in a couple of places – even Gambler’s Ruin – a topic I skirted just recently here. It certainly sounds like I knew back then what I couldn’t work out a few days ago; so maybe there’s something to all this forgetting stuff as you grow older.

Where was I? Oh, yes, Markov chains. In essence, they’re a description of a finite state machine with the transitions between states governed by some probability model. What can we determine from such a model? Well, there’s the possibility of calculating the probabilities for a steady state after a large number of transitions for a start. Using the Viterbi algorithm, you can try to determine the transition probabilities for a “hidden” model from a series of state changes. The standard (read: old) method for pricing equity options uses a Markov chain model known as the Black-Scholes algorithm (and, boy, does that take me back to the time I worked for the swaps trading desk at Deutsche Bank).

This article first appeared in issue 301, December 2010.

You can read the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

The call went out: November 2010 was going to be the 300th issue of PC Plus. Our articles had to be better than ever before and preferably some kind of top N list to go along with the issue’s theme (the lead article for example was 300 Advanced PC Tips).

So, my top 10 algorithms? Data structures? A possibility, but I wouldn’t have much room to say anything in depth about each (“Number 4: Quicksort. It’s very fast at sorting but a bit complicated to get right. Number 5: Red-black trees. A very fast search structure but nearly impossible to get right.”). After some thought I finally decided on listing my top 10 programming mistakes. I’d been doing a series of “Messages from the CTO” for the DevExpress newsletter and some of these top 10 items came up during my writing those for work. Hey, I’m all for recycling!

As it happened, this particular article turned out to be the most popular I’d ever written for PC Plus. It got published online by techradar.com, with more comments than I ‘d seen before for one of my articles posted there. I got mail about it. I seem to remember it got picked up by the Code Project newsletter as well. All in all, quite a good one.

This article first appeared in issue 300, November 2010.

You can read the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

I’d just read a book called Introduction to the Theory of Computation by Michael Sipser and found it fascinating enough that I tried to encapsulate what NP-complete means in a 2000-word essay for October 2010’s issue. Was I successful? You’ll have to read it to find out.

In essence, I talk a bit about big-Oh and show that algorithms that have exponential or factorial big-Oh expressions are terrible to implement since they rapidly get to the point where it just takes too long to do anything. I then elide a smidge of “intractability” and a whiff of “decidability” and introduce NP-completeness. I show that if you solve one NP-complete problem in “polynomial time”, you’ve solved all of them since they are all transformable into the “Boolean satisfiability problem” in polynomial time. So, solve that last one in polynomial time and the computing world will beat a path to your door and fête you forevermore.

(Annoying things: again I tried to have superscripts in the text. I should have learned my lesson by now: it gets lost during the typesetting. So, for example, PermSort – see the article for what it is – would take 3 * 10¹⁴³ years to sort 100 items at a rate of a million permutations per second.)

This article first appeared in issue 299, October 2010.

You can read the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

Ah, memories, memories. For September 2010’s issue I wrote about how to solve Rubik’s Cube, and it allowed me to revisit my days at Kings’, London, when I first came across the puzzle. Back in those days (and probably even now), the Maths Society at Kings had a fun weekend away in Windsor Great Park where we’d have talks about recreational mathematics. (Yes, I know, many people don’t think “recreational” and “mathematics” can be in the same sentence, but bear with me here.) Of course, it was an occasion for too much drinking and smoking and playing 3-card brag and staying up all night, but in 1979 we discovered a puzzle that pushed all that aside: Rubik’s Cube.

And, boy, was it addictive. We had Prof Singmaster (the author of the first book about Rubik’s Cube, and the person who laid down the naming convention for describing Cube moves) attend and he showed how to solve it using simple moves that could be repeated ad nauseam to eventually solve the Cube. He also showed how to speed up the Cube by disassembling it, sanding the internal sides a little and spraying with silicone spray to lubricate it. I practiced enough over the next few weeks that I could easily solve the Cube within two minutes, but never got better at it than that. These days, people are solving it within a few seconds, which is quite incredible.

In the article, I discuss various manual algorithms that have been devised since 1979. There’s Singmaster’s original, Fridrich’s (the one where you have to memorize 120 different moves), Marshall’s, and Petrus’. And then came the computer algorithms: Thistlethwaite’s and Kociemba’s. There is of course the ultimate algorithm known colloquially as God’s algorithm, but no one has found that yet.

Another aspect to God’s algorithm is how many moves does it entail to solve a thoroughly mixed up Cube? By simple counting arguments, it was shown early on that the lower bound is at least 18 moves. Coincidentally, just after I’d written this article, Rokicki, Kociemba, Davidson, and Dethridge proved that all cube positions could be solved with at most 20 moves (they used a computer program to essentially count them all).

Me? I’ve still got my original 32 year old Cube. It’s still as smooth and fast as ever, but I’ve now forgotten my moves. The muscle memory I’d achieved through those weeks of repetition has been lost. I now use an iPhone app to solve my Cube, although mine has the colors in the “wrong” order. It’s non-standard according to the prevailing color scheme so I have to remember to swap over two colors when entering the random Cube into the app. My wife bought me a wooden 30th Anniversary cube last year for Christmas and let’s say there’s no way it’ll ever be used in speed trials.

(Fascinating fact: Images of Rubik’s Cube are copyrighted. My editor at PC Plus, Alex Cox, had to apply for permission for us to use images of a Rubik’s Cube in the article. Fascinating fact 2: the images we used were generated by Alex from a POV-Ray template.)

This article first appeared in issue 298, September 2010.

You can read the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

This particular article explored how to generate arithmetic expressions using a card game as a basis for discussion. It appeared in August 2010, and came about because of me reading two blog posts on entirely different topics within a week or so of each other. The combination triggered an Ah ha! moment, and I wrote it up. The first was for a card game called Krypto and appeared on The Daily WTF; the second was about generating all binary trees of a particular size and appeared on Eric Lippert’s blog, Fabulous Adventures in Coding.

In essence, for the card game you strip out all the court cards and jokers, shuffle the remainder and deal out five cards plus one to the side. The object of the game is to think of an arithmetic expression that links the values of the five cards (in the original sequence, mind) to equal the value of the sixth. You can use the four normal operators in any combination plus as many parentheses as you need. It’s not a bad game to exercise your arithmetic abilities and can be quite difficult for certain combinations of cards. Where enumerating all binary trees come in is to try and write a computer program to list out all possible expressions that satisfy the card layout.

In the article, I used Reverse Polish Notation (RPN) because it’s a damn sight easier than infix notation, and I glibly tossed off an assertion saying it’s easy to convert from RPN to infix. I then wrote a blog post about how easy it was, only to be brought up short, because it damn well isn’t. Sigh.

This article first appeared in issue 297, August 2010.

You can read the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

For the July 2010 issue, something rather cool: face detection. How does a program (such as that one in your point-and-click camera) work out from an image whether there is a face in it, and if so where it is?

The algorithm most used is the Viola-Jones classifier algorithm. Basically the way it works is not to try and identify a face in the image, but instead to analyze the image for certain rectangular “features” – no, not facial features, something altogether more basic than that – and then classify those features. But what features should they look for? In essence they analyzed thousands of faces culled from images on the internet to identify certain large scale characteristics that appeared in all/most of those facial images. They then designed (and trained – it was a neural network) a cascading classifier such that if an image had features A or B then it probably was a face, otherwise it certainly wasn’t. Next up were features C, D, E, etc. If the image failed at all of these, it wasn’t a face. And so on, so forth.

The eventual neural network was fast enough and small enough to fit in a camera’s ROM, leading to those clever cameras that can spot a face in a scene and focus on it. Now they even can tell if the face detected is smiling… Damned clever, what?.

This article first appeared in issue 296, July 2010. It was also published online on the TechRadar site.

You can read the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

This article followed on from the previous, as it happened. You see I’d painstakingly drawn the figures for the pentominoes article in Adobe Illustrator and I got to wondering if there was an easier way to create them. I half-remembered about ray-tracing (my friend Duncan had created some great images a while back) and so I looked it up. A couple of links later I had POV-Ray downloaded and installed and was playing around. Naturally, the ray-traced image I spent most time on for this article was an image showing a pentomino solution. I even wrote about it on this blog at the time.

Not much else to report about this article. I did some research on how it all worked (lots of mathematics!) and essentially presented that from a layman’s viewpoint. Basically you view the image as a viewport onto a scene. For each pixel in the viewport you trace back the ray of light that produced the pixel value, taking into account reflections from and refractions through the objects in the scene. Lots of computation later, and you have a very photo-realistic image.

In reality, playing with POV-Ray is a hoot. You tweak here and there, defining your objects, their color and transparency, and let it rip generating the image. Rinse and repeat.

This article first appeared in issue 295, June 2010.

You can read the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

This article was just a great deal of fun to write. I wanted to talk about Knuth’s DLX algorithm (“Dancing Links”) as a solution to the exact cover problem. I’d already talked about Sudoku (a great demo of DLX) recently as an article in the mag, so there was nothing for it but to go for pentominoes, one of the other examples Knuth gave. And it gave me a great reason to bring out my old pentomino set that I was given as a teenager and futz around with it. Needless to say I’m still just as bad at solving it as I was then.

Here’s a pentomino set, a beautiful wooden hand-crafted one:

photo © 2009 Jeffrey Bary | more info (via: Wylio)

Actually this is an enhanced version: if you look there’s an extra 2×2 block in the top left hand corner so that you can solve putting the twelve 5-square pieces, plus the extra one, into an 8×8 box. In fact, one of Knuth’s examples solves this exact problem, but with the square block in the center.

About 4 years ago I bought my own wooden set in a 6×10 box – it uses 12 different colored hardwoods for the pieces – because I couldn’t find my teenage set. This sized box is the “usual” problem to solve and there are 2339 solutions. And then, of course, the next vacation I took in England at my parents’, I did find it.

In the article I talked about how you might approach writing a program to solve putting the 12 pentominoes into a 3×20 box (there are 2 solutions). I started off with the brute force method, which is laughable as an algorithm, although doable on modern machines, and moved on to more subtle methods like observing that X or F (the pieces are named after the letters of the alphabet they most closely resemble) cannot be placed right next to the short edges, and so on.

I then talked about the exact cover problem. Suppose you have a matrix of ones and zeroes. Can you select a set of the rows such that when they’re merged together there is one and only one 1 in each of the columns? This is known as an exact cover, and is amenable to a solution that involves a backtracking algorithm. Knuth was the first to notice that you can do some clever recursive stuff with linked lists of linked lists that would help with the housekeeping needed for backtracking, and called the resulting algorithm, the Dancing Links Algorithm, or DLX.

It turns out you can phrase a pentominoes problem as an exact cover (in essence, every square in the box has to be occupied by one and only one square from the 12 pieces) and so is amenable to a solution from DLX. Ditto, a Sudoku puzzle can also be cast into a large exact cover problem.

(Aside: although the DLX paper is still available online, it’s now been published in Knuth’s Selected Papers on Fun and Games.)

This article first appeared in issue 294, May 2010. It also appeared online on the PCPlus website.

You can read the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)