smert.net

Recently I’ve bought another PC which I’ve started using in place of my laptop while I am at home. I’ve decided to switch my laptop back to a machine for testing. I like trying other Linux distributions and I don’t care for testing them out using virtualization. Once I get a feel for it on a actual machine it is a lot easier to test and revert to a previous state using VMware Server or VirtualBox. Since I’m using it for testing again I decided to put several distributions back on it. At one time many months ago I had installed Windows XP (with Microsoft Shared Computer Toolkit which is now called Windows SteadyState), Windows Vista, FreeBSD, CentOS, Fedora, Mandriva, OpenSuSE, Slackware and Ubuntu. That didn’t last long because I was actually using that computer and I didn’t want to make major changes to it when newer versions of the distributions came out.

Read more

There is very popular web comic called XKCD. The site seems to have been around since January of 2006 and I’m sure that anyone that reads Digg or Reddit will be familiar with them. I visit there from time to time and even have a couple of their comics taped to my desk at work.

A few weeks ago Jordan brought up one in particular because of a job listing for a “consulting and software development firm”. The comic is a bit old and is from earlier this year in July. In the job listing they had a programming exercise referring to that comic and wanted it to work on multiple data sets read from a file. The problem in the comic is np-complete. If you aren’t familiar with that term than you might want to read up. Quoting the article on nist.gov below.

Note: A trivial example of NP, but (presumably) not NP-complete is finding the bitwise AND of two strings of N boolean bits. The problem is NP, since one can quickly (in time ?(N)) verify that the answer is correct, but knowing how to AND two bit strings doesn’t help one quickly find, say, a Hamiltonian cycle or tour of a graph. So bitwise AND is not NP-complete (as far as we know).

Read more