Sem 6 MU Practical Programs

Hello Folks,

Blogging after a huge gap of 4 months or so, this semester was full of boring lectures still I have to attend them :(

I didn't blogged for a while coz I was busy preparing some xyz stuff cant reveal ...BIG SECRET :P

purpose of this post is to give away all my sem 6 practical programs ...download and enjoy!

spcc list

1. assembler
2. dll
3. macro
4. macro processor
5. operator Precedence
6. predictive Parser
7. program token generation
8. shift reduce

acn list

1. ftp
2. tftp

oose list

1. fp
2. cocomo

amp list

1. simulation of pipelining
2. simulation of branch pridiction logic
3. simulation of intruction pairing rules
4. simulation of mesi protocol_for_datacache
5. simulation of super scalar arch
6. si-protocol for code cache

dwm list

1. id3
2. kmeans clustering
3. kmedoids clustering
4. KNN classification
5. mst clustering
6. NB Classifier
7. NN clustering
8. simple linear regression

cn list

1. bellman ford
2. CheckSum
3. CRC
4. Hamming Code
5. Parity

ns2 & awk codes

1. First Sample
2. First Sample with awk codes
3. DVMRP with awk codes
4. mm1 & mm1re with awk codes
5. Centralized_Multicast with awk codes
6. Distance Vector NLink Failure with awk codes
7. TCP Analysis with awk codes

Download@

The Mean, Median & Mode Revisited

Problem:

Given a 2 sorted array find mean, median & mode

Solution:

1) Two Sorted arrays can be merged in O(n) time.
2) Calculating mean is simple i.e.
        a) calculate k = summation of mergedarray[i]
        b) do k/mergearray.length
        c) display k as mean value
3) Calculating Median
        a) In case total no of element is ODD, int m = mergedarray.length/2, then display m as median value
        b) In case total no of element is EVEN, int m = mergedarray.length/2,
            int val = (mergedarray[m]+mergedarray[--m])/2
            display val as median
4) Calculating Mode is simple i.e.
     -- find number which  occurs max number of times.

Code:

     

import java.util.ArrayList;


public class MyDS {

 int[] no,count;
 int ptr = 0;
 public MyDS(int n) {
  no = new int[n];
  count = new int[n];
 }
 
 public void add(int val, int occ) {
  no[ptr] = val;
  count[ptr] = occ;
  ptr++;
 }
 
 public ArrayList getModeValue() {
  int max = 0,z=0;
  ArrayList k = new ArrayList();
  for (int i = 0; i < count.length; i++) {
   if( count[i] > max) {
    max = count[i];
    z = i;
   }
  }
  k.add(no[z] + " " + max);
  for (int i = 0; i < count.length; i++) {
   if( count[i] == max && z != i ) {
    if(!k.contains(no[i] + " " + max))
    k.add(no[i] + " " + max);
   }
  }
  return k;
 }
 
 

}



import java.util.ArrayList;

public class Merge2SortedArray {

 int arr1[],arr2[],farr[];
 int ptr1,ptr2,fptr;
 
 void init(int[] a, int[] b ) {
  arr1 = a;
  arr2 = b;
  farr = new int[arr1.length+arr2.length];
  merge();
 }
 
 private void merge() {
  // TODO Auto-generated method stub
  /**
   * while-loop to tackle merging of sorted arrays of unequal length
   * for-loop is ok for merging equal length sorted array.
   * 
   */
  while (ptr1 <= arr1.length || ptr2 <= arr2.length) {
   if(arr1[ptr1] < arr2[ptr2]) {
    farr[fptr] = arr1[ptr1];
    fptr++;
    ptr1++;
   }else if( arr2[ptr2] < arr1[ptr1] ) {
    farr[fptr] = arr2[ptr2];
    fptr++;
    ptr2++;
   }else {
    farr[fptr] = arr1[ptr1];
    fptr++;
    farr[fptr] = arr1[ptr1];
    fptr++;
    ptr1++;
    ptr2++;
   }
   if(ptr1 >= arr1.length) {
    copyArr2();
    break;
   }else if( ptr2 >= arr2.length) {
    copyArr1();
    break;
   }
  }

  median();
  mean();
  MyDS ds = new MyDS(farr.length);
  
  for (int i = 0; i < c; i++) {
   int occurence = mode(farr[i]);
   ds.add(farr[i],occurence);
  }
  
  displayMode(ds);
 }

 private void displayMode(MyDS ds) {
  // TODO Auto-generated method stub
  ArrayList modeValue = ds.getModeValue();
  System.out.println("And the mode value is ");
  for (String string : modeValue) {
   System.out.println(string);
  }
 }

 private int mode(int k) {
  // TODO Auto-generated method stub
  int z = 0;
  for (int i = 0; i < c; i++) {
   if(farr[i] == k)
    z++;
  }
  return z;
 }

 private void mean() {
  // TODO Auto-generated method stub
  int sum =0;
  for (int i = 0; i < c; i++) {
   sum += farr[i];
  }
  System.out.println("And mean is " + sum/c);
 }
 
 int c = 0;
 private void median() {
  // TODO Auto-generated method stub
  
  for (int k : farr) {
   if(k != 0) {
    System.out.print(k + " ");
    c++;
   }
  }
  
  System.out.println("\n" + "And the median is ");
  
  if((c%2)==0) {
   int med = c/2;
   avgingMideans(med,--med);
  } else
   System.out.println(farr[((c+1)/2)-1]);
 }

 private void avgingMideans(int c2, int c3) {
  // TODO Auto-generated method stub
  int k = (farr[c2]+farr[c3])/2;
  System.out.println(k);
 }

 private void copyArr1() {
  // TODO Auto-generated method stub
  for (int i = ptr1; i < arr1.length; i++) {
   farr[fptr] = arr1[i];
   fptr++;
  }
 }

 private void copyArr2() {
  // TODO Auto-generated method stub
  for (int i = ptr2; i < arr2.length; i++) {
   farr[fptr] = arr2[i];
   fptr++;
  }
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int[] a = {6,6};
  int[] b = {2,4};
  new Merge2SortedArray().init(a  ,b);
 }
}

GOOD LUCK!  Merry Christmas & Happy New Year !!

Break The Integer

Problem:

Given an integer n, break it in smallest non-repeating subsets.

Eg 1: 5
1 1 1 1 1
2 1 1 1
3 1 1
4 1
5

Eg 2: 10
1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
3 1 1 1 1 1 1 1
4 1 1 1 1 1 1
5 1 1 1 1 1
6 1 1 1 1
7 1 1 1
8 1 1
2 2 2 2 2
3 3 3 1
4 4 2
5 5
6 4
7 3
8 2
9 1
10

Time Complexity (for main logic):

n + n + n + n (for 4 loops)

i.e. 4n

i.e. O(n)

O(n) extra space.

Code:

public class SplitTheInteger {

 private int userInput;
 int[] temp;

 void start( int no ) {
  
  userInput = no;
  temp = new int[userInput];
  
  for (int i = 0; i < userInput; i++) {
   temp[i] = 1;
  }
  
  int len = userInput-1;
  
  /**
   * its working for userinput 5
   * 1 1  1  1  1
   * 2 1  1  1 -1
   * 3 1  1 -1 -1
   * 
   * 4 1 -1 -1 -1 //this is taken care by for
                 *  
                 * loop below while loop so to avoid redundancy i have 
   * made 'no-1'
   * 
   * 5
   */
  while (temp[0] != no-1 ) {
   algo();
   temp[0]++;
   temp[len] = -1;
   len--;
   
  }
  
  for (int i = 2; i <= userInput; i++) {
   /**
    * Suppose i = 3
    * UserInput = 10
    * 10/3 = 3
    * so print 3 three times and call done which will select 
    * such a number that will sum up UserInput i.e. 10
    */
   int m = userInput/i;
   int count = 0;
   while ( count != m ) {
    System.out.print( i + " ");
    count++;
   }
   if(i*count != userInput)
    done(count*i);
   System.out.println();
  }
  

  
 }
 
 
 private void algo() {
  // TODO Auto-generated method stub
  int z = temp[0];
  for (int k : temp) {
   if( k != -1)
    System.out.print(k + " ");
  }
  System.out.println();
  
    
 }


 private void done(int i) {
  // TODO Auto-generated method stub
  for (int j = 1; j <= userInput; j++) {
   if(j+i == userInput) {
    System.out.print(  j );
    break;
   }
   
  }
 }


 public static void main(String[] args) {
  // TODO Auto-generated method stub
  new SplitTheInteger().start(10);
  
 }

}

Good Luck! & Happy Coding!!!

Turing Machine

Problem:

Design a TM to perform addition of 2 integers.

Background:

I am using TM with one way infinite tape

Time Complexity (for compute function):

O(m) where m is no1+no2

no1 is 1st operand for addition & no2 is second

Code:

import java.util.Scanner;

public class Adder {

 int head,sum;
 char[] tape;
 
 void init( ) {
  //one way infinite tape 
  tape = new char[37677];
  for (int i = 0; i < tape.length; i++) {
   tape[i] = 'B';
  }
  Scanner s = new Scanner(System.in);
  System.out.println("enter no1");
  int no1 = s.nextInt();
  System.out.println("enter no2");
  int no2 = s.nextInt();
  int p = 0;
  for (int i = 0; i < no1; i++,p++) {
   tape[i] = '0';
   
  }
  tape[p] = '1';
  p++;
  for (int i = 0; i < no2; i++,p++) { 
   tape[p] = '0';
  }
  compute();
 }
 private void compute() {
  // TODO Auto-generated method stub
  for (int i = 0; i < tape.length; i++) {
   if(tape[i] == '1') {
    tape[i] = '0';
   }
   if(tape[i] == 'B')
    reverse(i);
  }
 }
 
 private void reverse(int i) {
  // TODO Auto-generated method stub
  --i;
  tape[i] = 'B';
  for (int j = 0; j < tape.length; j++) {
   if(tape[j] != 'B')
    sum++;
  }
  System.out.println("sum is = " + sum);
  System.exit(0);
 }
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  new Adder().init();
 }

}

Cut The Rope

Problem:

Given a integer n, find all the subsets of n such that product obtained is maximum.

Eg 1: n = 10 {3 ,3 ,4} gives us 36 (highest product)

Eg 2: n = 20 {3 ,2 ,3 ,4 ,5 ,3} gives us 1080 (highest product)

Background:

At first glance i saw this problem as a inverted sum of subset problem, where we have given subsets as well as sum, but it is inverted because here we have just sum (n here) no subsets , we have to find all the subsets as a part of the solution.

After finding 1st subset store it somewhere, find next, now compare 1st and 2nd subsets product,

if 2nd subset-product > 1st subset-product

   store 2nd subset-product in some variable

repeat it until loops are exhausted.

Instead of solving it recursively i tried to solve it with tight for loops and a while loop.

Time Complexity:

O(n^2) and additional O(n) extra space.

Code:

import java.util.ArrayList;

public class CutTheRope {

 private int val;
 private int highval;
 private int m;
 /**
  * @param n
  */
 void start( int n ) {
  
  for (int i = 2; i < n-1; i++) {
   ArrayList myList = new ArrayList();
   myList.add(i);
   boolean isTrue = false;
   while (!isTrue) {
    
    
    for (int j = 2; j < n-1; j++) {
     int k = 0;
     for (Integer integer : myList) {
      k += integer.intValue();
     }
     //k+j+1 should not be equal to n ...
                                        //bcoz we r not staring loop from 1 its from 2
     if(k+j <= n && (k+j+1) != n)
      myList.add(j);
     if(k+j==n) {
      isTrue = true;
      break;
     }
    }
   }
   for (Integer integer : myList) {
    val = mult(integer.intValue());
    //System.out.print(integer + " ,");
   }
   //System.out.println();
   
   if (m >= 1) {
    if (highval < val)
     highval = val;
   }else {
   m++;
   highval = val;
   }
   k = -1;
  }
  if(highval != 0)
 System.out.println(highval);
   else
 System.out.println(n);
 }
 
 int k =-1;
 private int mult(int intValue) {
  // TODO Auto-generated method stub
  if(k == -1) {
   k = intValue;
  }
  else
  {
   k *= intValue;
  }
  return k;
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  new CutTheRope().start(22);
 }

}

Try it!

Good Luck.......

Can You Find Longest Palindrome??

Placements            Placements            Placements!!!

This period of time I.e from September to I guess April is a golden period for all final year engineering students as many companies come to respective colleges paying different amount of salary “k” where k ranges between 2.50 <= k <= 7 lac/annum (at-least in my college).

Today as usual I was heading to my college in 8:24 CST train, in my compartment there were 2 students both were dumb, dumb because one of them was telling to other that “I couldn’t be able to write code for prime number during 1 to 1 PI (Personal Interview)” shit and still this people call themselves computer science majors ...duhh!!!

So I thought why not to write a series of blogs which will showcase some of the challenging problems in CS ranging from simplest to most challenging one's...HOPE THIS WILL HELP!

#1 Longest Palindrome

Problem statement:- Given a string “S”  find longest possible substring “Si” such that

0 <=s<=n

Where n is length of string S and s is length of String Si.

public class LongestSubstring {

    void start( ){
       String s = new Scanner(System.in).nextLine();
       palindrome(s);
   }
  
    public static void main(String[] args) {
       
        new LongestSubstring().start();
    }

    char[][] c;
    int uptr = 0,lptr = 1;
    private void palindrome(String s) {
        char[] str = s.toCharArray();
        c = new char[2][str.length];
        System.arraycopy(str, 0, c[lptr], 0, str.length);
        int j = str.length-1;
        for (int I = 0; I <= j; I++,j--) {
            if( str[I] == str[j] )
                c[uptr][I] = c[uptr][j] = '1';
            
        }
        int res = 0;
        for (int I = 0; I < c[0].length; I++) {
            if( c[uptr][I] == '1'){
                System.out.print(c[lptr][I]);
                res++;
            }
         }
        System.out.println();
        System.out.println("len of largest palindrome = " + res);
    }
}

OUTPUT:

#1 abgaffdgba

Longest palindrome – abgffgba

Stay hungry stay foolish!

Mod2 Division

 Hi there, its been a while i have not posted any thing just busy with my strong & hectic college schedule, today i m posting one of my work called

MOD2 DIVISION.

There is a reason to code this small library which performs mod2 division :
And the reason is , when implementing CRC in software we need to perform mod2 division.

for those who don't know what is CRC?.

How to use this Library ?

Modulo2Div modulo2Div = new Modulo2Div();
modulo2Div.setDividend("1111101");
modulo2Div.setDivisor("10001");
modulo2Div.mod2Div();
System.out.println( "QUo = " + modulo2Div.getQue() + " Rem = " + modulo2Div.getRem());

Note: inorder to use this library you must set this mod2lib.jar in your classpath.

Download

Problem #1

Little penguin Polo adores strings. But most of all he adores strings of length n.

One day he wanted to find a string that meets the following conditions:

1. The string consists of n lowercase English letters (that is, the string's length equals n), exactly k of these letters are distinct.
2. No two neighbouring letters of a string coincide; that is, if we represent a string as s = s₁s₂... s_n, then the following inequality holds, s_i ≠ s_i + 1(1 ≤ i < n).
3. Among all strings that meet points 1 and 2, the required string is lexicographically smallest.

Help him find such string or state that such string doesn't exist.

String x = x₁x₂... x_p is lexicographically less than string y = y₁y₂... y_q, if either p < q and x₁ = y₁, x₂ = y₂, ... , x_p = y_p, or there is such number r (r < p, r < q), that x₁ = y₁, x₂ = y₂, ... , x_r = y_r and x_r + 1 < y_r + 1. The characters of the strings are compared by their ASCII codes.

Input

A single line contains two positive integers n and k (1 ≤ n ≤ 10⁶, 1 ≤ k ≤ 26) — the string's length and the number of distinct letters.

Output

In a single line print the required string. If there isn't such string, print "-1" (without the quotes).

Sample test(s)

input

7 4

output

ababacd

input

4 7

output

-1

Solution

Solution for the above problem can be downloaded from here

Sum Of Subset (Using PowerSet)

for those who don't know sum of subset problem just google it.

But allow me to explain what is power set 

e.g. let X be an set, X = { 1,2,3}
then power set will contain = 2^n subset of set X, where n is no. of elements in set X
so our power set will contain total 8 subset of set X
power set = { , {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }
notice that the 1st set is a null set because a null set is a subset of every set.

Now consider sum of subset problem 
let X be an array which contains input from user let X = {1,2,3}
then power set = { , {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }
let m = 3

then the output of sum of subset problem is { {3},{1,2} }

if you are reading from beginning than now you must have a fair idea about what we are going to do, if you didn't understand than chill, the concept will be very clear in 5 minutes from now.

once we have computed the power set, we will take each individual set from the power set, if the power set contains only 1 element than we will compare that element with m if that element is equal to m than we will print that set as  1 of the solution, but if set contain multiple elements in it than we will add them all and compare the sum with m if it is equal than we will print the set. that's it!

Program:

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;


 //@author Naved Momin navedmomin10@gmail.com;

public class SumOfSubsets {


    public ArrayList powerSet(int a[]){
        ArrayList pw = new ArrayList();
        
        pw.add(" ");
        for (int i = 1; i <= a.length; i++) {
            ArrayList tmp = new ArrayList();
            
            for (String e : pw) {
                if(e.equals(" "))
                    tmp.add(""+a[i-1]);
                else
                    tmp.add(e+ " " + a[i-1]);
            }
            pw.addAll(tmp);
        }
       
        return pw;
    }
    int m ;
   
    
    public void navedsSOS( ArrayList p ){
        int sum = 0;
        System.out.println( "output: ");
        for (String string : p) {
            
                String[] split = string.split(" ");
                
                if(split.length > 1){
                    for (String no : split) {
                    sum += Integer.parseInt(no); 
                    }
                    if( sum == m){
                        if(!set.contains(string)){
                            set.add(string);
                            System.out.println( string );
                           
                        }
                    }
                    sum = 0;
                }else if( split.length == 1){
                    int k = Integer.parseInt(string);
                    if( k == m ){
                        if(!set.contains(string)){
                            System.out.println( " " + k );
                            set.add(string);
                        }
                    }

                }
            
        }
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        SumOfSubsets s = new SumOfSubsets();
        s.init();
    }
    int n ;
    int arr[];
    Scanner s = new Scanner(System.in);
    Set set = new LinkedHashSet();
    private void init() {
        System.out.println( "enter n ");
        n = s.nextInt();
        System.out.println( "enter m ");
        m = s.nextInt();
        arr = new int[n];
        System.out.println( "enter elemets ");
        
        
        
        for (int i = 0; i < n; i++) {
            arr[i] = s.nextInt();
                    
            //set.add(arr[i]);
        }
  
        ArrayList powerSet = powerSet(arr);
        navedsSOS(powerSet);
    }
}

outout:

Round Robin In Java

for those who don't know Round Robin algorithm

Program

import java.util.Scanner;

 
 //@author Naved Momin naved.spartans.rocks75@gmail.com/navedmomin10@gmail.com
 
public class SimpleRR {

    int [] temp;
    int commBT, k, tq;
    int[][] d;
    int btcache;

    
    void getData( ){
        Scanner s = new Scanner(System.in);
        System.out.println( "enter no. of process");
        int pcount = s.nextInt();
        d = new int[pcount][2];

        temp = new int[pcount];
        System.out.println( "enter BT");
        for (int i = 0; i < pcount; i++) {
            d[i][0] = i;

            int m = s.nextInt();
            d[i][1] = m;

            commBT += m;
        }
        System.out.println( "enter TQ ");
        tq = s.nextInt();
        start();
        display( );
        
    }
    void start( ){
        for (int i = 0; i < d.length; i++) {
            int bt  = d[i][1];
            if( bt > 0){
                if( bt <= tq){
                    temp[i] = btcache+bt;
                    btcache = temp[i];
                    k += bt;
                    bt -= bt;
                     
                }
                else{
                    temp[i] = btcache+tq;
                    btcache = temp[i];
                    bt -= tq;
                    k += tq;
                }
                
                d[i][1] = bt;
               
                
            }
        }
        if( k!= commBT)
            start();
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        SimpleRR r = new SimpleRR();
        r.getData();
    }

    private void display() {
        float val = 0;
        int c = 1;
        for (int i : temp) {
            System.out.println( "BT for process " + c + " is " + i );
            val += i;
            c++;
        }
        System.out.println( "avg BT = " + val/temp.length);
    }
}

The above code finds & prints turn-around time & average turn around time for the given data.

Output

Finding Nth Largest Term In Unsorted Array

Given a task of finding nth largest term in an unsorted array by obeying following rules ...

Rules

1. You cannot sort an array
2. You cannot use a single library function (No API calls are allowed)
3. A separate copy of array should not be created

This can be easily implemented using a stack where we will start filling the stack with the smallest element, such that at the end we will get largest term at the top.

Algorithm:

1. accept array elements
2. determine the minimum element from the array
3. insert it into the stack
4. repeat step 2 & 3 until stack contains all elements of array
5. accept nth position from the user, say x
6. return the element which is stored at the x position
7. display the result
8. stop

Psuedo code for finding minimum element in an array

imin <-- 0;

        for ( i <-- 0; i < arr.length; i++) {

            imin <-- i;

            for (j <-- 0; j < arr.length; j++) {

                if( a[j] < a[imin] ){

                    imin <-- j;

                }

            }

        }

where " imin " stores index of the minimum element.

Code

package Kthlargestterm;

import java.util.Scanner;

 //@author Naved Momin(navedmomin10@gmail.com)
 
public class KthLargestTerm {

    static int[] a;
    static Scanner s = new Scanner(System.in);
    static int counter = 0;
    static StackUsingLL stack = new StackUsingLL();
    
    public KthLargestTerm(int size) {
        a = new int[size];
    }
    
    int getMin( ){
        int imin = 0;
        for (int i = 0; i < a.length; i++) {
            imin = i;
            for (int j = 0; j < a.length; j++) {
                if( a[j] < a[imin] ){
                    imin = j;
                }
            }
        }
        int k = a[imin];
        a[imin] = Integer.MAX_VALUE;
        return k;
    }
    
     
     static void getData( ){
        System.out.println( "enter size "); 
        int n = s.nextInt();
        KthLargestTerm kth = new KthLargestTerm(n);
        System.out.println( "enter data ");
        for (int i = 0; i < n; i++) {
            a[i] = s.nextInt();
        }
        
        int min = kth.getMin();
         int c = 0;
        while ( min != Integer.MAX_VALUE && c < n ) {             
            if(!stack.contains(min))
                stack.insert(min); 
            
            min = kth.getMin();
            c++;
         }
        
        System.out.println( "enter nTh position to view nth largest term ");
        int m = s.nextInt();
         while (m != -1) {     
             if( m >= 0 ) {
                    int item = stack.getItem(m);
                    String str =  (m == 1) ? "st" 
                            : (m==2) ? "nd" 
                            : (m == 3 ) ? "rd"
                            : "th";
                    
                    System.out.println( m + str +  " largest term is " + item );
                }
             System.out.println( "press -1 to exit or press any key to continue...");
             m = s.nextInt();
             if( m != -1 ){
                System.out.println( "enter nTh position to view nth largest term ");
                m = s.nextInt();
                
             }
         }
        
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        getData();
    
    }
}   




class Node{
    int data;
    Node next;
}

public class StackUsingLL {
 
    Node top ;
    static int insertAccount = 1;
    
    public boolean isempty( ){
       if( top == null ){
           return true;
       }else
           return false;
    }
    
    public void insert( int x ){
        Node newrec  = new Node();
        newrec.data = x;
        newrec.next = null;
        
        if( top == null ){
            top = newrec;
        }else{
        newrec.next = top;
        top = newrec;
        }

      insertAccount++;
    }
    
    public int delete( ){
        if( isempty() ){
            System.out.println( "stack empty" );
        return -1;
        }
        else{
            int x = top.data;
            top = top.next;
            return x;
        }
    }
    
    public boolean hasNext( ){
        
        if( top != null ){
            return true;
        }
        else{
            return false;
        }
    }
    
    public boolean contains( int min ){
        boolean val = false;
        Node p = top;
        while ( p != null ) {            
            if( stackTop( ) == min ){
                val = true;
                break;
            }
            else
                val = false;
            p = p.next;
        }
        return val;
    }
    
   public int getItem( int index ){
        if( index <= insertAccount ){
            int i = 1;
            int d = -1;
            Node p = top;
            while (p != null) {            
                if( index == i ){
                    d = p.data;
                    break;
                }
                i++;
                p = p.next;
            }
            return d;
        }else{
            System.err.println( "index was out of range ...");
            return -1;
        }
    }
    
    public int stackTop(){
        return top.data;
    }
    
    public void display( ){
        if( isempty() )
            System.out.println( "stack empty");
        else{
            Node p = top;
            while (p != null) {
                System.out.println( p.data + " ");
                p = p.next;
            }
        }
    }
    
}

Output

In case you want *.jar file then download it from here

Correct Implementation of Insertion Sort

Given a task of implementing insertion sort, many people end up with following code 

    
void insertionSort(int a[]){
 for (int i = 0; i < a.length; i++) {
                
                for (int j = i; j > 0; j--) {
                    int k = j-1;
                        if( a[j] < a[k]){
                            int temp = a[j];
                            a[j] = a[k];
                            a[k] = temp;
                        }
                    
                }
 }
}

Although the code works as expected & sorts the given data in O(n^2) time, but this is the wrong implementation of insertion sort.

Do You Know Why ?

The reason is best case time complexity of insertion sort is O(n) but this code has O(n^2), in short no matter what sequence of data you through at this code it will take O(n^2) time i.e best, avg. & worst case time complexity of this code is O(n^2).

Note: If you have clear your "Analysis of Algorithms & Design" paper you will understand what is written above.

If you have understand the above statements than you can fix the wrong implementation on your own, the above implementation can be corrected by just adding one statement which i left it for you as an exercise.

In case you are in hurry you can adopt My way to write insertion sort

Correct Implementation 

    
 int[] insertionSort(int [] a ){
        for (int j = 1; j < a.length; j++) {
            int i = j-1;
            while ( ( i >= 0 ) && a[i] > a[i+1] ) {                
                int k = a[i];
                a[i] = a[i+1];
                a[i+1] = k;
                i -= 1;
            }
        }
        return a;
    }

The best case time complexity(i.e when array elements are already in ascending order) of this code is O(n) & worst case time complexity is O(n^2), which proves that this code is correct implementation of Insertion Sort.

Swapping Using 2 Variables

Some of mine friends asked me a question, the Question was

Agreed that we can swap two numbers using some math, but how can we swap two chars & string without using 3rd variable ?

This blog post will answer the question, the method i have used is preety simple & straight forward
We will do following swapping

• Number Swapping
• Chars Swapping 
• Strings Swapping

To begin with lets quickly see the codes

• Number Swapping

 void swappingNumbers( int a, int b ){

        System.out.println( "input value  a = " + a + "  b = " + b );
        a = a+b;
        b = a-b;
        a = a-b;
        System.out.println( "swapped values a = " + a + " " + " b = " + b );
    }

The above code swaps two ( signed & unsigned ) numbers without using any 3rd variable

• Chars Swapping 

 void swappingChars(char a, char b ){
        System.out.println( "input value  a = " + a + "  b = " + b );
        int p = (int)a ,q = (int)b;
        p =  ( ( (int) p ) + ((int)q) ) ;
        q = ( ( (int) p ) - ((int)q) ) ;
        p = ( ( (int) p ) - ((int)q) ) ;
        System.out.println( "swapped values p = " +  ( (char)p) + " q = " + ((char)q) );
    }

The above code swaps 2 chars without using 3rd variable. Here using two variable i.e p & q we have swap the chars

• String Swapping

 
void swappingStrings(String str1, String str2){
        System.out.println( "input value  str1 = " + str1 + "  str2  = " + str2 );
        str2 = str1 + " " + str2;
        String[] split = str2.split(" ");
        str1 = split[1];
        str2 = split[0];
        System.out.println( "swapped values = str1 = " + str1 + " str2 = " + str2);
    }

The above code swaps 2 Strings without using 3rd variable.

Output

Hope this helps.

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