Floyd Warshall Algorithm!

The Floyd-Warshall Algorithm is an efficient algorithm to find all-pairs shortest paths on a graph. That is, it is guaranteed to find the shortest path between every pair of vertices in a graph. The graph may have negative weight edges, but no negative weight cycles (for then the shortest path is undefined).

This algorithm can also be used to detect the presence of negative cycles—the graph has one if at the end of the algorithm, the distance from a vertex v to itself is negative.

The problems form ACM UVA , 523 and 627

Assuming that a[i][j]=-1 where there is no path. p[i][j] is used for tracing the shortest path. The Algorithm is just an application of Dynamic Programming. INF is considered to be a very big integer.

for(int i=0;i<n;++i)
for(int j=0;j<n;j++)
if (a[i][j]==-1)
{
a[i][j]=INF;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
p[i][j]=i;
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(a[i][j] > a[i][k]+a[k][j])
{ a[i][j]=a[i][k]+a[k][j];
p[i][j]=p[k][j];
}
}
}
}

Longest path!

The problem taken form acm uva site , Longest Path

Since we need to know the longest path for a source node given, the graph of cities to be traversed in DFS. The Depth First Traversal visits all nodes reachable from the source node. Here is the function needed for DFS in this problem.

void dfs(long snode)
{
long i;
if(sum>max)
{
max=sum;
p=snode;
}
for(i=0;i<num;i++)
{
if(n[snode][i]==1&&visited[snode][i]==0&&i!=start)
{
visited[snode][i]=1;
sum++;
dfs(i);
sum--;
visited[snode][i]=0;
}
}
}

Threaded binary Trees !!

Traversing the binary tree is the most important operation and used in almost every application. The iterative implementation of traversing the binary tree is implemented using either stack (simulation of recursion) or using the threaded binary trees , later being the more efficient. The idea is to maintain extra information of a particular traversal which saves a lot of pushing and popping in stack implementation. This is done by maintaining extra pointer to the leaf nodes (right child in case of right-in threaded binary tree, named on the basis of same) known as thread . This is done as follows:

While adding a left child in right-in threaded binary tree

- Point the right child of the node to its parent.

While adding a right child in right -in threaded binary tree

-Point the right child of the node to the thread of the parent

The thread is detected from the normal links by using a boolean field in the node , when set to true indicates that it is actually a thread .

Here is the implementation
struct tnode *insert(struct tnode *p , int val)
{
if(p==NULL)
{
p = (struct tnode *)malloc(sizeof(struct tnode));
p->data = val;
p->left = NULL;
p->right = NULL;
p->rthread=true;
}
else
{
struct tnode *q,*temp;
q=p;
temp=p;
while(q != NULL && q->rthread==false)
{
temp= q;
if( val >= temp->data )
q=temp->right;
else if( val < temp->data )
q=temp->left;
}
struct tnode *n;
n= (struct tnode *)malloc (sizeof(struct tnode));
n->data =val;
if( val >=temp->data )
{
if(temp->rthread)
{
struct tnode *r;
r=temp->right;
temp->right =n;
temp->rthread=false;
n->left=NULL;
n->right=r;
n->rthread=true;
}
}
else
{
temp->left = n;
n->left=NULL;
n->right=temp;
n->rthread=true;
}
}
return p;
}

A left-in-threaded binary tree  may be defined similarly, as one in which each NULL left pointer  is altered to contain a thread to that node’s inorder predecessor. An in-threaded binary tree may then be defined as a binary tree that is  both left in-threaded and right in-threaded. 

Kopete and Latex

Latex has been the best typesetting software ever made. I have always preferred it for any type of document. Latex has been very useful in case you want to use many mathematical formulas in the document. Sometimes, though rarely , we need to use mathematical expressions in our chat conversation. I was wondering if any messenger provides the \Latex support in the chat window. Then I found kopete’s ” KopeTeX” plugin allows Kopete to render Latex \
formulas in the chat window. The sender must enclose the formula between two $ signs. \
ie: $$formula$$ +This plugin requires ImageMagick convert program installed in order.

For example: for T= 2 PI /OMEGA

$$T=2\frac{\pi}{\omega}$$

Merging two sorted linked lists !!

The problem is just like merging step in merge sort, wherein we have two sorted arrays and merge them into one. The algorithm is simple and stated as:
struct node *merge(struct node *p,struct node *q)
{
struct node *r,*s;
struct node *a=NULL;
r=p; s=q;
while(r !=NULL && s!= NULL)
{
if(r->data <= s->data)
{
a=insert(a,r->data);
r=r->link;
}
else{
a=insert(a,s->data);
s=s->link;
}
}
if(r==NULL)
while(s!=NULL)
{
a=insert(a,s->data);
s=s->link;
}
else
while(r!=NULL)
{
a=insert(a,r->data);
r=r->link;
}
return a;
}

all about binary tree !!

I recently implemented few of the operations on the binary tree. Some of the operations might match with my previous posts. I have simply posted the code. Please come up with queries if any.

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
long long test;
using namespace std;
struct tnode {
int data;
struct tnode *left;
struct tnode *right;
};
int flag=0;
struct tnode *insert(struct tnode *p , int val)
{
if(p==NULL)
{ p = (struct tnode *)malloc(sizeof(struct tnode));
p->data = val;
p->left = NULL;
p->right = NULL;
}
else
{
struct tnode *q,*temp;
q=p;
temp=p;
while(q != NULL )
{
temp= q;
if( val >= temp->data)
q=temp->right;
else
q=temp->left;
}
struct tnode *n;
n= (struct tnode *)malloc (sizeof(struct tnode));
n->data =val;
if( val >=temp->data )
temp->right =n;
else
temp->left = n;
}
return p;
}
int count1 ( struct tnode *p)
{ int c1=0;
int c2=0;
if( p != NULL){
c1=count1(p->left);
c2= count1(p->right);
return 1+c1+c2;
}
}
struct tnode *delmin(struct tnode *p)
{
struct tnode *temp=p;
while( temp->left->left != NULL)
{
temp = temp->left;
}
temp->left=NULL;
delete(temp->left);
return p;
}
struct tnode *delmax(struct tnode *p)
{
struct tnode *temp=p;
while( temp->right->right != NULL)
{
temp = temp->right;
}
temp->right=NULL;
delete(temp->right);
return p;
}
int height(struct tnode *p)
{
int h1=0;
int h2=0;
if (p == NULL)
return 0;
if(p->left)
h1= height(p->left);
if(p->right)
h2= height(p->right);
return (1+max(h1,h2));
}
bool iscomptree(struct tnode *p)
{
struct tnode *temp=p;
int l,h;
l=count1(p);
h=height(temp);
int t;
t=(int) (pow(2,((float)h))-1);
if(t == l)
return true;
else
return false;
}
struct tnode *mirror(struct tnode *p)
{
if(p == NULL)
return p ;
else
{
mirror(p->left);
mirror(p->right);
struct tnode *temp;
temp=p->left;
p->left=p->right;
p->right=temp;
}
return p;
}
bool identical(struct tnode* a, struct tnode* b)
{
if (a==NULL && b==NULL){return(true);}
else if (a!=NULL && b!=NULL)
{
return(a->data == b->data &&
identical(a->left, b->left) &&
identical(a->right, b->right));
}
else return(false);
}
int check( struct tnode *p)
{ int h1,h2,sum=0;
if(p != NULL)
{
if(p->left && ! (p->right) || p->right && !(p->left))
{
flag=1;
return flag;
}
else{
if(flag != 1)
{
flag= check(p->left);
flag=check(p->right);
}
}
}
return flag;
}
int add ( struct tnode *p)
{ int sum1=0, sum2=0 ;
if( p != NULL){
sum1=add(p->left);
sum2=add(p->right);
return sum1+sum2+p->data;
}
}
void inorder ( struct tnode *p)
{
if( p != NULL){
inorder(p->left);
printf("%d\t",p->data);
inorder(p->right);
}
}
void preorder ( struct tnode *p)
{
if( p != NULL){
printf("%d\t",p->data);
preorder(p->left);
preorder(p->right);
}
}
void postorder ( struct tnode *p)
{
if( p != NULL){
postorder(p->left);
postorder(p->right);
printf("%d\t",p->data);
}
}
main()
{
struct tnode *root=NULL;
root=insert(root,16);
root=insert(root,14);
root=insert(root,20);
root=insert(root,12);
root=insert(root,15);
root=insert(root,18);
root=insert(root,22);
printf("Inorder traversal of the tree\n");
inorder(root);
cout<<endl;
printf("Preorder traversal of the tree\n");
preorder(root);
cout<<endl;
printf("Postorder traversal of the tree\n");
postorder(root);
cout<<endl;
printf("Height of the binary tree : ");
cout<<height(root)-1;
cout<<endl;
printf("Strictly binary tree[=0]: ");
cout<<check(root);
cout<<endl;
printf("Complete binary tree[=1]: ");
cout<<iscomptree(root);
cout<<endl;
struct tnode *r;
cout<<endl;
root=delmin(root);
inorder(root);
root=delmax(root);
cout<<endl;
inorder(root);
}

Pirates !

Five pirates have 100 gold coins.They have to divide up the
loot.In order of seniority,each pirate proposes a distribution
of the loot.All the pirates vote,and if at least half accept the
proposal,the loot is divided as proposed.If not,the most senior
pirate is eliminated,and they start over again with the next
senior pirate.What solution does the most senior pirate
propose? Assume they are very intelligent,extremely greedy,
and interested in surviving.

Solution:

The most senior pirate knows that he needs to get two other pirates
to vote for his solution in order for him not to be eliminated. So why
would any pirate vote for him? The next most senior pirate would
surely see it in his self-interest for the senior pirate to be eliminated.
Letís start simplifying. If there were only one pirate, there would
be no puzzle. The pirate would take all the loot, and no one
would complain.
Now consider the situation with two pirates. Same outcome. The
senior pirate takes all the loot, and the other pirate can’t do a thing
about it as the senior pirate’s vote represents half of the voters.
It gets more complicated for the senior pirate when there are
three pirates. Let’s number the pirates from least to most senior:
1, 2, and 3. With three pirates, pirate 3 has to convince at least one
other pirate to join his collation. Pirate 3 realizes that if his plan
is not adopted, he will be eliminated, and they will be left with two
pirates. All of them know what happens when there are two pirates:
pirate 2 takes all the loot himself and pirate 1 gets nothing. So pirate
3 proposes that he will take 99 gold coins and give 1 coin to pirate
1. If pirate 1 has any self-interest at all, he really has no choice. If
pirate 1 rejects the offer, he gets nothing. So pirate 3ís plan will
pass two to one over pirate 2ís objection.
With four pirates, an even number, the senior pirate needs just one
vote other than his own to impose his will. His question now is which
one of the other pirate’s votes can be exchanged for the fewest number
of coins. Pirate 2 recognizes that he is most vulnerable. Therefore, pirate
4 knows that if he gives pirate 2 anything at all, he will vote for it.
A rule is emerging here. In each case, the senor pirate should buy
only the votes he needs, and buy them as cheaply as possible. Apply
the rule to the five-pirate case. Pirate 5 needs two votes plus his own.
The goal is to toss a coin or two to pirate 1 and pirate 3, the two
pirates in the most vulnerable positions. Both will be empty-handed .

if the senior pirate is eliminated and four pirates remain. So pirate
5 offers one coin to pirate 3 and one coin to pirate 1. Pirates 2 and
4 get nothing.

Click here for detailed solution.

Why nine minutes?

Many consumer alarm clocks have a snooze button that is
calibrated for 9 minutes.Does that sound like an odd
decision? Many people would think a 10-minute snooze
interval would make more sense.So were the designers asleep?
Why 9 minutes?

By setting the snooze time to 9 minutes, the alarm clock only needs to
watch the last digit of the time. Whether implemented by physical circuitry
or software, it is easier to manipulate just the terminal digit.

putchar to int!

Print an integer using only putchar. Try doing it without using extra storage.

void print_to_int(int x)
{
if(x <=9)
{putchar(x+'0');
return;
}
else
print_to_int(x/10);putchar(x%10+'0');
}

Level order traversal!

For the level order of the binary tree:

1- start from the root, display it

2-put the left child and then right child in a queue

3-again consider the first element of the queue as root and repeat the procedure till the whole tree is traversed.

here is the C code :

void levelorder(struct tnode *p)
{
struct tnode *queue[100]={(struct tnode*) 0};
int size=0;
int qptr=0;
while(p)
{
printf("%d\t",p->data);
if(p->left)
{
queue[size++]=p->left;
}
if(p->right)
{
queue[size++]=p->right;
}
p=queue[qptr++];
}
}