Showing posts with label dsa labs. Show all posts
Showing posts with label dsa labs. Show all posts

## Friday, June 7, 2013

### Huffman Algorithm Implementation in C| Huffman Encoding| Huffman Algorithm Example

Huffman Algorithm is an encoding technique for symbols where most frequently occuring symbols are represented with short length bit strings and least frequently occuring symbols are represented with long bit strings.

This algorithm is widely used as the fundamental encoding algorithm in compressing audio and image files.

## Saturday, May 18, 2013

### Implementation of Warshall's Algorithm in C++ with Source Codes

Warshall's algorithm is used to find the transitive closure of a graph. It's one of the efficient method to compute closure path that can be produced. Transitive closure is an important application in graph theory in computer science.
The following provides the source codes for implementing the Warshall's algorithm:

``````
//.............................USE OF WARSHALL'S ALGORITHM TO CREATE TRANSITIVE CLOSURE OF A GRAPH..........

#include<iostream>
#include<conio.h>

using namespace std;
const int num_nodes =10;

int main()
{
//..............................................................VARIABLE DECLARATION
int num_nodes,k,n;
char i,j,res,c;
``````

### C Source Code for Dijkstra's Shortest Path Algorithm

Dijkstra's Shortest Path Algorithm is the popular algorithm for finding shortest/optimal path in compute science due to its widespread application in different branches- computer networks, distributed systems, signal processing etc.

I've implemented the algorithm for finding the minimum distance between any two nodes:

``````
///......................................SHORTEST PATH ALGORITHM << Dijkstra Algorithm >>......................

#include<stdio.h>
#include<conio.h>
#define MAX_NODES 10
#define INFINITY 1000
#define MEMBER 1
#define NON_MEMBER 0

struct arc{
int weight;
};``````
`int main(){`
``````
int i,j,k,weight[MAX_NODES][MAX_NODES],num_nodes,source,dest,precede[MAX_NODES];
int distance[MAX_NODES],permanent_nodes_set[MAX_NODES];
int current,current_distance,n;
int smalldist,newdist;
char s,d,node;

printf("\n\t\t................................................................................\n");
printf("\t\t\t\tSHORTEST PATH ALGORITHM << Dijkstra Algorithm >>");
printf("\n\t\t................................................................................\n");
printf("\n\n\t\t\tAssign 1000 as INFINITY for non-adjacent nodes !!\n\n");
printf("\nEnter the number of nodes in the GRAPH :");
scanf("%d",&n);

for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
printf("\nEnter weight for arc[%c][%c] :",65+i,65+j);
scanf("%d",&weight[i][j]);
weight[j][i] =weight[i][j];
weight[i][i] =INFINITY;
}

printf("\nEnter the source _node :");scanf(" %c",&s);
source =(int)(s-97);
printf("\nEnter the destination_node :");scanf(" %c",&d);
dest = (int)(d-97);

printf("\n\t\t\tThe shortest path is :>>\n\n\t\t\t");
for(i=0;i<n;i++)
{
permanent_nodes_set[i] =NON_MEMBER;
distance[i] =INFINITY;
}
permanent_nodes_set[source]=MEMBER;
distance[source]=0;
current=source;
while(current!=dest)
{
smalldist =INFINITY;
current_distance =distance[current];
for(i=0;i<n;i++)
if(permanent_nodes_set[i] ==NON_MEMBER)
{
newdist =current_distance+weight[current][i];
if(newdist<distance[i])
{
distance[i]=newdist;
precede[i]=current;
if(node!=(65+current))
printf(" %c ->",65+current);
node =65+current;

}
if(distance[i]<smalldist)
{
smalldist =distance[i];
k =i;
}

}

current =k;
permanent_nodes_set[current] =MEMBER;

}

printf(" %c ->",65+dest);
printf("\n\n\t\t\tThe shortest distance = %d\n",distance[dest]);

getch();
return 0;
}

``````

### Priority Queue Implementation: C source codes

A priority queue is data structure in which intrinsic ordering of the elements does determine the results of its basic operations. These are of two types- ascending (e.g. queue) and descending (e.g. stack).
The following source code implements ascending type priority queue in C:

``// Ascending Priority Queue Implementation in C``
``````#include<iostream.h>
#include<conio.h>

const int MAX=5;

class pqueue
{
int front,rear;
public:
struct data
{
int val,p,o;
}d[MAX];
``````

### Merge Sort Algorithm with C source Codes

Here, I've presented the merge sort algorithm as the straight merge sort. The basic idea is to break the file into n subfiles of size 1 and merge adjacent disjoint pairs of files and repeating the process until we've single file remaining of size n.
The C Source codes is as follows:

`// Merge sort implementation in C`
``````#include<stdio.h>

void getdata(int arr[],int n)
{
int i;
printf("\nEnter the data:");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
}
``````

### Implement Infix to postfix conversion using Stack C source codes

We can implement a valid infix expression to a valid postfix expression using stacks in c as shown:

``````

//C PROGRAM TO CONVERT GIVEN VALID INFIX EXPRESSION INTO POSTFIX EXPRESSION USING STACKS.

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#define MAX 20

char stack[MAX];
int istack[MAX];
int top = -1;
char pop();
void push(char item);
``````