Coding Recipies: November 2013

29 Nov 2013

DP: Longest Common Sub-Sequence

Problem Statement:
    Find the LCS or Longest Common Sub-sequence (not necessarily contiguous) of the two given Sequences.

Seq 1: P R A T E E K
Seq 2: R A T H O R E

LCS is : R A T E

Solution :

LCS applications:
1. Molecular Biology :
          To compare DNA sequences

2. File Comparison:
3. Screen Redisplay:
           As in Mobile display only the changed pixel are updated, instead of updating the whole screen.
This is problem is combinatorial in nature and therefore can be solved by Brute force,
Possible Subset of the given sequences of length m and n will be 2^m and 2^n respectively, which will be matched by one with each other. Thus , the Complexity of the algorithm will be exponential.

Now,
    Question is "Can we do Better" as Professor Tim Roughgarden says.

We can see this problem fulfilling the properties of Dynamic Programming.

Principle behind Dynamic Programming says , start with recursive algorithm , which may be inefficient because of repeated computation of sub-problems. Simply remember the solution of sub-problems, which reduce the recomputing and will be simply looked up when required.
Thus computation time reduces to proportional to the number of sub-problems.

Dynamic Programming Properties:
1. Optimal sub-structure :
       We can decompose our problem in to smaller sub-sequence and calculate solution for them.

Fig: Optimal Sub-Structure

2. Overlapping Sub-Problem:
Our Problem involves kind of recursion.

Given

Seq 1: P R A T E E K
Seq 2: R A T H O R E

Fig: LCS for given strings

Here ,all those characters are picked which come from diagonal cell, i.e. which are marked in orange, cell in green indicates the Longest Common Sub-sequence

Full Source Code: LINK

 /**
  * Longest Common Sequnece Subroutine
  */
 public static int lcs(String s1, String s2){

  char[] X = s1.toCharArray();
  char[] Y = s2.toCharArray();
  int[][] LCS = new int[Y.length +1 ][X.length +1 ];

  for(int i=1;i<=Y.length;i++)
  {
   for(int j=1;j<=X.length;j++)
   {
    if(Y[i -1 ]== X[j-1])
     LCS[i][j] = 1 + LCS[i-1][j-1];
    else
     LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
   }
  }

  // Start Trace Back
  StringBuilder sb= new StringBuilder();
  int i=Y.length ;
  int j=X.length ;

  while(i > 0 && j>0)
  {
   //System.out.println(i + " " + j);
   if(Y[i-1] == X[j-1])
   {
    sb = sb.append(X[j-1]);
    i--;
    j--;
   }
   else
   {
    if(LCS[i][j-1]> LCS[i-1][j])  
     j--;
    else
     i--;
   }
  }

  System.out.println(sb.reverse());
  return LCS[Y.length][X.length];
 }

References:1. http://www.ics.uci.edu/~eppstein/161/960229.html
2. Refer NPTEL videos of design and algoritms (IIT Mumbai)
3. http://www.youtube.com/watch?v=wJ-rP9hJXO0

Please comment and post suggestions

Happy Coding!! :)

Continuous Subsequence divisible by a number

Problem Statement:
What is the number of sub-sequences divisible by the given divisor ?

Given sequence:

{1 , 1 , 3 , 2 , 4, 1 ,4 , 5}
Divisor is 5

Answer is 11

Reference : Problem number 3 of
http://www.mii.lt/olympiads_in_informatics/pdf/INFOL062.pdf

Solution:

Our goal is find the number of continuous sub-sequences divisible by the divisor
We will group the pre-fixes of the given sequence by the remainders (here modulo 5) of the sums of their elements.
If there are 'k' prefixes for some remainder, then number of continuous sub sequences, with the sums of elements divisible by divisor (here 5) will be given by

ⁿC₂= k(k-1)/2

Full Source Code: LINK

Implementation:

        /**
  * Sub-Routine to count numnber of sub-sequnces
  * @param d: the given divisor
  */
 public static int solve(int[] arr, int d)
 {
  Object o;
  int Answer = 0;
  int[] hash = new int[d];

  int sum = 0;
  int val;
  int num;

  for (int i = 0; i < arr.length; i++) {
   num = arr[i];

   if(num % d == 0) // count numbers which are divisible by divisor
    Answer ++ ;

   sum +=  num; 
   val = sum % d;

   if(val<0) //handle negative numbers
    val = val * (-1);

   hash[val] = hash[val] + 1;
  }

  int size=hash.length ;
  for (int i = 0; i < size; i++)  {
   int count = hash[i];

   if(count > 1)
    Answer = Answer + count * (count -1)/2 ;
  }
  System.out.println(Answer+hash[0]);
  return Answer+hash[0];
 }

Users are requested to refer the reference.
If u liked my article please comment and like the page on facebook.
Happy Coding!! :)

Stack: Minimum Element Lookup with O(1)

Problem Statement:
Implement a Stack with Minimum Element look-up in Constant time.

Solution:
Full Source Code : LINK

For this problem we would require extra stack which will maintain the Minimum element on the top. This stack will always have minimum element on the top.

We will be customizing the "Push" and "Pop" operations slightly of the Custom Stack in order for constant look-up of minimum element in the Stack.
We will be using two stacks viz.

1. Original Stack: Stack holding the elements
2. Min Stack : Stack holding min element on top

Fig: Original Stack and Min Stack for the given Sequence

1. Push Operation:
           a) If element being pushed is smaller than the top element of Min Stack,
                           push to Original Stack and also Min Stack.
           b) If element being pushed is greater than the top element of Min Stack,
                           push to Original Stack.

Push Sub-routine implementation

       /**
  * Push Subroutine
  */
 @Override
 public void push(int data) {
  if(original.isEmpty())
   minStack.push(data);

  else{
   if(data < minStack.peek())
    minStack.push(data);
  }
  original.push(data);
 }

2. Pop Operation:
          a) If top element of Original Stack is equal to top element of Min Stack
                         pop Original Stack and also pop Min Stack
b) If top of Original Stack is not equal to top of Min Stack
           pop Original Stack only.

Pop Sub-routine implementation

        /**
  *Pops element from the custom stack 
  */
 @Override
 public int pop() {
  if(original.peek() == minStack.peek())
   minStack.pop();

  return original.pop();
 }

3. Get Minimum Operation:
Return the top element of Min Stack

4. Peek
Return top element of Original Stack

/**
  * Peek Minimum Element
  */
 @Override
 public int getMin(){
  return minStack.peek();
 }

 /**
  * Peek for the element
  */
 @Override
 public int peek() {
  return original.peek();
 }

 @Override
 public boolean isEmpty() {
  return original.isEmpty();
 }

Please comment and post your suggestion. Please "Like" page on facebook if u liked the article.
Happy Coding!! :)

Linked List: Deleted Node with given pointer

Problem Statement:
Given a pointer of a Singly Linked List, delete the node pointed by the given Pointer.

Given Linked List with given Pointer pointing to "2"

Fig: Linked List with given pointer at 2

Solution:

Here the trick is copy the content of the next node that is "3" here to the given node ("2" here)
and delete the next node.

public void deleteNode(Node current){
  Node nextNode = current.next;
  current.data=nextNode.data ;
  current.next = nextNode.next;
 }

The Node structure of Linked List

/**
 * Linked List Node
 * @author Prateek
 */
class Node {

 public int data;
 public Node next;
 
 public Node(int data){
  this.data=data;
 }
 
 public String toString(){
  return ""+data;
 }
}

Note: This logic is not applicable for the last node in the Linked List.

Please post your comment and suggestions.
Happy Coding!! :)

Insertion Sort

Problem Statement:
Implement and Discuss Insertion Sort

Solution:

Insertion Sort is one of the basic sorting techniques , which is simple but inefficient in sorting large amount of data as compared to Quick Sort, Merge Sort , Heap Sort etc ..

However Insertion sort has a number of advantages:

1. Adaptive: i.e. efficient for data sets that are already substantially sorted.
Time Complexity : O(n+d) , where d is the number of inversions.
2. Stable: does not change the relative order of elements with equal keys
3. In-Place : no additional space required.
4. Online : can sort as it receives the data.
5. More efficient than other quadratic algorithms O(n^2) like , Selection Sort and Bubble Sort,
best case is O(n) for insertion sort and worst case is O(n^2)

Humans usually sort the deck of cards using insertion sort.

Concept Involved:
For every iteration the element picked is inserted into its correct position in the already sorted array, for N element each element is picked and placed to its correct position.

Full Source Code: LINK

Code Implementation:

       /**
  * Insertion Sort Subroutine
  */
 public int[] insertionSort(int[] arr)
 {
  int size = arr.length;
  for(int i=1;i<size;i++){
   int j=i;
   int num=arr[i];
   while(j>0 && arr[j-1] > num){
    arr[j]=arr[j-1];
    j--;
   }
   arr[j]=num;
  }
  return arr;
 }

Steps involved in sorting the given sequence:
Sequence : {3, 7, 4, 9, 5, 2, 6, 1}

Fig: Sorting of 30 element array

3 7 4 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 5 7 9 2 6 1

2 3 4 5 7 9 6 1

2 3 4 5 6 7 9 1

1 2 3 4 5 6 7 9

Below is another graphical representation of intermediate step
of insertion sort.


Fig: Steps involved in Insertion Sort

References: Wikipedia
Try writing code for insertion sort by yourself
Please comment and post your suggestions.

Happy Coding!! :)

Queue

Problem Statement:
Implement Queue

Solution:

Given below is the kind of scenario in case of Queue Data structure ,
where items are pushed(en-queue-d) from rear and removed (de-queue-d) from front.

Fig: Example of Queue

Operations supported by Queue data structure are:
1. En-queue:
It means insertion of elements from rear pointer
2. De-queue:
It means deletion of items from front pointer.

A Queue supports FIFO operations i.e. First In First Out (FIFO)

Implementation:

-
/**
 * Queue Implementation
 * @author Prateek
 */
public class Queue {
 
 private static int DEFAULT_CAPACITY = 5;
 
 int front;
 int rear;
 int arr[];

 public Queue() {
  arr = new int[DEFAULT_CAPACITY];
  Arrays.fill(arr, -1);
  front = 0;
  rear = 0;
 }

 public Queue(int size) {
  DEFAULT_CAPACITY=size;
  arr = new int[DEFAULT_CAPACITY];
  Arrays.fill(arr, -1);
  front = 0;
  rear = 0;
 }
 
 public void push(int data) {
  rear = (rear) % (DEFAULT_CAPACITY);
  if (arr[rear] == -1) {
   arr[++rear] = data;
   System.out.println("Pushed: " + arr[rear - 1]);
  } else 
   System.out.println("Queue is Full");
 }

 public void pop() {
  int val = arr[front];
  arr[front] = -1;
  front++;
  System.err.println("Poped: " + val);
 }

 public void display() {
  System.out.print("Queue is : \t");
  int i = front;
  while (i <= DEFAULT_CAPACITY) {
   System.out.print(arr[i]+"\t");
   i = (i + 1) % DEFAULT_CAPACITY;
   if (i == rear)
    break;
  }
 }
}
-

References:
http://basicstodatastructures.blogspot.in/2013/10/queue.html from a good friend of mine.

Please post your comments and suggestions

Happy Coding!! :)

Stack

Problem Statement:
        Implement Stack

Solution:

Stack supports three main operations:
1. Push:
         Insertion of element
2. Pop:
       Removal of the last element inserted
3. Peek:

A stack supports LIFO operations i.e. Last In First Out (LIFO)
These all operations are assisted by the "top" pointer which tracks the top most element element in the stack.

Fig: Stack of books and Stack of Boxes

-
 /**
 * Stack Implementation
 * @author Prateek Rathore
 *
 */
public class Stack {
 int arr[];
 private static final int DEFAULT_CAPACITY = 10;
 public static int top = -1;
 
 public Stack() {
  arr = new int[DEFAULT_CAPACITY];
 }
 
 public Stack(int size) {
  arr = new int[size];
 }

 public void push(int data) {
  arr[++top] = data;
 }
 public int pop() {
  return arr[top--];
 }

 public int peek() {
           return arr[top];
 }
 
 public boolean isEmpty() {
  if(top==-1)
   return true;
  return false;
 }
}
-

References:
Refer to one of my friend's post on stacks: LINK

Please post your comments and suggestions.

Happy Coding !! :)

Is Binary Tree Symmetric

Problem Statement:
Check if the Given Binary Tree is Symmetric about the plane passing through root.

Fig: Symmetric Binary Tree about the place passing through root

Solution:
Full Source Code : LINK
Below is the recursive implementation to check if Binary Tree is Symmetric

       /**
  * Sub-routine to check if Binary Tree is Symmetric
  */
 public boolean isSymmetric(Node left, Node right){
  if ( (left==null && right!=null) || (left!=null && right==null) )
   return false;

  if(left==null && right==null)
   return true;

  return isSymmetric(left.left,right.right) && isSymmetric(left.right,right.left);
 }

Please comment and post your suggestions.
Happy Coding!! :)

25 Nov 2013

DP: Longest Increasing Sub-Sequence

Problem Statement:
Given a sequence , find the Longest sub-sequence which is increasing.
Given Sequence:

2 , 7 , 3 , 4 , 9 , 8 , 12

Resultant Longest sub-sequence is 2 , 3 , 4 , 9 , 12

Solution:

Full Source Code: LINK

What are the number of possbile subsets ?
= 2^n

We will solve this problem using Dynamic Programming(DP)
For a DP , it has the properties
1. Optimal Sub-Structure
It means if i have solution of sub- problems , and optimal solution of those sub-problems can be combined to get the solution of bigger problem..

We will define a term ,
L(i) = Length of the Longest Increasing Sub-Sequence which includes element arr[i] as its last element.

Equation for the optimal sub-structure
      L(i) = 1 + MAX ( L(j) )    , where 0<= j < i and A[i] > A[j]

2. Overlapping Sub-Problem:
We can observe that there are values which needs to be recomputed again and again, therefore its and overlapping.

Consider and example

As i have discussed in previous posts of DP(Dynamic Programming) can be solved by memomisation or tabulation method,
I have used tabulation method here to find the solution

Intermediate Steps involved for the given sample

 L(0) = 1   
 L(1) = 1 + Max(L(0))  
     = 1 + Max(1)  
     = 1 + 1  
     = 2  
 L(2) = 1 + Max(L(0))  
     = 1 + Max(1)  
     = 2  
 L(3) = 1 + Max(L(0),L(2))  
     = 1 + Max(1 ,2)  
     = 1 + 2   
     = 3  
 L(4) = 1 + Max(L(0),L(1),L(2),L(3))       
     = 1 + Max(1 , 2 , 2 , 3)  
     = 1 + 3  
     = 4  
 L(5) = 1 + Max(L(0),L(1),L(2),L(3))  
     = 1 + Max(1 , 2 , 2 , 3 )  
     = 4  
 L(6) = 1 + Max(L(0),L(1),L(2),L(3),L(4),L(5))  
     = 1 + Max(1 , 2 , 2 , 3 , 4 , 4)  
     = 5

Below is the logic of the sub-routine to find the increasing sub sequence:

 private static int[] LIS;  
 private static int[] sol; //Array to retrive the sequence
 static int tail=0;   //final element of sequence

 /**
  * Procedure to find LIS
  * @param arr : input array
  * @return longest value on increasing sub sequence
  */
 public static int lis(int[] arr){
  int len = arr.length ;

  LIS = new int[len];
  sol = new int[len] ; 

  Arrays.fill(sol, -1);

  LIS[0] = 1; //base case
  int MAX_LIS=1;  // default value
  int max; // gets max value for each i
  for(int i=1;i < len ; i++)
  {
   max=0;
   for(int j=0 ; j<i ; j++)
   {
    if(arr[i] > arr[j] && LIS[j] > max )
    {
      sol[i] = j ; //used to save
      max = LIS[j]; //update max for value of i
    }
   }
   LIS[i] = 1 + max ;

   if(LIS[i] > MAX_LIS){
    MAX_LIS = LIS[i];
    tail=i;
   }
  }

  printSequence(sol, arr);
  System.out.println("Sequence length : " + MAX_LIS);
  return MAX_LIS ;
 }

Below is the sub-routine to print the increasing sub-sequence computed from the above sub routine.

     public static void printSequence(int[] sol , int[] arr){
  System.out.println("Sequence : ");
  for (int j = tail; j >= 0; j = sol[j])
   System.out.print(arr[j]+"\t");
 }

Please comment and post suggestions , for the above code.

Happy Coding !! :)