Dijkstra's shortest value  algorithm
#include<iostream>
using namespace std;

const int INF =9999;

int main(){
    int arr[4][4];
    int cost[4][4]= {
                        7 , 5 , 0 , 0,
                        7 , 0 , 0 , 2,
                        0 , 3 , 0 , 0,
                        4 , 0 , 1 , 0                        
                    };
                    
    int i, j ,k, n =4;
    
    for (i =0;i<n ;i++){
    for (j = 0;j<n;j++)
    {
        if(cost[i][j]== 0)
        arr[i][j]= INF;
        else
        arr[i][j] = cost [i][j];
    }
    }
    
    cout << "Adjacency matrix for cost of edges \n";
    for (i =0;i<n ;i++){
    for (j = 0;j<n;j++)
    cout << arr[i][j] << "\t" ;
    cout << "\n";
    
    }
    for(k=0;k<n;k++){
        for (i =0;i<n ;i++){
            for (j = 0;j<n;j++){
                if(arr[i][j]>arr[i][k]+arr[k][j])
                arr[i][j] = arr[i][k]+arr[k][j];
            }
            
        }
    }
    
    cout << "\n Adjacency matrix of lowest cost between the vertices : \n";
    for (i =0;i<n ;i++){
        for (j = 0;j<n;j++)
            cout << arr[i][j] << "\t" ;
            cout << "\n";
        
    }
}  

    
    
    
    

DEPTH FIRST SEARCH

ALGORITHM -

1 - Visit vertex , say v and mark this vertex visited.

2- Select unvisted vertex w adjacent to v.

3- Repeat steps 1 and 2 till adjacent vertex of w are visited.

4- On reaching vertex whose all adjacent vertices have been visited, go back to last vertex visited which has been unvisited vertex adjacent to it and go back to step 1  -  this is hint to apply recursion!!

5- Terminate when no unvisited vertex can be reached from any of the visited vertex.

// Depth First Search Algorithm for undirected  graphs

#include<iostream>

using namespace std;

#define TRUE 1

#define FALSE 0

const int MAX =8;

struct node {

    int data;

    node *next;

};

class graph{

    private:

        int visited[MAX];

    public:

    graph();

    void dfs(int v,node **p);

    node* getnode_write(int val);

    void del(node *n);

};

 graph::graph(){

    for(int i=0;i<MAX;++i)

    visited[i]= FALSE;

}

node* graph:: getnode_write(int val){

    node *newnode = new node;

    newnode->data= val;

    return newnode;

}

void graph:: del(node *n){

node *temp;

    while(n!=NULL){

        temp= n->next;

        delete n;

        n=temp;

    }

}

void graph:: dfs(int v, node **p){

    visited[v-1]= TRUE;

    cout << v <<"\t";

    node *t;

    t= *(p+v-1);

    while(t!=NULL){

        if(visited[t->data-1]== FALSE){

            dfs(t->data,p);

        }

        else

        t=t->next;

    }

}

int main(){

    node *arr[MAX];

    node *v1,*v2,*v3,*v4;

    graph g;

    v1 = g.getnode_write(2);

    arr[0] =  v1;

    v1->next = v2 =  g.getnode_write(8);

    v2->next = NULL;

   

    v1 = g.getnode_write(1);

    arr[1] = v1;

    v1->next = v2= g.getnode_write(3);

    v2-> next = v3 = g.getnode_write(8);

    v3->next  =  NULL;

   

    v1 = g.getnode_write(2);

    arr[2] = v1;

    v1->next = v2 = g.getnode_write(4);

    v2->next = v3 = g.getnode_write(8);

    v3->next = NULL;

   

    v1= g.getnode_write(3);

    arr[3] = v1;

    v1->next = v2 = g.getnode_write(7);

    v2->next =NULL;

   

   

    v1 = g.getnode_write(6);

    arr[4] =v1;

    v1->next = v2 = g.getnode_write(7);

    v2->next = NULL;

   

    v1 = g.getnode_write(5);

    arr[5]= v1;

    v1->next =NULL;

   

    v1 = g.getnode_write(4);

    arr[6] = v1;

    v1->next = v2 = g.getnode_write(5);

    v2->next = v3 = g.getnode_write(8);

    v3->next = NULL;

   

    v1 = g.getnode_write(1);

    arr[7] = v1;

    v1->next = v2 = g.getnode_write(2);

    v2->next = v3 = g.getnode_write(3);

    v3->next = v4 = g.getnode_write(7);

    v4->next = NULL;

   

    cout << endl;

    g.dfs(1, arr);

    for(int i =0 ; i<MAX;++i)

    g.del(arr[i]);

    return 0;

   

}

UVA 941 PERMUTATION

Rank of a  given String - In a Lexicographic taste- 
Lexicographic style deals with dictionary style arrangement of characters.
The Rank of a particular arrangement  of characters of a string pretains to a particular permutation adhering to lexicographic arrangement

Taking an example of a given string "abc" , the rank of "abc" would be 1 - lexicographically
Similarly-
abc = 1
acb = 2
cba = 6

The simplest solution that strikes in mind is to take out all lexicographic permutation of the given string and then 
iterate over all permuataions until we find our given match , incrementing passing by every term.

This solution can make complexity increasing exponentially in worst case  :P


The efficient solution is  somewhat tricky , just some high school math work- 
Let the given string be " JIM"  
Check first character "J"  
Total characters = 5
Character smaller then "J" = "I" i.e 1
So there can be 1*2! strings , which have first character smaller then "J" - 
IXX

Now fixing "J" we gotta find smaller strings  starting with "J"
Next character "I" have no character smaller then itself so zero in this case with total rank 1*2!+ 0*1!+...
Next character "M"  have no character smaller then itself so zero in this case with total rank 1*2!+ 0*1!+0*1!..

So rank = 1*2!+ 0*1!+0*0!= 2
As rank starts from 1 unlike numbering starting from zero in programming so rank of "JIM" = 2+1= 3

NOTE- 
To calculate the Lexicographic permuatation for repeated characters, just follow same procedure and in end divide the rank with p! where p is count of occurence of each repeated character . eg-  rank/2! in case of  string  "JIMMY "

//******************* codebloodedvalley.blogspot.com *********************
// ******************  1:24 AM  03-03-2014, GNDU RC SATHIALA *************
#include<stdio.h>
#include<string.h>
#define MAX_CHAR 256

// utility function to find n factorial
int fact(int n){
return (n<=1) ? 1 : n * fact(n-1) ; 
}

// an array count where value at each index gonna 
// contain total count of smaller characters present in given string

void  increaseCountbyPopulating (int* count ,  char* str){
int i;
for(i=0;str[i];++i) // populating  count of each character
++count[ str[i] ];

// instead of calling a loop again n again to check the total characters smaller then particular 
//character present , just iterate once and add the preceding value in every next count[i] for  i <=256
// This will help us to straightway accessing the total numbers of of character smaller then count[str[i]] as shown
// later in the rankFinder() . 
// Unexpected , but Dont panic :D

for(i=1;i<256;++i)  
count[i]+=count[i-1];


}
void countUpdate(int* count, char ch){        // this function is fixing the value of character as explained above
// by deleting its every  occurence in count[] 
int i;
for(i=ch;i<MAX_CHAR;++i)
--count[i];


}

//  now checkout the function to find the rank,pretty simple, understand afformentioned point carefully 
int rankFinder(char* str){
int len =  strlen(str);
int mul = fact(len);
int rank = 1, i;

int count[MAX_CHAR] = {0}; // initialising all elements to 0

 // populating count[i] having count of characters smaller then i present in given string
 increaseCountbyPopulating(count,str);
  for (i = 0; i < len; ++i)
    {
        mul /= len - i;  // this is tricky and efficient, simple high school maths

        // count number of chars smaller than str[i]
        // from str[i+1] to str[len-1]
        rank += count[ str[i] - 1] * mul;

        // Reduce count of characters greater than str[i], i.e fixing the occurence of string[i]
        countUpdate (count, str[i]);
    }

    return rank;
}

// Driver program 
int main()
{
    char str[] = "JIM";
int rank= rankFinder(str);  
printf ("%d", rank);
    return 0;
}