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