Wednesday, July 29, 2009

Travelling Salesman Problem is NP-complete

It's been a while since I was last in a classroom studying computability and complexity.

This is one of the most interesting results and it's worth remembering.

The TSP is described succinctly on wikipedia:

Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.

The key is that you have to visit each city exactly once and that it should be the shortest such tour.

Find a lot more about the TSP on wikipedia. And if you don't know what NP-complete is, here is the wikipedia page.

Why is this important? As software engineers and programmers, we should be aware of the limits of what we can do with our craft.

little tidbit on polymorphism in C++

Here's another interview question that I've come across:

Polymorphism in C++ is supported with the use of dynamic binding with the use of virtual functions.

There are two things to do when you want to use dynamic binding:

  1. Only member functions that are declared virtual are dynamicallly bound.
  2. The call must be made through a pointer or reference to a base class.

When these conditions are met, the function call is dynamically bound. Otherwise, the function is resolved at runtime. And dynamic binding is how C++ supports polymorphism. (Although I believe templates support a different kind of polymorphism, dynamic binding polymorphism is what people mean when they simply say polymorphism...)

Tuesday, July 28, 2009

how to check CPU and memory usage on a Linux box

I was asked this question once on a job interview. The interview was supposedly for a C++ developer role but they were considering me for a Linux/DB admin job. (Not really sure why. :)

I answered top because that was the only command I ever used on my Linux boxen. And after the interview, I remembered the uptime command.

So I finally decided to figure out what a good answer would have been in addition to those two commands.
And the winner is:


The most important fields here are:

  • free - amount of physical memory not in use

  • id - percent of CPU time that is idle
  • wa - percent of CPU time spent waiting for IO

Tuesday, July 21, 2009

vim sort lines

This is actually very easy. All you do is:


If you only want to keep unique lines, do the following:

:sort u


Wednesday, July 15, 2009

Using ffmpeg to convert video files for the PSP

Well first you have to install ffmpeg. I will save that for another post.

Let us assume that your ffmpeg is capable of encoding for the PSP platform. The command to convert to a PSP format is:

ffmpeg -i yourfile.avi -f psp -r 29 -b 768K -ar 24000 -ab 64k -s 320x240 M4V00001.MP4

To be honest, I'm not really sure what the parameters mean. (Again, save for another post :). But this command works for me. One thing of note is the -s parameter which refers to the size. The PSP format needs both dimensions to be divisible by 16. You can use -s 368x208 for widescreen videos.

To create the thumbnail file:

ffmpeg -i yourfile.avi -f image2 -ss 5 -vframes 1 -s 160x120 M4V00001.THM

The -ss parameter refers to which frame to use. I believe the units for this is seconds.

Stay tuned for more PSP/ffmmpeg posts. I will also post how to convert using mencoder

Monday, July 13, 2009

google front page!

The admittedly simple post, String Concatenation In Bash, has made it to the front page of google when searching for "bash string concatenation."

Here's proof. w00t. Not bad methinks. Not that I get a lot of traffic on this blog but I like to keep it going for personal satisfaction. :) And to save (and share) a lot of the little things that I learn along the way.

subversion: backing up your repository

Here's a simple way to do it:

svnadmin dump /path/to/repo/ | bzip2 -c >

Monday, July 6, 2009

vim paragraph reformat (justify or align)

I like editing my plaintext files (and some of my source code) at

:set textwidth=78

The problem is that vim does not automatically justify or realign when adding/deleting text. The simple way to do it is to select the lines to format and use:


Note that since gq is an operator that you can use other ways to select the text to format, but visual mode is the most intuitive for me.

You could for example do this:


The downside is that you'd have to know the line count. A more useful text movement command to use with gq is ) (which moves you to the end of the current paragraph. So you'd do this:


Friday, July 3, 2009

how to eject stuck cd/dvd in linux

I'm using Opensuse 11.1. And it refuses to eject a DVD data disc I have inserted. This is the method I used to eject it.

First, find which processes are accessing it using the lsof command (lsof stands for list open files.) On OpenSuse 11.1, I used:

lsof /dev/sr0

This gave me the PID of the "offending" process. Which I was able to kill. Then eject as normal.