Asymptotic Notation in Algorithms

Suppose we are considering two algorithms, A and B, for solving a given problem. Furthermore, let us say that we have done a careful analysis of the running times of each of the algorithms and determined them to be and , respectively, where n is a measure of the problem size. Then it should be a fairly simple matter to compare the two functions and to determine which algorithm is the best!

But is it really that simple? What exactly does it mean for one function, say , to be better than another function, ? One possibility arises if we know the problem size a priori. For example, suppose the problem size is and . Then clearly algorithm A is better than algorithm B for problem size .

In the general case, we have no a priori knowledge of the problem size. However, if it can be shown, say, that for all , then algorithm A is better than algorithm B regardless of the problem size.

Unfortunately, we usually don't know the problem size beforehand, nor is it true that one of the functions is less than or equal the other over the entire range of problem sizes. In this case, we consider the asymptotic behavior  of the two functions for very large problem sizes. 

                                                                 Read More

Read More

Graph Traversal Implementation Using C - Adjacency List

Different graph traversals are
Breadth First Search
Depth First Search

Implementation 



/************************************************************
* Filename: graph_operations.c
* Description: To implement Graph Operations using Adjacency List
* Author: Sarju S
* Date: 03-Apr-2012
*************************************************************/
#include
#include
//Structure for Vertex Nodes
struct vertexNode{
int element;
int visited;
struct edgeNode *edge;
struct vertexNode *next;
};
typedef struct vertexNode vertexNode ;
vertexNode *start = NULL;


//Structure for Edge Nodes
struct edgeNode{
struct vertexNode *connectsTo;
struct edgeNode *next;
};
typedef struct edgeNode edgeNode ;
//Structure for Stack Nodes
struct stackNode
{
vertexNode *vElement;
struct stackNode *next;
};
typedef struct stackNode stackNode;
stackNode *top = NULL;


//Structure for Queue Nodes
struct queueNode
{
vertexNode *vElement;
struct queueNode *next;
};


typedef struct queueNode queueNode;
queueNode *qFront=NULL,*qRear=NULL;


//Function for creating new vertex node
void addVertex(int element){
vertexNode *newVertex,*temp;
//Allocating memory for new vertex node and initializing the values
newVertex = (vertexNode *) malloc(sizeof(vertexNode));
newVertex->element = element;
newVertex->visited =0;
newVertex->edge=NULL;
newVertex->next=NULL;
if(start==NULL){//If the graph is empty
start=newVertex;
}
else{//If the graph is not empty
temp= start;
while(temp->next!=NULL){
temp = temp->next;
}
temp->next = newVertex;
}
}


//Function for creating new edge node
void addEdge(int v1, int v2){
edgeNode *newEdge,*temp;
vertexNode *temp1,*v,*u;
temp1 = start;
/*Finding the source and destination vertex v is
the source vertex and u is the destination
vertex*/
while(temp1){
if(temp1->element == v1)
v=temp1;
if(temp1->element == v2)
u=temp1;
temp1=temp1->next;
}
newEdge = (edgeNode *) malloc(sizeof(edgeNode));
newEdge->connectsTo = u;
newEdge->next = NULL;
if(v->edge==NULL){
v->edge = newEdge;
}
else{
temp=v->edge;
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=newEdge;
}

}


//Function for displaying the graph
void displayGraph(){
vertexNode *temp1;
edgeNode *temp2;
temp1=start;
while(temp1){
printf("%d->",temp1->element);
if(temp1->edge!=NULL){
temp2=temp1->edge;
while(temp2){
printf("%d->",temp2->connectsTo->element);
temp2=temp2->next;
}


}
printf("\n|\n");
printf("v\n");
temp1=temp1->next;

}

}
//Stack push function
void push(vertexNode *v){
stackNode *newStackNode;
newStackNode = (stackNode *) malloc(sizeof(stackNode));
newStackNode->vElement = v;
newStackNode->next = NULL;
if(top==NULL){
top=newStackNode;
}
else{
newStackNode->next = top;
top = newStackNode;
}


}
//Stack pop function
vertexNode * pop(){
vertexNode *temp=NULL;
if(top==NULL){
printf("\nStack is Empty");
}
else{
temp = top->vElement;
top = top->next;


}
return(temp);
}
//Function for Depth First Search
void dfs(){
vertexNode *temp;
edgeNode *temp2;
push(start);
while(top){
temp = pop();
if(temp->visited==0){
printf("%d\t",temp->element);
temp->visited = 1;
}
temp2=temp->edge;
while(temp2){
push(temp2->connectsTo);
temp2=temp2->next;
}
}
}
//Queue Insert function
void enQueue(vertexNode *v){
queueNode *tmp_ptr=NULL;
tmp_ptr=(queueNode *)malloc(sizeof(queueNode));
tmp_ptr->vElement = v;
tmp_ptr->next = NULL;
if(qFront == NULL){
qFront=tmp_ptr;
qRear=tmp_ptr;
}
else{
qRear->next=tmp_ptr;
qRear=tmp_ptr;
}

}


//Queue Delete function
vertexNode * deQueue(){
/*Delete element from Queue*/
vertexNode *temp=NULL;
temp = qFront->vElement;
if(qFront==NULL)
printf("\nThe Queue is Empty");
else if(qFront==qRear)
qFront=qRear=NULL;
else
qFront=qFront->next;

return(temp);

}
//Function for Breadth First Search
void bfs(){
vertexNode *temp;
edgeNode *temp2;
enQueue(start);
while(qFront){
temp =deQueue();
if(temp->visited==0){
printf("%d\t",temp->element);
temp->visited = 1;
}
temp2=temp->edge;
while(temp2){
enQueue(temp2->connectsTo);
temp2=temp2->next;
}
}
}
/*Function used for clering the visit tag of the
nodes to zero*/
void clearVisit(){
vertexNode *temp=start;
while(temp){
temp->visited =0;
temp=temp->next;
}
}


int main(){
int ch;
int element;
int v1,v2;
do{
printf("\n1:AddVertex\n2:AddEdge\n3:Dispaly\n4:DFS\n5:BFS\n6:Exit");
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch){
case 1: printf("Entere the vertex to add:");
scanf("%d",&element);
addVertex(element);
break;
case 2: printf("\nEnter the vertices that are to be connected:");
scanf("%d%d",&v1,&v2);
addEdge(v1,v2);
break;
case 3: displayGraph();
break;
case 4: dfs();
clearVisit();
break;
case 5: bfs();
clearVisit();
}
}while(ch<6);
return 0;
}




OUTPUT

sjcet@sjcet-laptop:~$ gcc -Wall graph_operations.c
sjcet@sjcet-laptop:~$ ./a.out


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:0


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:1


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:2


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:3


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:4


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:5


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:6


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:7


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:1
Entere the vertex to add:8


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:0 1


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:0 2


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:1 3


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:2 4


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:3 5


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:4 6


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:4 7


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:2


Enter the vertices that are to be connected:4 8


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:3
0->1->2->
|
v
1->3->
|
v
2->4->
|
v
3->5->
|
v
4->6->7->8->
|
v
5->
|
v
6->
|
v
7->
|
v
8->
|
v


1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:4
0 2 4 8 7 6 1 3 5
1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:5
0 1 2 3 4 5 6 7 8
1:AddVertex
2:AddEdge
3:Dispaly
4:DFS
5:BFS
6:Exit
Enter your choice:6
sjcet@sjcet-laptop:~$ ./a.out

Read More

Postfix Evaluation using Stack

/************************************************************
* Filename: postfix_evaluation.c
* Description: postfix evaluation using stack
* Author:Sarju S
* Date: 02-Dec-2011
*************************************************************/


#include
#include
#define MAX_EXPR_SIZE 100
#define MAX_STACK_SIZE 100 


typedef enum {eos,lparen, rparen, plus, minus, times, divide,mod,operand} precedence;
char postfixExpr[MAX_EXPR_SIZE];
int stack[MAX_STACK_SIZE];
int top=-1,postfixCount=0;


void stackFull()
{
fprintf(stderr, "Stack is full cannot add elements\n");
exit(EXIT_FAILURE);
}


void stackEmpty()
{
fprintf(stderr, "Stack is empty cannot delete elements\n");
exit(EXIT_FAILURE);
}


void push(int item)
{/* add an element to stack */
if(top>=MAX_STACK_SIZE-1)
stackFull();
top++;
stack[top] = item;
}


int pop()
{/*Delete top element from the stack*/
if(top==-1)
stackEmpty();
return stack[top--];
}




precedence getToken(char *symbol)
{ /* get the next token, symbol is the character representation,which is 
returned, the token is represented by its enumerated value, which is 
returned in the function name */
*symbol = postfixExpr[postfixCount];
postfixCount++;
switch(*symbol) {
case '\0': return eos;
case '(' : return lparen;
case ')' : return rparen;
case '+' : return plus;
case '-' : return minus;
case '/' : return divide;
case '*' : return times;
case '%' : return mod;
default  : return operand;
}
}




int postfixEvaluate(){
/* evaluate a postfix expression and returns the result */
precedence token;
char symbol;
int op1,op2;
token = getToken(&symbol);
while(token!=eos){
if(token==operand)
push(symbol-'0');

else{
/* pop two operands, perform operation and 
push result to stack */
op2 = pop();
op1 = pop();
switch(token){
case plus :push(op1+op2);
  break;
case minus :push(op1-op2);
  break;
case times :push(op1*op2);
  break;
case divide :push(op1/op2);
  break;
case mod :push(op1%op2);
 
}
}
token = getToken(&symbol);
}
return pop();/* return result */
}


void main(){
int result;
printf("\nEnter the POSTFIX expression:");
scanf("%s",postfixExpr);
result=postfixEvaluate(); /* Function Call*/
printf("\nThe Result is:%d",result);
}




OUTPUT

krishnakripa@krishnakripa-K8Upgrade-VM800:~$ gcc postfix_evaluation.c
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ ./a.out


Enter the POSTFIX expression:62/3-42*+


The Result is:8
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ 

Read More

Infix to Postfix conversion using stack

/************************************************************
* Filename: infix_to_postfix.c
* Description: infix to postfix conversion using stack
* Author:Sarju S
* Date: 01-Dec-2011
*************************************************************/
#include
#include
#define MAX_EXPR_SIZE 100
#define MAX_STACK_SIZE 100 

typedef enum {eos,lparen, rparen, plus, minus, times, divide,mod,operand} precedence;
char infixExpr[MAX_EXPR_SIZE],postfixExpr[MAX_EXPR_SIZE];
precedence stack[MAX_STACK_SIZE];
int top=-1,infixCount=0,postfixCount=0;

void stackFull()
{
fprintf(stderr, "Stack is full cannot add elements\n");
exit(EXIT_FAILURE);
}

void stackEmpty()
{
fprintf(stderr, "Stack is empty cannot delete elements\n");
exit(EXIT_FAILURE);
}

void push(precedence item)
{/* add an element to stack */
if(top>=MAX_STACK_SIZE-1)
stackFull();
top++;
stack[top] = item;
}

precedence pop()
{/*Delete top element from the stack*/
if(top==-1)
stackEmpty();
return stack[top--];
}

void printToken(precedence token){
/* to print the symbol corresponding to token*/
switch(token) {
case 3 :postfixExpr[postfixCount]='+';
postfixCount++;
break;
case 4 :postfixExpr[postfixCount]='-';
postfixCount++;
break;
case 5 :postfixExpr[postfixCount]='*';
postfixCount++;
break; 
case 6 :postfixExpr[postfixCount]='/';
postfixCount++;
break;
case 7 :postfixExpr[postfixCount]='%';
postfixCount++;
}
}

precedence getToken(char *symbol)
{ /* get the next token, symbol is the character representation,which is 
returned, the token is represented by its enumerated value, which is 
returned in the function name */

*symbol = infixExpr[infixCount];
infixCount++;
switch(*symbol) {
case '\0': return eos;
case '(' : return lparen;
case ')' : return rparen;
case '+' : return plus;
case '-' : return minus;
case '/' : return divide;
case '*' : return times;
case '%' : return mod;
default  : return operand;
}
}

int checkPriority(precedence token){
switch(token) {
case plus   : 
case minus  : return 4;
case times  : 
case divide : return 6;
}

}

void infixToPostfix()
{/* output postfix of expression */
char symbol;
precedence token;
top = 0;
stack[0]= eos;
token = getToken(&symbol);
while(token!=eos){
if(token == operand){
postfixExpr[postfixCount]=symbol;
postfixCount++;
}

else if(token == rparen){
/*unstack tokens until left parenthesis */
while(stack[top]!= lparen)
printToken(pop());
pop(); /*remove left parenthesis */
}
else {
/*remove and print symbols whose in-stack precedence is greater than or 
 equal to the current tokens incoming precedence */
if(token!=1) /*Avoid Comparison of Left Paranthesis */
while(checkPriority(stack[top])>= checkPriority(token))
printToken(pop());
push(token);
}
token =getToken(&symbol);
} 
while((token = pop())!=eos)
printToken(token);
postfixExpr[postfixCount]='\0';
}

void main(){
printf("\nEnter the INFIX expression:");
scanf("%s",infixExpr);
infixToPostfix(); /* Function Call*/
printf("\nThe POSTFIX expression:");
printf("%s\n",postfixExpr);

}

OUTPUT

krishnakripa@krishnakripa-K8Upgrade-VM800:~$ gcc infix_to_postfix.c
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ ./a.out

Enter the INFIX expression:((a/(b-c+d)))*(e-a)*c

The POSTFIX expression:abc-d+/ea-*c*
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ ./a.out

Enter the INFIX expression:a/b-c+d*e-a*c        

The POSTFIX expression:ab/c-de*+ac*-
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ 

Read More