10 b IMPLEMENTATION OF HUFFMAN CODING

10 b IMPLEMENTATION OF HUFFMAN CODING

AIM:

      To write a java program to implement Huffman Coding

ALGORITHM:

1.Sort the message ensemble by decreasing probability.

        2. N is the cardinal of the message ensemble (number of different messages).

        3.Compute the integer n_0 such as 2<=n_0<=D and (N-n_0)/(D-1) is integer.

        4. Select the n_0 least probable messages, and assign them each a digit code.

        5. Substitute the selected messages by a composite message summing their probability, and    re-order it.

        6.While there remains more than one message, do steps thru 8.

        7.   Select D least probable messages, and assign them each a digit code.

        8.   Substitute the selected messages by a composite message summing their probability, and re-order it.

        9. The code of each message is given by the concatenation of the code digits of the aggregate they've been put in.

PROGRAM :

import java.util.*;

abstract class HuffmanTree implements Comparable<HuffmanTree>

 {

public final int frequency;

public HuffmanTree(int freq)

{

 frequency = freq;

}

public int compareTo(HuffmanTree tree)

{

return frequency - tree.frequency;

}

}

class HuffmanLeaf extends HuffmanTree

{

public final char value;

public HuffmanLeaf(int freq, char val)

{

super(freq);

value = val;

}

}

class HuffmanNode extends HuffmanTree

{

public final HuffmanTree left, right;

public HuffmanNode(HuffmanTree l, HuffmanTree r)

{

super(l.frequency + r.frequency);

left = l;

right = r;

}

}

public class HuffmanCode

{

public static HuffmanTree buildTree(int[] charFreqs)

{

PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();

for (int i = 0; i < charFreqs.length; i++)

if (charFreqs[i] > 0)

trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));

assert trees.size() > 0;

while (trees.size() > 1)

{

HuffmanTree a = trees.poll();

HuffmanTree b = trees.poll();

trees.offer(new HuffmanNode(a, b));

}

return trees.poll();

}

public static void printCodes(HuffmanTree tree, StringBuffer prefix)

{

assert tree != null;

if (tree instanceof HuffmanLeaf)

{

HuffmanLeaf leaf = (HuffmanLeaf)tree;

System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix);

} else if (tree instanceof HuffmanNode)

{

HuffmanNode node = (HuffmanNode)tree;

prefix.append('0');

printCodes(node.left, prefix);

prefix.deleteCharAt(prefix.length()-1);

prefix.append('1');

printCodes(node.right, prefix);

prefix.deleteCharAt(prefix.length()-1);

}

}

public static void main(String[] args)

{

String test = "this is an example for huffman encoding";

int[] charFreqs = new int[256];

for (char c : test.toCharArray())

charFreqs[c]++;

HuffmanTree tree = buildTree(charFreqs);

System.out.println("SYMBOL\tWEIGHT\tHUFFMAN CODE");

printCodes(tree, new StringBuffer());

}

}

10 a. IMPLEMENTATION OF ACTIVITY SELECTION

10 a. IMPLEMENTATION OF ACTIVITY SELECTION

AIM:

      To write a java program to implement Activity Selection.

ALGORITHM:

  1.Sort the activities as per finishing time in ascending order

  2.Select the first activity

  3.Select the new activity if its starting time is greater than or equal to the previously selected        activity
   4.REPEAT step 3 till all activities are checked

PROGRAM :

import java.util.*;

import java.lang.*;

import java.io.*;

class ActivitySelection

{

public static void printMaxActivities(int s[], int f[], int n)

{

int i, j;

System.out.print("Following activities are selected : n");

i = 0;

System.out.print(i+" ");

for (j = 1; j < n; j++)

{

if (s[j] >= f[i])

{

System.out.print(j+" ");

i = j;

}

}

}

public static void main(String[] args)

{

int s[] =  {1, 3, 0, 5, 8, 5};

int f[] =  {2, 4, 6, 7, 9, 9};

int n = s.length;

printMaxActivities(s, f, n);

}

9. IMPLEMENTATION OF MATRIX CHAIN MULTIPLICATION

9. IMPLEMENTATION OF MATRIX CHAIN MULTIPLICATION

AIM: 

To write a java program to implement Matrix Chain Multiplication.

ALGORITHM:

1. A chain of matrices to be multiplied is given as input.
2. For a sequence A1,A2,A3,A4 of 4 matrices, there are 5 different orderings=5 different parethesization.

i)                    (A1,(A2(A3 A4)))

ii)                  (A1((A2 A3)A4))

iii)                ((A1 A2)(A3 A4))

iv)                ((A1(A2 A3))A4)

v)                  (((A1 A2)A3)A4)

3. Matrix_Multiply(A,B)

       If coloumns[A]!=rows[B]

            Then error “incomplete dimensions”

            Else for i <- 1 to rows[A]

              Do for j <- 1 to columns[B]

                   Do c[I,j] <- 0

                        For k<- 1 to columns[A]

                        Do c[i,j]=C[i,j]+A[i,k]+B[i,j]

                        Return c

4.    A parenthesizing of the chain of the matrices is obtained as output.

PROGRAM :

public class MatrixChainMulti

{

void matrixchain(int a[])

{

int q;

int n=a.length;

int m[][]=new int[n][n];

int s[][]=new int[n][n];

for (int i=1;i<n;i++)

m[i][i]=0;

for (int l=2;l<n;l++) //l is the length

{

for(int i=1 ;i<n-l+1;i++)

{

int j=i+l-1;

m[i][j]=Integer.MAX_VALUE;

for (int k=i ;k<=j-1;k++)

{

q=m[i][k]+m[k+1][j]+a[i-1]*a[k]*a[j];

if(q<m[i][j])

{

m[i][j]=q;

s[i][j]=k;

}

}

}

}

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

{

for(int j=0;j<n;j++)

System.out.print(m[i][j]+" ");

System.out.println();

}

print_optimal(s,1,6);

}

void print_optimal(int s[][],int i,int j)

{

if (i==j)

System.out.print("A"+i);

else

{

System.out.print("(");

print_optimal(s,i,s[i][j]);

print_optimal(s,s[i][j]+1,j);

System.out.print(")");

}

}

public static void main(String args[])

{

int a[]={30, 35, 15, 5, 10, 20, 25};//A1:-30x35, A2:- 35x15, A3:- 15x5, A4:- 5x10 , A5:- 10x20, A6:- 20x25

MatrixChainMulti n=new MatrixChainMulti();

n.matrixchain(a);

}

}

8b. IMPLEMENTATION OF BELLMANFORD ALGORITHM

8b. IMPLEMENTATION OF BELLMANFORD ALGORITHM

AIM:

To write a java program to implement quick sort.

ALGORITHM:

  1. Start with the weighted graph

              2.Choose the starting vertex and assign infinity path values to all other vertex      

         3.Visit each edge and relax  the path distance if they are inaccurate

  4.We need to do this V times because in the worst case the vertex path length might need to       be readjusted V times

  5.Notice how the vertex at the top right corner had its path length adjusted

  6.After all vertices  have their path lengths we check if a negative cycle is present

PROGRAM :

import java.util.Scanner;

public class MergeSort

{

public static void sort(int[] a, int low, int high)

{

int N = high - low;

if (N <= 1)

return;

int mid = low + N/2;

sort(a, low, mid);

sort(a, mid, high);

int[] temp = new int[N];

int i = low, j = mid;

for (int k = 0; k < N; k++)

{

if (i == mid)

temp[k] = a[j++];

else if (j == high)

temp[k] = a[i++];

else if (a[j]<a[i])

temp[k] = a[j++];

else

temp[k] = a[i++];

}

for (int k = 0; k < N; k++)

a[low + k] = temp[k];

}

public static void main(String[] args)

{

Scanner scan = new Scanner( System.in );

System.out.println("Merge Sort Test\n");

int n, i;

System.out.println("Enter number of integer elements");

n = scan.nextInt();

int arr[] = new int[ n ];

System.out.println("\nEnter "+ n +" integer elements");

for (i = 0; i < n; i++)

arr[i] = scan.nextInt();

sort(arr, 0, n);

System.out.println("\nElements after sorting ");

for (i = 0; i < n; i++)

System.out.print(arr[i]+" ");

System.out.println();

}

}