Wednesday, March 28, 2012

Recursion - Kanpsack Problem

Continuing my quest, playing with old computer science theories today i am writing about recursion and using it to solve similar issue as that of Knapsack problem. So, if you know about Recursion (like some flavor of it which i discussed in my last post) you would know its a very powerful tool which can be used to solve complex computer science problems.
In this approach we call same method from within a method with a base case which marks as its end, so we effectively call our self till we reach a base case and then we trace back till the starting. In java when a method call is placed in code it is loaded on to a stack in JVM which the run time environment will call, so if i call my self again and again i will end up having several stack entries of the same method and when the base case returns something it will unfold with last in last out rule.
As it may seem this is a powerful yet not that efficient tool as the repeated method calls can be expensive.

So, let's take a sample problem which is similar to Knapsack Problem remember Knapsack problem is a NP-complete problem hence no optimal solution exists for it. Please note this exercise is to understand and practice  recursion not to get the optimal solution to Knapsack Problem.

Problem
We have a array of descending numbers and we need to pick a set whose total is equal to the target.

E.g. array = 11, 8, 7, 6 ,5
Target Total = 20

We will create a program that can calculate the first set of numbers from this to get the result.


public class KnapsackProblem {
 
 private Stackx output;
 private int[] input;
 private int size;
 private int target;
 
 public KnapsackProblem(int target){
  this.input = new int[10];
  this.size = 0;
  this.output = new Stackx(10);
  this.target = target;
 }
 
 public void insert(int item) {
  input[size++] = item;
 }
 
 public void recKnapsack() {
  boolean flag = false;
  for (int i = 0; i < size; i++) {
   if (input[i] == target) {
    System.out.println("got it !");
   } else if (input[i] > target) {
    continue;
   } else if (input[i] < target) {
    boolean result = knapsackNew(target, i);
    if (result) {
     output.display();
     flag = true;
     break;
    } else{
     while(!output.isEmpty()){
      output.pop();
     }
    }
   }
  }
  if (flag) {
   System.out.println("  Success !!");
  } else {
   System.out.println("Cant find any conbination to get the target: " + target);
  }
  
 }

 public boolean knapsackNew(int target, int i) {
  if (i == size) {
   return false;
  }
  if (input[i] < target) {
   output.push(input[i]);
   return knapsackNew(target - input[i], ++i);
  } else if (input[i] > target) {
   return knapsackNew(target, ++i);
  } else if (input[i] == target) {
   output.push(input[i]);
   return true;
  }
  
  return false;
 }
 
 public static void main(String[] args) {
  KnapsackProblem obj = new KnapsackProblem(20);
  
  obj.insert(11);
  obj.insert(8);
  obj.insert(7);
  obj.insert(6);
  obj.insert(5);
  
  obj.recKnapsack();
 }
}
 

References :
Data Structures and Algorithms by Robert Lafore

Monday, March 26, 2012

Shell Sort - Let the shelling begin

So, many of us already know about insertion sort which is a nice sorting algorithm for sorting but lacks in performance, with complexity of O(n2), but gives a good performance when it comes to almost sorted list.

Using this property of fast processing in case of almost sorted list, Shell sort can achieve much better results then insertion sort. Shell sort does this by doing a "incremental sort" of the array. By that i mean it first divides the array into parts and sorts the elements relative to each other.

E.g. Array = 5 2 4 1 6 3 7

Lets take a interval of 4 and consider every 4rd element in this array

so we will compare 5, 1 and 7 and will sort these element relative to each other.

new Array = 1 2 4 5 6 3 7

In the next iteration we will consider a smaller number, finally we will reach to a point where we will have a interval of 1 and will be a simple insertion sort but by that time must of the element would be in there positions or very near to there final positions making this a fast iteration.

So we start with a big "Shell" and imagine these are the only elements in the array and sort then move on to making them smaller and smaller till we have a shell size of 1. As you may have noticed key is the division rule or the series(called a "Gap Sequence"or "Interval Sequence") we will use to decide on the shell sizes. Remember we need to have a series which ends with 1 so that we can run the insertion sort in the end. One of these series is provided by Kunth,

h = 3*h + 1

now in word of Kunfu Panda "enough talk, let's code"


 
 /**
 * This method will sort the array 
 * using Kunth's formula to calculate 
 * the bucket.
 */
public void shellSort() {
 int inner;
 int outer;
 int h = 1;
 /**
  * Calculate the bucket size to the max
  * then we move down till we reach around 1
  */
 while(h <= (nElemt/3)){
  h = h*3 + 1;
 }
 while(h > 0){
  for(outer = h; outer < nElemt; outer++){
   int temp = array[outer];
   inner = outer;
   while(inner > h-1 && 
                                    array[inner - h] >= temp){
    array[inner] = array[inner - h];
    inner -= h;
   }
   array[inner] = temp;
  }
  h = (h-1) / 3; //get the value of bucket back
 }
}

References :
Data Structures and Algorithms in Java by Robert Lafore

Tuesday, March 13, 2012

Merge Sort explained

For past few days i have been going back to basics. these are the topics which got me started with coding in the first place. Although these are simple topics in Computer science but form the very basic of coding in any language.

Well lets start off with some back ground about the Merge Sort. This basically comes from the family of algorithms which is based on divide and conquer methodology(If you know your history almost all civilizations at some point of time had someone playing this game in the kingdom).

The intent is to divide a big problem(in this case a array ) into smaller problems so that they can be solved easily(by easily i mean in few lines of code). Imagine if you have a array of 10,000 objects and you want to sort it according to their values (in this case we will take a simple example of a integer generally these are complex objects but the principle remains the same). If we divide this array till it becomes a single element then we simply compare the element and get the result, that forms the basis of this algorithm. We will divide a array till we have two arrays having only one element and then we compare them and merge the arrays.

So, we have two steps
  1. Divide till we reach to a point where we have 1 element which can be compared.
  2. merge the elements.
For all the math interest groups, these are Mathematical Induction problems where you have a base case (in this case a array with elements which can be compared and merged in one go) and the repeating case.

Merging 
Lets look at Merging two sorted arrays first. We will be doing this when we divide the single array into two and then we will merge it.

Input array A = 11,33,55,77,99
Input array B = 22,44,66,88

For merging these 2 arrays we will choose each element and compare with each other and push in a new array. 

Iteration 1: compare 11 with 22
11 is smaller hence we push it in a new array C and increment the counter for A. 
then we compare next element in A with same element in B i.e. 33 with 22 now 22 is smaller hence we push 22 in C and increment the counter for B.

array C : 11,22

After all the iteration we will have one single array with sorted elements.

Recursion
Now let's look at recursion part of it. Our focus here is to divide the problem into smaller parts till we reach the base case.
e.g. Input Array = 55,33,44,11,22

we will take a lower pointer (0 position ) and upper pointer(4 position) and calculate the mid. Now we will call the same method with upper pointer as mid and same value of lower pointer.
We will keep on calculating till we have lowerPtr == UpperPtr then we have only one element.

Similarly we will call same method again with mid as lower pointer and same value for upper pointer.

The code will look like this.

public void recMergeSort(int[] workspace, int lowerBound, int upperBound) {
if (lowerBound == upperBound) {
return;
} else {
int mid = (lowerBound + upperBound)/2;
recMergeSort(workspace, lowerBound, mid);
recMergeSort(workspace, mid + 1, upperBound);
merge(workspace, lowerBound, mid + 1, upperBound);
}
}
We use workspace array to hold the merged output

the last line submits the array to get it merged, here we will divide the same array in two parts from lower to mid and from mid+1 to upper.

Here is the Java code for it.

public void merge(int[] workspace, int lowPtr, int highPtr,
int upperBound) {
int i = 0; // workspace index
int lowerBound = lowPtr;
int mid = highPtr - 1;
int n = upperBound - lowerBound + 1;  // number of items
while (lowPtr <= mid && highPtr <= upperBound) {
if (array[lowPtr] < array[highPtr]) {
workspace[i++] = array[lowPtr++];
} else {
workspace[i++] = array[highPtr++];
}
}
while(lowPtr <= mid){
workspace[i++] = array[lowPtr++];
}
while(highPtr <= upperBound){
workspace[i++] = array[highPtr++];
}

for (int j = 0; j < n; j++) {
array[lowerBound + j] = workspace[j]; // copy the merged array back
}
}
Since we keep on dividing the array into 2 parts, the final time complexity of this algorithm is O(n log n)
Please keep in mind the base of Log is 2 here.

For better time complexity we compromise on space here as we are using 2 arrays of the same size, so if you are programming on device which is limited on size you might want to consider more complex sorting algorithms but more on that later.


References :
Data Structures & Algorithms in Java by Robert Lafore