Huffman-Encoding In Action

Curiosity regarding huffman-decoding process, force me to make one working huffman-encoding/decoding app.

What is Huffman-Encoding In Action ?

Huffman-Encoding In Action is a small GUI program which allows you to visualize how huffman encoding decoding works.

The actual work is done in a class that encapsulates all the functionality, so it should be easy to set up another GUI for it.

For those who don't know what is Huffman Coding read this 

How It Works 

Let q be the priority doubly linked list

l be the list

class Node
{
    Node left, right;
    char data;
    int freq;
    char lEW = ' ';
    char rEW = ' ';
    boolean isRoot = false;
}

Above code is a structure of a node

/**
     * start of the algorithm
     * characters are read'ed 1 by 1 and count is determined using variable count 
     * and a newrec of type node is created which has a data as = char and freq = count for eg:
     * x is the char which appears 3 times then newrec.data = x and newrec.freq = 3 and finally it is inserted 
     * into Sorted DLL and l contains the char x so that when x appear next we could identify that its freq is already
     * determined
     * the same process is repeated for all the char in the string or txt.
     * @param txt 
     */
    public void start( String txt ){
        ogtxt = txt;
        char[] toCharArray = txt.toCharArray();
        for (char x : toCharArray) {
            int count = 0;
            
            
            if( !(l.contains( String.valueOf( x ) ) ) ){
                for (char k : toCharArray) {
                    if( k == x )
                        count++;
                }
                Node newrec = new Node();
                newrec.freq = count;
                newrec.data = x;
                newrec.left = newrec.right = null;
                q.insert(newrec);
                l.add(String.valueOf( x ));
            }
           
        }

        makeSingleTree( );//a recursive function which makes single huffman tree. base case = when there will be only one record in our sorted doubly linked list.
        root = q.delete();// that single tree is now assigned to root
        root.isRoot = true;
         if(root.left != null & root.right != null){
            assignWeights( root );// assigns 0 to every left edge and 1 to every right edge
            traverse(root);//this will traverse and determine the huffman code for each letter or char.
        }else{
            onlyOneNode = true;
        }
        displayHuffmanCode();// this function will display the unique huffman code for each char.
       
    }

So, there you go, now you have basic idea about how the entire process works, the code is well formed in several different methods and is pretty easy to understand as well.

Speed

On my Desktop with with 2.8GHZ. Huffman-Encoder requires just a couple of ms to generate huffman code.

Download

you can download Huffman-Encoding In Action's latest version from here

Miscellaneous 

When given input such as OOOOOOO the encoder will show output Only1Node O 7.

Movie Scheduling Problem

Last night one of mine coding friend thrown a problem on me, & he called it as movie scheduling problem, He wanted me to develop a algo & code for this.

The Problem

Let x be a super-star
Let n be a Producer

n Producers wanted to cast x in there upcoming movie, and for that they are offering the same amount to x but the start & end date interval of each movie making process is different for eg. 1 movie require 10 months to complete whereas other require 1.5 yrs, now the algo. has to decide which movie x will do such that x will make the highest profit.

The criteria for job acceptance is clear: 

x want to make as much money as possible. Because each of these films pays the same fee

per film, this implies x seek the largest possible set of jobs (intervals) such that
no two of them conflict with each other.


I come up with 3 Algo's lets go through it one by one ...

ALGO 1: Earliest Job 1st

Suppose x don't have any work so he will select a movie which ever comes first
but this algo will not make the highest profit bcoz if actor select the 1st movie and the 2nd to 5th movie offers are such that the total time period require to complete all 4 movies is equal to time require to complete 1st movie.
So here the total loss is of 4 movies...


ALGO 2: Smallest Job 1st

This algo is better than the previous one bcoz it will give decent solution.

ALGO 3: Earliest Completion Date

This algo. gives optimal solutions for most of the possible inputs ...

I have coded the solution for Algo 3 whose output looks like ...

The Output
--------------------------------------------------------------------------------------------------------------
The output is a 4 dimension array where
0th column gives movie name
1st column gives start date
2nd column indicates end date
3rd column indicates status P or F , such that P indicate, the no. of movies has to be accepted by x to earn the maxm profit.

Download 

InOrder Traversal Of BST (Iterative Solution)

One best question in my sem-III DSF paper was 

Iterative Solution For Inorder Traversal

I was not prepare for it, but i was knowing the recursive way of traversing the BST tree so i applied  the same concept and find out a algo in 25 minutes sadly in 5 minutes or even less i couldn't complete that question and my ma'am snatch the paper, coz the time was 5:30 pm duhh!!

And after examz i came home and implemented that algo and it was 100% perfect solution for iterative way of Tree traversal , today i m gonna show that to you .......

The thing you must note, in the Stack implementation is that it does not store the data it store the refrence i.e a Node which inturn contains the data.

package datastructurepractice.BST;

/**
 *
 * @author Naved Momin
 */
class StackNode
{
    Node data;
    StackNode next;
}

public class StackForBST {
    StackNode top;
    
    public void push( Node x ){
        if( x != null )
        {
            StackNode newrec = new StackNode();
            newrec.data = x;
            newrec.next = null;
            if( top == null)
                top = newrec;
            else
            {
                newrec.next = top;
                top = newrec;
            }
        }

    }
    
    public void display( ){
        System.out.println( "stack display");
        if( isempty() )
            System.out.println(" empty stack ....");
        StackNode n = top;
        while( n != null){
            Node r = n.data;
            System.out.print (r.data + " ");
            n = n.next;
        }
    }
    
    boolean isempty( ){
        if( top == null)
           return true;
        else
            return false;
    }
    
    Node stacktop( ){
        if( top != null )
        return top.data;
        else
            return null;
    }
            
    
    
    public Node pop( ){
        if( !isempty() ){
            Node x = top.data;
            top = top.next;
            return x;
        }else{
            System.out.println( "stack out of data");
            System.exit(0);
            return null;
        }
    }
    
}


package datastructurepractice.BST;

import java.util.Calendar;
import java.util.Scanner;

/**
 *
 * @author Naved Momin
 */

class Node{
    int data;
    boolean lV = false, rV = false;
    Node left, right;
}
public class BST {
    Node root;
    private long start;
    private long end;
    
    public void travInorder( ){
        inorder(root);
    }
    
    public void insert( int x ){
        Node newrec = new Node();
        newrec.data = x;
        newrec.left = null;
        newrec.right = null;
        if( root == null){
            root = newrec;
        }
        else{
            Node a, b;
            a = b = root;
            while( a != null ){
                b = a;
                if( x < a.data ){
                    a = a.left;
                }else{
                    a = a.right;
                }
            }
            if( x <= b.data ){
                b.left = newrec;
            }else{
                b.right = newrec;
            }
        }
        

    }
    
    public void displayInorder( ){
        System.out.println( "inorder recurssive ");
        long start1 = Calendar.getInstance().getTimeInMillis();
        inorder(root);
        long end1 = Calendar.getInstance().getTimeInMillis();
        System.out.println( "total time taken (Recursive)" + (end1 - start1 ) + " ms");
        
        
        System.out.println( "inorder iterative ");
        start = Calendar.getInstance().getTimeInMillis();
        inOrderIterative(root);
        
        
    }
    
    public void delete( ){
        System.out.println( "enter value ot be deleted");
        int v = new Scanner(System.in).nextInt();
        
        Node a, b ;
        a = b = root;
        while( a != null && a.data != v){
            b = a;
            if( v < a.data )
                a = a.left;
            else
                a = a.right;
        }
        if( a == null )
            System.out.println( "i could not find the value");
        else{
            if( a.left != null && a.right == null){
                if( root == a){
                    root = a.left;
                }else{
                    if( a == b.left){
                        b.left = a.left;
                    }else{
                        b.right = a.left;
                    }
                }
            }
            else if( a.right != null && a.left == null ){
                if( root == a){
                    root = a.right;
                }else if( b.right == a){
                    b.right = a.right;
                }else{
                    b.left = a.right;
                }
            }else if( a.right == null && a.left == null){
                if( root == a){
                    root = null;
                }else if( b.right == a){
                    b.right = null;
                }else{
                    b.left = null;
                }
            }else if( a.right != null && a.left != null){
                Node c = a.right;
                while (c.left != null) {
                    c = c.left;   
                }
                c.left = a.left;
                if( a == root){
                    root = a.right;
                }else {
                    if( b.left == a)
                        b.left = a.right;
                    else
                        b.right = a.right;
                    
                }
                
            }
            System.out.println( "deleted node = " + v) ;
        }
    }
    
    
    
    boolean isempty( ){
        if( root == null)
            return true;
        else
            return false;
    }
    
    public void inOrderIterative( Node root ){
        StackForBST s = new StackForBST();
        s.push(root);
        
        while (true) {            
            Node r = s.stacktop();
           
            while( r.lV && r.rV ){
                s.pop();
                r = s.stacktop();
                
                if( r == null ){
                    end = Calendar.getInstance().getTimeInMillis();
                    System.out.println( "total time taken (Iterative)" + (end - start ) + " ms");
                    System.exit(0);//when stack becomes empty
                }
                    
            }
            
            
            
            if( !r.lV){
                while( r.left != null){
                    r.lV = true;
                    r = r.left;
                    s.push(r);
                }
            }
            r.lV = true;
            System.out.print(r.data + " ");
            
            if( r.lV == true && r.rV == false && r.right != null){
                r.rV = true;
                r = r.right;
                s.push(r);
            }else{
                r.rV = true;
            }
        
       }
        
        
    }
    
    
    
    public void inorder( Node root  ){
       
        if( root != null ){
            inorder(root.left);
            System.out.print( root.data + " ");
            inorder(root.right);
        }
        
    }
    public static void main(String[] args) {
        // TODO code application logic here
    }

}

//Output

run:
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
11111
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
22222
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
333333
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
444444
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
666666
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
555555
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
5656
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
4545
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
2323
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
1212
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
8989
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
45457
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
23235
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
232356
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
454545
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
232356
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
232345
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
232356
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
12214
enter 1 for insert 2 for delete 3 for display 4 for exits 
122
exits command executed
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
3
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
444
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
55
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
32
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
1
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
2
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
3
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
4
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
5
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
6
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
7
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
8
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
9
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
10
enter 1 for insert 2 for delete 3 for display 4 for exits 
3
inorder recurssive 
1 2 3 3 4 5 6 7 8 9 10 32 55 444 1212 2323 4545 5656 8989 11111 12214 22222 23235 45457 232356 232356 333333 444444 454545 555555 666666 
total time taken (Recursive)3 ms

inorder iterative 
1 2 3 3 4 5 6 7 8 9 10 32 55 444 1212 2323 4545 5656 8989 11111 12214 22222 23235 45457 232356 232356 333333 444444 454545 555555 666666 
total time taken (Iterative)13 ms

From this it looks like recursive approach is faster than iterative approach.......Hence we have proved that recursion is not always slow, there are some problems which are best solved(In terms of performance & simplicity) by "RECURSION".

Trace the code to get the algo. and slight modification will give you preorder & postorder....GL.