IEEEXtreme Competition 2011

This post is just a brief nod to the IEEEXtreme Competition that I took part in at the end of last year with a couple of like-minded students at my university. Queen Mary, University of London were kind enough to host the participants from Imperial College. (Unfortunately just a single team, since the others didn’t manage to get their registration through in time!

The event was a gruelling but undoubtedly challenging and enjoyable 24 hours of programming solutions to a range of small problems given to us by the competition organisers. Alas, we were restricted to C++ for our solutions (the lesser of two evils when compared to Java), but considering than myself and one of the two other team members were far from regular users, I thought we did a fair job of coping. (We were constantly refreshing ourselves on much of the basics!)

The results were published not too long ago, and I must say I was amazed we managed to rank as high as 71 overall (out of some 1,500 teams). In fact, I gather we were somewhere in the 20s at one point, but evidently slipped dramatically when we all lost the desire to keep going about four hours from the end.  What’s even more astounding is that our lone Imperial College team managed to rank first among the teams from the United Kingdom. Admittedly, this says more about the popularity of this relatively new contest in the UK, especially when one notes how many British teams entered. Eastern European countries unsurprisingly put forth a host of participants. Still, I was moderately pleased with our effort. Our phenomenal team spirit more than made up for any shortcomings, of course.

Oh, and as it turns out, a power outage in that area of London induced a delay of some two hours, mainly spent dashing around the campus. The fire alarm and standing around in the freezing area wasn’t much appreciated, though I doubt it affected our success in any real way. Though that isn’t what I’ll be telling the electricity company, of course, when I claim full competition-related damages.

Most annoyingly of all during the marathon competition, there was a singularly irritating problem relating to dynamic programming that none of our team was able to solve throughout the event — despite persistent efforts and the fact that the great majority of other team had no problem! The contest had its faults too; the arbitrary swings in difficulty level of many questions often took us by surprise, as the times taken for us to fully solve the questions ranged from 20 minutes to 5 hours to never. I hear most were rather better specified than their counterparts from last year, however.

In all, my day of IEEEXtreme was a perversely enjoyable exercise in frantic coding and sleep deprivation. Probably not one I’ll repeat in its current form (even if I were still in university), but not one I’d take back either. I daresay I’ll be revisiting the similar but less biologically demanding Google Code Jam contest this year, only to fail utterly in the second one, when facing up against some truly super-human competitors.

The Hardest Logic Puzzle Ever

Some time ago I wrote a post about the well-known logic puzzle of The Traveller’s Paradox and attempted to derive and justify a solution using the formal methods of propositional calculus (zeroth order logic). I return today to another intriguing and somewhat challenging problem within the realm of mathematical logic, albeit with what I hope is a much clearer approach and argument.

Although “The Hardest Logic Puzzle Ever” is scarcely a logically verifiable statement, the puzzle does indeed have a reputation as a rather tricky logic puzzle (at least among those encountered by laymen) and in any case has a non-trivial solution. The problem has some notable names attached to it, having originally been published in The Harvard Review of Philosophy by the logician George Boolos, but originating with the popular mathematician Raymond Smullyan, and altered slightly by the late computer scientist and AI pioneer John McCarthy.

The puzzle is commonly stated as follows.

Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, in some order. You do not know which word means which.

At first glance, the problem may appear insurmountable due to the behaviour of god C, yet when we notice that his behaviour is not truly random, but rather only his veracity is — he otherwise follows all rules of logic. Boolos clarified: “Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.”.

Encountering this puzzle for the first time just in the past week, I made an effort to solve it on my own using a formal approach, as much as possible. As it turns out, I had some success, and hence thought I might share my reasoning here in the form of an article.

Let us begin by setting up the puzzle in the standard language of propositional logic (that is, Boolean algebra). We first define our useful propositional variables and predicates, which are

• $R$, whether the da response corresponds to yes (absolute truth). $R$ is thus true if da means yes and ja means no, and false if da means no and ja means yes;
• $T$, whether a given god (we consider them independently) is telling the truth. Note, this has a well-defined value even for Random (god C), since the context is a specific question and corresponding response.
• $Q$, the question (propositional predicate) that is asked to a given god.

Note that the latter two variables are semantically valid within only within individual questions. However, because we shall only utilise them within the context of question-response pairs, we need not concern ourselves with this.

There is a number of ways to convert the verbal problem statement into a set of formal logical expressions, but I shall adopt a fairly direct and unambiguous one here. We start by noting two simple facts regarding the truthfulness of a particular yes-no response $A$.

\begin{aligned} T &\rightarrow (A \leftrightarrow Q) \\ \neg T &\rightarrow (A \leftrightarrow \neg Q) . \end{aligned}

Note that the biconditional ($\leftrightarrow$) can be interpreted as material (syntactic) equality. This is precisely equivalent to the non-fundamental XNOR ($\oplus$) operator in propositional logic. With a bit of manipulation it can be shown that

$A \leftrightarrow \neg (Q \oplus T) .$

In other words, the yes-no of any response shall be the absolute (true) answer to the question XNOR whether one is asking a truth-teller.

We must then note the complication to the puzzle introduced by the fact we do not understand the language of the gods. ‘da’ could mean either yes or no and ‘ja’ conversely. To account for this, we can write two more statements specifically about the da-ja response (denoted $B$), which take virtually identical forms to before;

\begin{aligned} R &\rightarrow (B \leftrightarrow A) \\ \neg R &\rightarrow (B \leftrightarrow \neg A) . \end{aligned}

Unsurprisingly, this can be rewritten in the same way to use the XNOR operator;

$B \leftrightarrow \neg (A \oplus R) .$

Note that the value of $B$ represents the actual response; that is, it is the single observable of the logical system we have constructured to represent the puzzle.

While we could restrict ourselves to the use of the primitive Boolean operators (AND, OR, and NOT), the use of the XOR operator here facilitates things considerably, due to its special properties (notably commutativity and associativity) and the simplicity it gives our theorems.

Now, combining the two expressions (theorems) for $A$ and $B$ (this can be seen easily by considering the biconditional as equality), we can factor out the negations and use associativity of the XOR operator to write

\begin{aligned} B &\leftrightarrow \neg (\neg (Q \oplus T) \oplus R) \\ B &\leftrightarrow Q \oplus T \oplus R . \end{aligned}

We now have an easily manageable form for the da-ja response of a given god. The question now becomes, how do we extract the absolute truth value of the response from this observable variable? Clearly, one has no control over the $T$ and $R$ variables, which are predetermined by god being asked the question (and possibly by the flip of a coin) as well as the language of the gods. However, we do have direct and full control over the question to ask, the predicate $Q$.

In order to extra meaningful (absolute) truth value we first note that any propositional variable XNOR itself is false, thus disappearing from its containing expression. Given that we wish to eliminate the variables $T$ and $R$ from the final expression, we can decompose the predicate $Q$; that is, give it an explicit form.

Let $Q = Q' \oplus T \oplus R$. Hence, we can say

\begin{aligned} B &\leftrightarrow Q' \oplus T \oplus R \oplus T \oplus R B &\leftrightarrow Q' \oplus (T \oplus T) \oplus (R \oplus R) B &\leftrightarrow Q' . \end{aligned}

At this point we almost have a solution to the puzzle. We have shown that one can obtain an accurate true-false response to any question we wish to ask any god. As long as we ask a question of the form $Q$, then a response (effectively to question $Q'$) of ‘da’ always corresponds to truth and ‘ja’ always to falsehood.

There are a number of ways to use this to reveal the identities of the three gods. The simplest and most direct, I feel, is to ask gods A and B whether they are Random. This definitively indicates the Random god (since if both answer in the negative, then it must be god C by elimination). One can then simply ask either of the remaining gods (not Random) whether he is True, deducing the identities of the True and False gods in a single question. Hence, we have totally and provably solved the puzzle within the desired three questions.

Losing faith in Apple

The iPhone 4S model was released by Apple just under a month ago here in the United Kingdom. Having gotten over the general disappointment of a late (delayed?) release and no new hardware (the widely-rumoured iPhone 5 model), I was soon excited by some of the new software features offered by iOS 5 on the new iPhone model, most notably the advanced voice recognition system Siri. The much-improved processing power, not to mention updates to the camera and external antenna were also appreciated, though in some sense just reaffirmed what the more demanding technical consumers were expecting in the original iPhone 4 release.

Four weeks later, and I’m still sitting here with my two-and-a-bit year old iPhone 3GS. I was due for an upgrade on my O2 contract just a week after the initial release, and contacted both O2 directly and my local Carphone Warehouse retailer to find out what the status of this upgrade was. Apparently, not only was the retailer entirely out of stock of the new iPhone 4S (in its warehouses or otherwise), but they had no word on when any further shipments would be arriving soon. In the ensuing three weeks, I’ve made the personal effort of checking for new stock updates every few days, only to be told that a new delivery should be coming soon. Besides a brief restocking a week ago (that didn’t include any of the 64 GB versions), I have repeatedly and consistently been told to come back and enquire again in a few days regarding stock. Now, it’s hard to blame this on Carphone Warehouse, since every employee I spoke to seemed about as perplexed as me.

To me, the simple fact that Apple has failed to sufficiently stock one of their primary UK retailers with the new iPhone model for almost 4 weeks now is absolutely shambolic. I mean, how can one of the largest companies in the world, which prides themselves on customer satisfaction, make such an atrocious mess of logistics? It’s not like Apple has just entered a technology sector with a minor new product no-one has heard about or might consider buying. While undoubtedly initial sales figures for the new iPhone have been quite impressive, I can’t help but think Apple has severely damaged customer relations in the UK, if not suffered a notable loss in sales. At this point in time, I’m really struggling to find that irrational love for a company that so many Apple fan-boys have latched onto over recent years. Sure, my current phone is an older iPhone model and my laptop a MacBook Pro, but I bought these products mainly because they far ahead of the field at the time of release and merited their price tags. With outstanding-looking Android phones currently on the market, and some impressive Windows Phone 7.5 models just released, I’m quickly rethinking whether to let myself be led around by Apple any more.

In short: get your act together, Apple, and don’t expect to remain the dominant player in consumer technology whilst sitting there and twiddling your thumbs. You’ve done of good work to earn the respect of millions of users throughout the world (not least through clever marketing), but realise that you’ve no god-given entitlement to keep it in the future.

Starting Tutoring

So this is sort of an overdue update where things are with my life, as well as a bit of self-promotion for the work I’m going to be doing over the next 9 months or so…

The first thing that needs to be mentioned is my total relief at no long being a student of physics. Well alright, it wasn’t all that bad. To be fair, there were many parts of my degree I enjoyed, yet unfortunately my current feelings seem to be dominated by a few painful lecture courses and exams! In any case, I am now happy to announce that I’ve graduated with 2:1 honours in theoretical physics at a world-class university.

Before I commit myself to the unavoidable drudgery of a full-time career, or more likely (given my talent for procrastination) a PhD course, the plan is to take a very non-committal year out — post-university gap year if you like. More on future plans to come in another post, but for now I wanted to mention that I’m going to be doing some part-time month over the coming year. Specifically, I will be working as a private tutor in the areas of mathematics, physics, electronics, computing, and English language/literature. My plan is to do this on an ad-hoc basis alongside other potential freelancing work. Learning and particular pedagogy is something I’m very passionate about. For anyone that may just happen to stumble across this post, I am offering to tutor secondary school students as well as adult learners in the N/NE London and SW Essex regions in these subjects, focusing on GCSE and A-level courses, but willing to accommodate to other courses.

If you’re at all interested, you can check out my profile on First Tutors. Feel free to contact me either via the contact form on this website, or via the First Tutors website.

Installing Windows 7 from an Upgrade Disk

Just a month or so ago now I received my shiny new MacBook Pro. While the matter of a long-time Microsoft fan selling out his soul so easily is the subject for another day, it is worth mentioning that I did not (indeed could not!) ditch the Windows operating system. My initial thoughts were fairly optimistic – all Macs now come with a utility called Boot Camp, which provides official support for installing a full copy of Windows alongside the existing OS X installation.

My problems, however, began when I started to read the Boot Camp installation guide. To my horror, in a clear notice in the guide, I was told that only a full installation disk for Windows can be used to install a Boot Camp (Windows) partition on the machine. Now, having long used Windows Vista on a previous laptop (which I was in the process of retiring), and given my purchase of a Windows 7 Ultimate upgrade disk less than a year earlier, I was most reluctant to shell out another larger sum of cash just to get Windows 7 running on my MacBook Pro. As it happens, my stubbornness insisted that I proceed with the Boot Camp installation anyway. (A few quickly researched articles online seemed to suggest I might have luck doing this.) In fact, I managed to use the upgrade disk to get as far as the verification code screen in the setup, before I decided things weren’t going to happen. Long story short: I played around with things for a while, eventually found a Microsoft support number to call, and had a very helpful and knowledgeable support technician guide me through the end of the installation and activation process.

As there appears to be minimal information regarding this process online, I thought I would post a short set of instructions here for all who are interested. Myself, I was much reassured to know that it is possible to make a clean installation of Windows (7) from an upgrade disk and activate the copy. While I have not tried the process on a machine other than my MacBook / outside of Boot Camp, I was reliabily informed that the process is no different. These are the steps to follow:

1. Insert the Windows Upgrade disk.
2. Follow the setup wizard and select the “clean install” option.
3. Windows should proceed to install successfully, and after a few reboots, you will reach the license key screen.
4. Leave the box for the license key blank and continue.
5. The installation should complete and you should be able to temporarily use Windows in “trial” mode (unactivated license).
6. Reboot the machine with the upgrade disk still in the drive.
8. The setup should proceed to perform an “upgrade”. In fact, you are just “upgrading” Windows 7 to Windows 7 (in my case) – this is required for the sake of license activation.
10. Open the Computer Properties window (Control Panel\System and Security\System).
11. At the bottom of the page is the Windows activation section. Select the “Change product key” option.
12. Enter the product key for your Windows Upgrade disk, and voila, you should have a full licensed copy of Windows in your machine.
13. (If the previous activation step did not work, try the phone activation upon failure, which is virtually guaranteed to succeed.)

While this process is somewhat non-intuitive and poorly documented, it is nonetheless quite possible. (I suspect there may be a loophole that allows customers of only upgrade disks to install full licensed versions of Windows, which explains the lack of information on the matter.) Either way, I hope this short guide helps save others the moderate amount of pain and trouble I had trying to work around this issue myself! I would be pleased to hear of any other success stories.

Musical Gem of the Week #15

Portrait of Tomaso Albinoni, to whom the piece is commonly misattributed.

Moving forward in time to the 1950s, we return with this piece to the style of Vivaldi and Bach. Albinoni’s Adagio in G minor was for some time thought to be be a work of the well-known 18th century Italian composer Tomaso Albinoni, yet is now accepted as a Neo-Baroque work of the modern biographer of Albinoni Remo Giazotto (with just perhaps some inspiration from an original Albinoni manuscript). The name and common attribution have nonetheless stuck, even to this day.

Though often described as a musical hoax, passing off a work as one by a famous master was a relatively common practice by lesser-known composers from the 19th century onwards, done in order to gain widespread recognition. In this sense, Giazotto has certainly succeeded, but moreover, he has created a masterpiece of modern classical music and an unforgettable melody of sombre.

(Performed by the Leningrad Chamber Orchestra.)

Astronomy Picture of the Day on your Desktop

It’s a universal fact that computer wallpapers never stay fun for long. No matter how pretty the picture is, staring at the same desktop each day can get a little tiresome. (Okay, so if you’re anything like me, the desktop is continuously obscured by masses of windows, but we all know that’s irrelevant.)

AE Aurigae and the Flaming Star Nebula. Image Credit & Copyright: Rolf Geissinger.

NASA have for years now run the wonderful Astronomy Picture of the Day website, featuring a new (and almost invariably stunning) image of outer space or some astronomical phenomenon – from our own moon, to neighbouring planets, stars, and galaxies. Even better these days, the pictures are inevitably high-resolution, making them ideal for desktop wallpapers.

As it happens, some clever guy came up with the idea of creating a program to run in the background and automatically update your desktop each day with the latest astronomical picture, published by NASA on their website. The application, called APOD Wallpaper, is available to download and install on your Windows machine, and having used it for roughly a week now, I can already highly recommend this handy little app. As a student of physics (and someone with a particular interest in astrophysics and cosmology), this has quickly become a must-have for my laptop; yet who could not appreciate the beauty of these pictures?

May you never tire of your desktop again!

Update

Having just gotten hold of my lovely new MacBook Pro, I’ve had a chance to play around with getting an automatic APOD wallpaper on OS X too. As it turns out a certain scripting guru (Harold Bakker) has written a script to automatically update the OS X desktop wallpaper with the latest APOD and has kindly put it on his website. It’s slightly less trivial to setup than the Windows app, though he provides clear instructions on how to create a cron job for automatic updates… it’s been working perfectly for me so far!

Musical Gem of the Week #14

It’s been some time since my last installment in this series, but despair not, there is more to come — beginning with a new modern masterpiece. Let me also say that I fully intend to restore a bit of regularity to this series!

Joaquin Rodrígo is arguably the greatest composer in the history of Spanish guitar music, though it was far from all he composed. His life, spanning almost the entirety of the 20th century, produced two great and enduring works. The more popular is the Concertio de Aranjuez, but it is his Fantasia para un gentilhombre, which I prefer and which I wish to introduce here. The name literally means “fantasy for a gentleman”; the gentleman in question here being the virtuoso guitarist Andrés Segovia. The piece itself draws inspiration from Spanish folk music, retaining both its lively and lyrical characteristics while making superb use of the classical orchestra. All in all, a true delight.

Watch and Listen:

1st Movement, Villano y Ricercare

2nd Movement, Españoleta y Fanfare

3rd Movement, Danza de las Hachas

(Performed by Narciso Yepes.)

(Unfortunately I couldn’t find any freely available download, so YouTube will make do! If you’re looking for a good performance to buy though, I can definitely recommend one by Pepe Romero and the Academy of St. Martin in the Fields.)

KD-Trees for .NET

The kd-tree is a well-known data structure, which alongside quadtrees and octrees, is commonly used for the task of space partitioning. That is, it aims to represent a set of points in k-dimensional space in a way that is efficient to access. Kd-trees, as do all binary trees, have the notable advantage of an $O(\log n)$ average search time, far superior to the naive $O(n)$ search.

While such trees perhaps have their best known application in computer graphics, I discovered them here in relation to a computational physics project on which I am currently working. For those who are curious about the context, I have recently been doing some statistical analysis on the distribution stars using the Hipparcos catalogue. Unfortunately due to sheer number of stars (100,000+), performing a nearest neighbour search or range search on each star in 3D (Euclidean) space is simply infeasible without the use of a clever algorithm. This is how I discovered the wonder of kd-trees, reducing a task that would otherwise take days to several minutes.

The software I am writing for this project happens to be in C# 4.0, and upon a bit of investigation, I discovered that there exists no (decent) implementation of the kd-tree structure and its algorithms for .NET.  Thus, with a bit of help from the Wikipedia article and a paper I dug up, I decided to have a go at a generic implementation. Now that it is complete and tested, I can gladly declare that the job was not half as easy as I expected (but somehow quite rewarding)!

The following features have been implemented (and fully documented with XML comments).

• Tree construction
• Dynamic node removal
• Nearest neighbour search
• Range search

I’ve now uploaded the complete code for the implementation, which is available below as several C# code files. Note that you will also need the (wonderful) Math.NET Numerics library to compile things – it provides the generic vector type and a few other handy things. (You can probably adapt the code easily enough if you don’t fancy having  this dependency.)

KdTree.cs

KdTreeNode.cs

Arithmetic.cs

Tests (MSTest framework)

KdTreeTests.cs

The idea is that the KdTree class is available to use as a black box, so let me know if anything is unclear. (If you’re wondering though, the arithmetic stuff is there to provide generic arithmetic support complementing the generic vector support. You’ll probably just want to use double most of the time.) Finally, if you’re interested in the unit tests, you can grab them over at the project repository. Enjoy.

Films to remember

With far too much free time on my hands of late, I must confess that immersing myself into the world of film became something of a habit. Alas, such days were rather short-lived; yet they have inspired me to publish this (much overdue) article.

Now, while I wouldn’t exactly describe myself as a film buff, it is certainly an art form of great interest (not to say entertainment) to me.  Though it is true I do tend to stay clear of a certain few types of films (viz. slashers, farcical comedies, and chick-flicks), I do like to think my knowledge of recent cinema (what, 1960s onwards?) encompasses a notable range. Not that it matters of course, for you will likely judge for yourself!

Unfortunately, since there are far too many films on my list of favourites to go into even the briefest details, I have but given a simple list of them. Let me also make clear that the themes, styles, and tones of these films do vary rather wildly – the list is not meant to be cohesive nor complete, and indeed the grouping by genre is a bit arbitrary. All the same, it is my strong belief that any one of these films is worth the time (and more) watching it, and perhaps even pondering the thing. While of course they may not all carry deep messages about life and the universe, their ability to open and enlarge the mind is unquestionable.

Romance

Any further worthy entries I encounter (or remember) will definitely make their way onto this list! (I would admit the Comedy section is a tad brief.)

Oh, and needless to say, I myself am always looking for suggestions for what to watch next. (We all know sifting through garbage for the rare gemstone isn’t fun, right?) Readers of the informed and sharing variety are encouraged to leave comments.