Sorting Stuff with Heap Sort - Part I

I’m starting a small series of blog posts that will explain the Heap Sort algorithm in depth. I’ve noticed that this is an academic topic that few are willing to touch but I am! I hope you find this short series informative.

The Basics.
First, lets get through the basics of any sorting algorithm. A sorting algorithm is an algorithm that seeks to arrange the elements of a data structure (think, a simple List) in a particular order. In most cases, we prefer the elements to be sorted in either ascending or descending order. The efficiency of an algorithm can be measured in terms of its Time Complexity or Space Complexity. The term Time Complexity refers to the amount of time that an algorithm takes to process the input and produce the desired output. The term Space Complexity refers to the amount of space or memory that an algorithm takes to produce the expected result. Generally, the complexity of an algorithm (time or space) is expressed as a function of the size of the problem, n. This is known as the Big-Oh Notation. So, if we were to say that a sorting algorithm has a time complexity of O(n), it means that the algorithm will take a factor of 10 units of time to sort 10 values. If the complexity of the algorithm were O(n²), then it would take a factor of 100 units of time to sort 10 values. Note that I have said that the algorithm will take "a factor of" time because this factor would depend on the particular problem. For example, if we were sorting simple integers, we could expect this factor to be a lot less than if we were sorting strings. Also, the complexity of an algorithm can be specified for Best, Worst or Average case scenarios. A best case scenario for a sorting algorithm would, of course, be if the data were already sorted in the first place. A worst case for a sorting algorithm would arise if the data were arranged in a manner that is contrary to the working of the algorithm. Generally, a good algorithm is measured for its worst-case scenario but in some cases, we also consider the average case.

Heap Sort is an O(nLogn) time complexity algorithm. This is in stark contrast with other sorting algorithms such as Bubble Sort (the unjustifiably most famous sort) which has an average or worst case complexity of O(n²). In my next post, we will dive into the Heap Sort algorithm and find out the reason as to why its called Heap Sort in the first place.

Setting up Code::Blocks on Windows

This blog post is a how-to manual on how to set up Code::Blocks for Windows along with some other libraries such SDL and GTK+.

What is Code::Blocks?
Code::Blocks is an Integrated Development Environment(IDE) for C++. This means that it provides a convenient means for programmers to type and execute their programs. You will need to provide a compiler for any IDE and there are several C/C++ compilers for the Windows environment. Since, this walk-through is newbie oriented, I will simply assume that you do not have any particular compiler in hand.

Setting up Code::Blocks on Windows.
In order to set up Code::Blocks for your Windows OS, go to http://www.codeblocks.org/downloads/5 . You will see two setup files for Windows 2000/XP/Vista. The first setup assumes that you already have a compiler to use with the IDE. The second setup, comes with the MinGW compiler for Windows. Download this setup from its Sourceforge link. Once you've downloaded the file codeblocks-8.02mingw-setup.exe, then do a full install of the IDE. I'm going to assume that the selected installation path for the IDE is C:\Program Files\CodeBlocks. The installation is pretty straight-forward and there should not be any problems. Try creating a new Console Application using the Project Wizard.

Setting up Simple DirectMedia Library for Code::Blocks on Windows.
Setting up SDL for Code::Blocks is pretty easy. Download the SDL 1.2 development bundle from the direct link here. Untar the contents of the file. You should get a folder named something like SDL-1.2.13 and within that folder you should find folders named include, lib, bin etc. Code::Blocks expects to see the file SDL.h within the include folder but as of now, if you look inside the include folder, you will find another folder named SDL. Copy all the header files from within the SDL folder one level up to the include folder and delete the folder SDL. Then, copy the entire SDL-1.2.13 folder to C:\Program Files\CodeBlocks. Now, fire up Code::Blocks and try creating a sample SDL project using the Project Wizard. When asked to specify SDL's location, just provide the path as C:\Program Files\CodeBlocks\SDL-1.2.13. Hopefully, everything should go as planned.

Setting up GTK+ for Code::Blocks on Windows.
Setting up GTK+ for Code::Blocks is even easier. Download the GTK+ development bundle from the direct link here. This zip file is a tarbomb, so neatly unzip the contents of this file to a folder named gtk+-bundle-2.12.9. Copy this entire folder to C:\Program Files\CodeBlocks. Now try creating a new GTK+ project using the Project Wizard. When asked to specify GTK's location, just provide the path as C:\Program Files\CodeBlocks\gtk+-bundle-2.12.9.

const_iterator : Safety or Necessity?

(Reader Level : Beginner)
(Knowledge assumptions : const-correctness, std::vector, iterators)
A while back I asked a senior programmer a very naive but valid doubt.
"Are const iterators used only to enforce safety or are there cases where they could be absolutely necessary?"
In reply, this is what I got and the answer was clear.

#include <iostream>
#include <vector>

class A
{
private:
std::vector<int> _vector;

public:
void Init()
{
   _vector.push_back( 1 );
   _vector.push_back( 2 );
   _vector.push_back( 3 );
}

void Display() const
{
   for(std::vector<int>::const_iterator itr = _vector.begin(); itr != _vector.end(); ++itr)    
      std::cout << (*itr) << std::endl;
}
};

int main(int argc, char *argv[])
{
A a;

a.Init();
a.Display();

std::cout<<"\n\n";
return 0;
}

If we were to try replacing the const_iterator in the Display() function with a normal iterator, the code would simply not compile. This is because the Display() routine is itself const and hence, we must guarantee that no member functions are altered within it. A normal iterator cannot give such a guarantee but a const_iterator can.

Movie Review: Into The Wild

Normally I'm an action junkie when it comes to movies, so its funny that 'Into the Wild' was not an action flick. The basic plot is as follows: After graduating from Emory University, top student and athlete Christopher McCandless abandons his possessions, gives his entire $24,000 savings account to charity and hitchhikes to Alaska to live in the wilderness. Along the way, Christopher encounters a series of characters that shape his life.

Seems pretty boring, right? That's what I thought when I read the plot summary on IMDB but I watched the movie anyway. It turns out that I was wrong and the movie offers some great insights into the philosophy of life and the spirituality that one can gain through adventure. This film is based on a book by Jon Krakauer who wrote about the true exploits of an American wanderer named Chris McCandless. At the end of the movie, you may become a bit cynical (as I did) due to certain developments in the plot. Then I remembered that this is an actual true story and that I was entirely missing the take home message. At any rate, whether you like or dislike this film, you are sure to have several opinions about it. To give it credit, Into the Wild won the 2007 Golden Globe Awards and was also nominated for the Academy Awards. It has also received favourable reviews from most movie critics. The acting, in my humble opinion, was top notch. Emile Hirsch (of Alpha Dog fame) plays McCandless and does a pretty good job. The film was directed by Sean Penn who was also involved in production as well as screenplay. One of the biggest assets of the film is probably its great soundtrack. The music is truly beautiful and it keeps you in touch with each scene. Don't google anything about the film until you've actually watched it. Otherwise you're just ruining the whole experience!

Some links to check out AFTER you've watched 'Into The Wild':
Wiki on Chris McCandless
Official film site

Creating a custom GRUB bootsplash

Creating your own GRUB bootsplash image does not require you to be an artist or an image-editing wizard. It's very easy.
Every GRUB bootsplash image must have the following characteristics:
a) Image format must be of the xpm format. GRUB will load compressed images even faster.
b) Image resolution must be 640x480, irrespective of whether your monitor is widescreen or not.
c) Image can only have a maximum 14 colours. No more.

Armed with these facts, let's go ahead and try to create our own bootsplash image. The image editing software that I am going to use for this purpose is the GIMP (GNU Image Manipulation Program).
First, pick out an image that you really like. The format doesn't matter at this point. It can be jpg, bmp, png, anything you like.

Now open the image in GIMP. Resize the image to a 640x480 resolution. Go to Image->Scale Image and set Width to 640 and the Height to 480. You can tweak the other settings in the same dialog if you want. After that click on the Scale button.

Next we need to make our image only have a maximum of 14 colours. So, go to Image->Mode->Indexed. Click on the Generate optimum palette radio button and set the Maximum number of colors to 14. Now we probably have a pretty ugly looking image. :)

Finally, save the image with extension xpm. You could call it something like bootsplash.xpm. Alright, we've got our image. Let's compress it. Open up a terminal and navigate to the folder where you saved bootsplash.xpm using the cd command. Then type:

gzip bootsplash.xpm

The gzip utility will compress our image and its name gets changed to bootsplash.xpm.gz. That's it! We're done. You can now set it as your new GRUB bootsplash. Enjoy!

By the way, this is what my own GRUB bootsplash looks like.

Mess around with your GRUB menu

GRUB stands for GRand Unified Bootloader. I don't know why, but someone thought that it would be a funny play on the term "Grand Unification Theory" in physics. Essentially, GRUB is a bootloader program that loads when you boot into your PC. Using the GRUB menu, you can then pick your operating system of choice (if you happen to have more than one). I've been using Linux for a while now and today I'll show you how to tweak your GRUB menu settings so that it looks and behaves the way you might want it to. The Linux distribution that I currently use is Kubuntu 7.10. As such, many of the commands that I use may be Ubuntuish.

Let's get started. The options for your GRUB menu are stored in a file named menu.lst. Typically, this file will be located at /boot/grub. Before making any changes to menu.lst, let's first take a backup of the file. Open up a terminal and type the following:

sudo cp /boot/grub/menu.lst /boot/grub/menu.lst_backup

The shell should prompt you for your root password. Once you enter your password, the contents of the file menu.lst will be copied to another file named menu.lst_backup.
Now type:

sudo nano /boot/grub/menu.lst

to take a look at the menu.lst file. I'd imagine the file contents to be something like this.
Any line in this file that starts with a # symbol is a comment. This means that it will be safely ignored when GRUB reads this file.

1. Changing the default OS.
You can change the OS that loads by default in the GRUB menu. In order to do this, first count the entries in the menu starting from zero (not one). Now, locate the line in the menu.lst file that says default<space>n where n is literally a number. Change that number to the entry you want. For example, in order to make the first entry in the list as the default OS to be loaded, change the line in menu.lst to default 0
Save the file and exit the editor by pressing Ctrl+O and Ctrl+X (only for nano). A common mistake that many make is inadvertently change the commented line in the file. If there is a commented line leave it as is.

2. Changing the timeout.
Generally, the GRUB menu gives you about five seconds to decide which OS you want to boot. At the end of this time, GRUB automatically boots into the default OS. To change the timeout, simply find the line in menu.lst that says timeout and change it to timeout<space>n where n is the number of seconds you want to set. I usually set this value to 15. Save the file and exit the editor.

3. Changing the splash image.
Here's a fun customization that you can do. Most GRUB menu screens are purely black with white text. If you want to change the GRUB menu screen to that of a picture, you can easily do that. Get a nice GRUB splash image from the net. You can find plenty under the BootSplash section on http://www.kde-look.org
The grub splash image file should be something like filename.xpm.gz. If your splash image file is not in the xpm format, then it cannot be loaded by GRUB. Alright, now to set this picture as a grub splash, copy it to /boot/grub. Do the following:

sudo cp <PATH_TO_IMAGE> /boot/grub/bootsplash.xpm.gz

where PATH_TO_IMAGE is the logical path to the GRUB bootsplash image file that you intend to use. Now reopen menu.lst with root previleges.
sudo nano /boot/grub/menu.lst

Add a new line to this file (preferably after the initial comments):
splashimage /boot/grub/bootsplash.xpm.gz
Save and exit the editor.
Now everytime you boot your system, you should see the pretty new GRUB splash image instead of that boring dark one!

NOTE: If at any point, you realise that you've messed up your menu.lst file, then just retrieve it from the backup that we had first created.
Type:

sudo cp menu.lst_backup menu.lst

Kubuntu 7.10 CD request

I feel quite happy today because the Kubuntu Gutsy CD that I requested from Canonical has arrived. I requested for the 32-bit version of the CD on the 7th of March and today is April Fool's. So, it totally took little more than three weeks to deliver the CD. I figured that since I lived in India which is quite some distance from the US, I'd at least have to pay for the shipping charges. The truth is that I didn't have to pay a dime, no shipping charges - nothing! A friend of mine told me that he had also got some free Ubuntu stickers along with his CD request. I didn't but that's okay because now I can make my own stickers. :D

https://shipit.ubuntu.com/