How my car was mowed down by a truck...

Actually my car was not mowed down, but it was damaged badly. This is a delayed post. The incident happened on March 08.

What happened was that i had gone with my friends and my wife to jaipur. And on the way back, we were in peak traffic. After driving for around 250 kms, We were around 2 kms from home and we were standing at a red light. There was a truck (not the big one, just a small one) on our right and lots of bikes on our left. We were waiting for the red light to turn green. After the light turned green, i just stood still allowing the bikes on the left to more out of my way. At that exact time i felt my door moving. I turned right and saw that the door was bending at an absurd angle. Actually it was coming off. And then my friend's wife from the back seat notified me that something was wrong. I looked up and saw the truck pushing my driver side door and trying to take it off with it.

My friend got down and asked the truck driver to move back. There were tons of vehicles behind us and all of them were honking. Also note thatthere was a police chowki just 10 meters from where the accident took place. No one got down to help us. Not even the respected police men. Anyways, the brawl started. My brain boiled with anger. After the car and the truck were unentangled, we got the truck to cross the red light andstop at the side of the road. I drove my car and stopped it right in front of the truck. And then joined the brawl.

The truck was having 1 driver and 4 passengers - all sqeezed in the tiny space at the front of the truck. We got the driver to come down. We could see a policeman coming. First of all, without even having a look at the vehicles, the policeman was sure that i was the culptript. Maybe that was because - i was the wealthier party and would have been able to oil his hands well (make a better offer to him for letting the matter dissolve). But when he saw the car, he was sure that the truck was at mistake. And as soon as he realized that he could not make anything out ofthis matter, he simply disappeared - leaving us to take justice in our own way. Why do the hell i pay my taxes then, so that the policeman would leave me without support at the time of need. This happens in india only - i believe.

I was so angry that i offered the truck driver my car. I told him that you take my car and get it repaired and give it back to me. I would drive around your truck for the time being. The truck driver was just trying to comprehend was i wanted to say. Anyways, after lots of argueing and haggling, the truck driver fell to my knees and asked me to let him go. And i did that in return of just Rs 2000/- so that he can go ahead and mow down someone else's car. I would like to extend my appologies if any truck by the number UP-21-N-0568 mows down another car.

The next day was another fight to figure out the cheapest way to get the car back in shape. I went over to Shiva motors - the authorized dealer for GM cars, and they gave me a quote of around 60,000/-. I was shocked. My heart stopped for a moment. They wanted to replace both the righthand side doors and the front bumper along with paint job and labour. I also went to another "bajaj allianz" authorized workshop and they gaveme a quote of around 30,000/-. My insurance is from bajaj allianz - so i was basically looking for the cashless facility.

By chance i came across a workshop in noida sector 5 "Kashyap auto works". They took a look at my car and told me that they would arrange all the parts and it should cost me around 25,000/-. I said ok, cause this was the best deal i had got. I intimated the insurance claim to bajaj allianz and left my car at the workshop. The surveyor from Bajaj Allianz came and saw the car - took photos. It took them 2 weeks to repair the car along with labor and new parts. The door cost me around 5000/- and the beading and handle of the door cost me 3000/- The total cost came to be around 15,500/-. I claimed and got 80%. But i lost my no claim bonus for the next year.

The morale of the story is, stay as far away from a truck as possible while driving. The indian police only steps in when they see a probability of making some money for themselves. Prevention is better than cure.

parking

Jaipur - the pink city

Why is jaipur known as the pink city - cause all houses there are colored pink. I had the opportunity of visiting jaipur this on 7th & 8th of this month (March 2009). We started early from New Delhi (Indirapuram to be specific) - around 6 am. We had thought that we will start at 5 but we got delayed. If we had started earlier, we might have got lesser traffic and lesser trucks.

The NH8 passing through gurgaon is great. It is a very smooth road and very wide. You can easily drive at 150 kmph. The only problem is that there are two-wheelers (which are not allowed - but in india who cares). And they drive at the middle of the highway at 40kmph. So, you got to be careful of them.

We had breakfast at The jungle Babble at Dharuhera. The breakfast was terrible. It used to be a nice resturant earlier, but now it seems that it has lost its charm. There are around 4 toll gates between delhi and jaipur and tons of slow moving trucks. Lots of impatient people driving their wagonrs at 120 kmph.

We reached jaipur at 12 pm. The jaipur city is a very small and crowded city. Very confusing - if you are there for the first time. You will find it very difficult to drive if you have a long car. Majority of the people are in rickshaws and in cycles. And the city was hot.

It took us an hour to find our hotel Umaid Bhawan- which we had reserved from yatra.com. It is a very small and nice hotel. We found it to be worth our money. The food was costly - as we had expected. But the rooms were very nice. It is worth a visit - for low budget accommodation. It is in a residential colony and is very quiet.

It is advisable to get a taxi/cab for moving around jaipur. If you drive your own car, you are bound to get lost and fined by the cops who are always on the lookout for non-local people for their "under table" income. But again dont get a cab from the hotel. Do some research and have some contact of cab drivers before going to jaipur. A cab from the hotel would cost you twice the original rate. We did the mistake of getting a cab from the hotel itself and we got an ambassador - whose top speed was 40 kmph. We drove in style.

The best shopping place in jaipur is near the hawa mahal. But that market is very costly. If you cross the crossroad near to the hawa mahal and go to markets behind the front shops, you would land in the whole sale market of cloth and other stuff. Get your stuff from there. It is cheap and nice.

The only things of historical importance/worship places worth looking in jaipur is "birla temple", "hawa mahal", "jal mahal" and "amber fort". Amber fort is huge. If you cannot climb to the top of the fort, you can take your car up to a parking place behind the fort and enter the fort from there. You can also hire an elephant to take you up. But it is better to go by foot and enjoy the view. There are lots of restoration work going on in amber fort. But the fort is huge and really worth looking. Dont forget the visit the underground surang near the exit from the fort.

Another place worth visiting is the "chowki dhani". You might have heard a lot about it. Jaipur without chowki dhani is half the trip. Well, chwoki dhani is around 20 kms from the main city - it is outside the main city. Better take a cab, because parking is a major problem. It is a type of village mela in the night with beautiful lighting and lots of village stuff like elephant ride, boat ride, camel ride, astrology, magicians, dances, puppet shows etc etc. The entry fee is 300/- per person which includes the diner. There are lots of stalls for eating chat/gol-gappa and they charge 10-20 rs. Rides also charge the same. There are some huts where you can sit and feel the atmosphere of a village hut. Enjoy the food cooked on the fire inside the hut - village style.

Diner is all veg but there are two options. Either you sit down on the ground and have it village style. Or you sit on a chair and have it. It is better if you go for the later option. Sitting down on the ground is something that we indians used to do long time ago. If you are not in the habit of sitting on the floor for long duration, you might find it tiring and uncomfortable. You might not be able to enjoy their food if you sit down. Better sit on table-chair system and enjoy the food.

Chowki dhani is also a resort and offers stay. But it is preferable that you do not stay there cause, then, going and coming from city would be a pain. And secondly their service is not that of a 5 star (though they claim that they are a 5 star).

While returning you should be leaving jaipur by 12 pm. That ways you would avoid the evening rush and traffic jams. We got stuck in a traffic jam near behror and it cost us an hour to get out of it. Better leave at 12 and have lunch on the way and reach delhi by 5 or 6 pm.

VIM improvements

If you have vim 7.x version, you should know that vim supports auto completion for certain languages like c, php, python, html, css, xml, javascript.



To enable autocompletion in vim, you need to create a file in your home directory

$ vim ~/.vimrc

Copy the following code into this file

autocmd FileType python set omnifunc=pythoncomplete#Complete
autocmd FileType javascript set omnifunc=javascriptcomplete#CompleteJS
autocmd FileType html set omnifunc=htmlcomplete#CompleteTags
autocmd FileType css set omnifunc=csscomplete#CompleteCSS
autocmd FileType xml set omnifunc=xmlcomplete#CompleteTags
autocmd FileType php set omnifunc=phpcomplete#CompletePHP
autocmd FileType c set omnifunc=ccomplete#Complete

And save the file.

Now open your file in vim and check out autocompletion

$ vim mycode.php

For autocompletion press Ctrl-X O. You should be getting a dropdown of available functions/variables and on the top of the screen a definition of the selected function.

Another thing that could be done in vim is tabs. Yup check out the following commands

:tabe oldfile.php - open oldfile.php in new tab for editing
:tabnew - open a new blank tab
:tabn - go to next tab
:tabp - go to previous tab
:tabr - go to first tab
:tabc - close current tab
:tabo - close other tabs

Coding is fun!!!

upgrade nvidia drivers on ubuntu 8.10

So, you have an nvidia graphics card and you want to enjoy the high resolution and smooth graphics that comes with nvidia. You want to see the eye-candy graphics on kde 4.2. Firstly when you install ubuntu, you might not get the nvidia drivers enabled by default. So get and install the default driver available with your ubuntu version install "envyng".

$ sudo apt-get install envyng-qt

Now this is an utility that installs the stable version of nvidia drivers compatible with your version of ubuntu. To install the driver run the program

$ envyng -t

Follow the on-screen instructions to install the driver. You would probably get driver version 177.82. for nvidia. Once the process is complete, restart the computer. Now you should be getting better graphics.

There are people like me who are not satisfied with the latest stable version of driver. To upgrade to the latest version of driver first download it from the nvidia website.

For 64 bit ubuntu you can go to:

ftp://download.nvidia.com/XFree86/Linux-x86_64/

And for 32 bit ubuntu you can go to:

ftp://download.nvidia.com/XFree86/Linux-x86/

For my 64 bit ubuntu 8.10, i could see that the latest version available was "180.29". Go inside the directory and see the available drivers

NVIDIA-Linux-x86_64-180.29-pkg0.run RUN 13650 KB 02/06/2009 08:48:00 PM
NVIDIA-Linux-x86_64-180.29-pkg1.run RUN 13652 KB 02/06/2009 08:48:00 PM
NVIDIA-Linux-x86_64-180.29-pkg2.run RUN 20453 KB 02/06/2009 08:48:00 PM

Why are there 3 drivers instead of one. Well, what nvidia does is that it compiles a basic driver and then keeps on adding more stuff into it. So basically you should download the latest "pkg#" version of driver. In our case it is

NVIDIA-Linux-x86_64-180.29-pkg2.run

So, now you have the latest driver with you and you want to install the driver.

Switch to a console. Press "CTRL-ALT-F1".
Login using username and password
Kill all gdm/kdm sessions

$ sudo killall kdm

Firstly lets remove the old driver

$ sudo apt-get remove nvidia-177-kernel-source nvidia-177-modaliases nvidia-glx-177 nvidia-glx-177-dev

That should clean up the system of old drivers. Now run the new driver.

$ chmod a+x NVIDIA-Linux-x86_64-180.29-pkg2.run
$ sudo ./NVIDIA-Linux-x86_64-180.29-pkg2.run


It opens up a blue screen and you got to answer tons of questions. Also try to remain connected to the internet cause it might try to download kernel-modules for your driver. If it fails to do so, it will compile the modules. Let the script also modify your xorg.conf file (it will ask your permission to do so).

Once everything is done, simply reboot.

And enjoy kde 4.2 eyecandy with latest nvidia drivers.

installing flash player on ubuntu 64 bit

Basically you can install flash player on a 32 bit ubuntu machine by using apt

$ sudo apt-get install flashplugin-nonfree

It downloads and installs flash player. And all you have got to do in restart firefox.

The issue I faced was how to install flash player on a 64 bit ubuntu machine. As far as i am aware there is no stable release of any flash player for a 64 bit machine. The only way to make the flash based websites work is to install something known as "nspluginwrapper".

nspluginwrapper allows you to use 32 bit netscape compatible plugins on x86_64 browsers. So, the flash plugin is 32 bit but nspluginwrapper allows it to run on browsers compiled for x86_64 machines.

To install flash plugin for 64 bit browser using apt:

$ sudo apt-get install nspluginwrapper flashplugin-nonfree lib32mss-mdns

Restart firefox and bingo, you have flash plugin on your browser.

mount iso image in ubuntu without burning them to disk

Another thing that could be done in linux is that you can mount the ISO image of any CD and browse/work on it. Following are the simple commands which help you achieve it

suppose you have a downloaded kubuntu-8.10-desktop-amd64.iso, and you want to check its contents.

jayant@localhost:~/$ sudo mkdir /tmp/kubuntu
jayant@localhost:~/$ sudo mount kubuntu-8.10-desktop-amd64.iso /tmp/kubuntu -t iso9660 -o loop
jayant@localhost:~/$ ls /tmp/kubuntu/
autorun.inf casper dists install isolinux md5sum.txt pics pool preseed README.diskdefines ubuntu umenu.exe wubi.exe

Bingo, your iso image is mounted and you can easily browse thru it. You dont need to burn it now.

To unmount the image simply issue

jayant@localhost:~/$ sudo umount /tmp/kubuntu

I hope this helps.

AVL Search Tree

With BST the problem is that it should be balanced properly so that the height of a tree with node n should be log(2)n. But since BST does not have any balancing algorithm which re-balances the tree on every insert/delete, the tree becomes unbalanced. In this case the height of the tree may go up to n (same as the number of elements n). So the worst case scenario for search is O(n) for a BST.

An AVL tree on the other hand is supposed to be balanced. Balanced means that
* Either the tree is empty
* Or for every node in a non-empty tree height(left_sub_tree) - height(right_sub_tree) <= 1

The idea is that whenever we insert/remove an element from the tree, we should check that the tree is balanced and if not, we should perform "rotations" to balance the tree.

For example we have a tree

        c
       /
      b

If we add a node "a" to the tree we will get

        c
       /
      b
     /
    a

Now the left subtree is of height 2 and the right subtree is of height 0, so it is unbalanced. So a single right rotation is performed to balance the tree.

      b
     / \
    a   c

Lets see a few algorithms to insert and remove nodes from an AVL tree

Single LL & RR rotation will do the following converstion



Simple rotation to left:

function Rotate_LL(oldRoot)
{
  Result = oldRoot.left;
  oldRoot.left = Result.right;
  Result.right = oldRoot;
  AdjustHeight(oldRoot);
  AdjustHeight(Result);
  AdjustHeight(oldRoot.left);
  return Result;
}

Simple rotation to right:

function Rotate_RR(oldRoot)
{
  Result = oldRoot.right;
  oldRoot.right = Result.left;
  Result.left = oldRoot;
  AdjustHeight(oldRoot);
  AdjustHeight(Result);
  AdjustHeight(oldRoot.right);
  return Result;
}

Following are the RL and LR rotations:

Double rotation to right:


Double rotation to left:


Lets assume that every node has a height attribute. AdjustHeight function updates the height to reflect the current height of the tree

Function adjustHeight(Node)
{
  if (Node != null) then
  {
    Node.height=1+max(height(node.left),height(node.right));
  }
}

Function to get the height of the node

Function getHeight(Node)
{
  if(Node == Void) return 0
  else return Node.height
}

Insert record in AVL tree. Remember that the tree has to be rebalanced after insert.

Function insertData(key, data)
{
  Node = new Node(key, data);
  root = insertNode(root, Node);
  root = rebalanceForInsert(root);
  adjustHeight(root);
}

Function insertNode(root, newNode)
{
  if (root == Void) root = newNode;
  else
  {
    if(root.key > newNode.key)
      root.left = insertNode(root.left, newNode);
    else
      root.right = insertNode(root.right, newNode);
  }
  result = rebalanceForInsert(root);
  adjustHeight(result);
}

Function rebalanceForInsert(Node)
{
  h_LL = height(Node.left.left);
  h_LR = height(Node.left.right);
  h_R = height(Node.right);
  h_RR = height(Node.right.right);
  h_RL = height(Node.right.left);
  h_L = height(Node.left);
  if( (h_LL == h_LR) && (h_LR >= h_R) )
    result = rotate_LL(Node);
  else if( (h_RR == h_RL) && (h_RL >= h_L) )
    result = rotate_RR(Node);
  else if( (h_LR == h_LL) && (h_LL >= h_R) )
    result = rotate_LR(Node);
  else if( (h_RL == h_RR) && (h_RR >= h_L) )
    result = rotate_RL(Node);
  else result = Node;
  return result;
}

Lets look at how to remove node from an AVL tree

Function Remove(key)
{
  if (root==void) result = void;
  else if(root.key == key)
  {
    result = root.data;
    root = removeNode(root);
  }
  else
    result = removeRec(root,key);
  adjustHeight(root);
  root = rebalanceForDel(root);
}

Function RemoveRec(node, key)
{
  if(root.key > key) //remove from left subtree
  {
    if(root.left == void) result = void;
    else if(root.left.key == key)
    {
      result = root.left.data;
      root.left = removeNode(root.left);
    }
    else
    {
      result = removeRec(root.left, key);
      adjustHeight(root.left);
      root.left = rebalanceForDel(root.left);
    }
  }
  else //remove from right subtree
  {
    if(root.right == void) result = void;
    else if(root.right.key == key)
    {
      result = root.right.data;
      root.right = removeNode(root.right);
    }
    else
    {
      result = removeRec(root.right, key);
      adjustHeight(root.right);
      root.right = rebalanceForDel(root.right);
  }
  return result;
}

Function removeNode(Node)
{
  if(Node.left == void) result = Node.right;
  else if(Node.right == void) result = Node.left;
  else (child = root.left)
  {
    if(child.right == void)
    {
      Node.data = child.data;
      Node.left = child.left;
    }
    else
      Node.left = swap_and_remove_left_nbr(Node,child);
    adjustHeight(Node);
    result = rebalanceForDel(Node);
  }
}

Function swap_and_remove_left_nbr(Parent, child)
{
  if(child.right.right != void)
    child.right = swap_and_remove_left_nbr(parent, child.right);
  else
  {
    parent.data = child.right.data;
    child.right = child.right.left;
  }
  adjustHeight(parent);
  result = rebalanceForDel(parent);
}

Function rebalanceForDel(Node)
{
  h_LL = height(Node.left.left);
  h_LR = height(Node.left.right);
  h_R = height(Node.right);
  h_RR = height(Node.right.right);
  h_RL = height(Node.right.left);
  h_L = height(Node.left);
  if( (h_LL >= h_LR) && (h_LR >= h_R) )
    result = rotate_LL(Node);
  else if( (h_RR >= h_RL) && (h_RL >= h_L) )
    result = rotate_RR(Node);
  else if( (h_LR >= h_LL) && (h_LL >= h_R) )
    result = rotate_LR(Node);
  else if( (h_RL >= h_RR) && (h_RR >= h_L) )
    result = rotate_RL(Node);
  else result = Node;
  return result;
}

That is quite a lot of stuff to digest...
Happy chewing...

Binary Search Tree

In a tightly packed binary search tree you need at max log(2)n comparisons to find a match for n elements. So, for example to search a list of 1000 elements, you should need max 10 comparisons. Additions and deletions from the BST (binary search tree) require that the sorted order of elements should be maintained.

Let us see some pseudo code for creating and maintaining binary search trees

Find an element X in a BST with root node N:

find (X, N)
{
  if(N == NULL) return NULL;
  if(X == N.data) return N;
  else if (X < N.data) return find(X, N.leftChild);
  else if (X > N.data) return find(X, N.rightChild);
}


Find the node with the minimum data. Start from root node N

findMinimum(N)
{
  if(N == NULL) return NULL;
  if(N.leftChild == NULL) return N;
  return findMinimum(N.leftChild);
}

Insert data X in a BST with root node N

Insert(X, N)
{
  if(N == NULL) //insert at last node
  {
    N = new BinaryNode(X, NULL, NULL);
    return;
  }
  if(X == N.data) // data already exists in BST, ignore X
    return;
  else if(X < N.data) Insert(X, N.leftChild);
  else Insert(X, N.rightChild);
}


Delete an element X from the BST with root node N

Delete(X, N)
{
  if(N == NULL) return;
  if(X < N.data) Delete(X, N.leftChild);
  else if (X > N.data) Delete(X, N.rightChild)
  else // X == N.data. Delete and readjust all children
  {
    if(N.leftChild == NULL && N.rightChild == NULL)
    {
      delete N;
      N = null;
      return;
    }
    else if(N.leftChild == NULL)
    {
      tmpN = N;
      N = N.rightChild;
      delete tmpN;
    }
    else if(N.rightChild == NULL)
    {
      tmpN = N;
      N = N.leftChild;
      delete tmpN;
    }
    else //replace N.data with minimum data from right subtree
    {
      tmpN = findMinimum(N.rightChild);
      N.data = tmpN.data;
      delete(N.data, N.rightChild);
    }
  }
}

Traversing binary trees

What are trees? Trees are data structures which contain a node and one or more children. A binary tree is a tree in which each node is either empty or contains at max two children.

A binary tree...

root --------> R
                /    \
               L     R
              /  \   /  \
             l  r   rl  

A binary tree of height h<=0 has at max 2^h+1 - 1 nodes. And the height of the tree h = log2(n), where n is the number of nodes in the binary tree.

Lets check out the recursive functions used to traverse the binary trees:

1. Preorder traversal:
Preorder traversal does the following recursively :
-> visit the root
-> traverse left subtree
-> traverse right subtree

function preorder(tree)
{
  if (tree == null) return;

  print(tree.root);
  call preorder(tree.left_subtree);
  call preorder(tree.right_subtree);
}

2. Inorder traversal:
Inorder traversal does the following recursively :
-> traverse left subtree
-> visit the root
-> traverse right subtree

function inorder(tree)
{
  if (tree == null) return;

  call inorder(tree.left_subtree);
  print(tree.root);
  call inorder(tree.right_subtree);
}

3. Postorder traversal:
Postorder traversal does the following recursively :
-> traverse left subtree
-> traverse right subtree
-> visit the root

function postorder(tree)
{
  if (tree == null) return;

  call postorder(tree.left_subtree);
  call postorder(tree.right_subtree);
  print(tree.root);
}

4. Breadth-first or level-order traversal:
In Level-order traversal each level is visited successively starting from root(level-0) and nodes are visited from left to right on each level. This is generally implemented using a queue data structure.

- push the root node in the queue
- pop the node from the queue, push the left and right child node in the queue.
- pop the root->left node from the queue and push the left and right child node of root->left in the queue.
- pop the root->right node from the queue and push the left and right child node of root->right in the queue.

function levelorder(tree)
{
  queue.push(tree.root);
  while(queue.size > 0)
  {
    Node n = queue.pop(); //get first node in queue
    if (n.left != null) queue.push(n.left);
    if (n.right != null) queue.push(n.right);
    print n;
  }
}