Dynamic Programming - Egg Dropping Puzzle

Dynamic Programming -- Egg Dropping Puzzle

The following is a description of the instance of this famous puzzle involving n=2 eggs and a building with k=36 floors.

Suppose that we wish to know which stories in a 36-story building are safe to drop eggs from, and which will cause the eggs to break on landing.

 We make a few assumptions:

1)An egg that survives a fall can be used again.
2)A broken egg must be discarded.
3)The effect of a fall is the same for all eggs.
4)If an egg breaks when dropped, then it would break if dropped from a higher floor.
5)If an egg survives a fall then it would survive a shorter fall.
6)It is not ruled out that the first-floor windows break eggs, nor is it ruled out that the 36th-floor do not cause an egg to break.

If only one egg is available and we wish to be sure of obtaining the right result, the experiment can be carried out in only one way. Drop the egg from the first-floor window; if it survives, drop it from the second floor window. Continue upward until it breaks.

 In the worst case, this method may require 36 droppings. Suppose 2 eggs are available. What is the least number of egg-droppings that is guaranteed to work in all cases?

The problem is not actually to find the critical floor, but merely to decide floors from which eggs should be dropped so that total number of trials are minimized.

Solution:

When we drop an egg from a floor x, there can be two cases (1) The egg breaks (2) The egg doesn’t break.

1) If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs

2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.

Since we need to minimize the number of trials in worst case, we take the maximum of two cases. We consider the max of above two cases for every floor and choose the floor which yields minimum number of trials.

  k ==> Number of floors
  n ==> Number of Eggs
 
  eggDrop(n, k) ==> Minimum number of trails needed to find the critical floor in worst case.
  eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1) , eggDrop(n, k - x)) :x in {1, 2, ..., k}}

Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */

public class EggDropingProblemApp
{
public static int max(int a, int b)
{
return (a > b)? a: b;
}
   public static int eggDrop(int n, int k)
    {
        int eggFloor[][] = new int[n+1][k+1];
        int res;
        int i, j, x;
         
        for (i = 1; i <= n; i++)
        {
            eggFloor[i][1] = 1;
            eggFloor[i][0] = 0;
        }
         
        for (j = 1; j <= k; j++)
            eggFloor[1][j] = j;

        for (i = 2; i <= n; i++)
        {
            for (j = 2; j <= k; j++)
            {
                eggFloor[i][j] = Integer.MAX_VALUE;
               
                for (x = 1; x <= j; x++)
                {
                     res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
                     if (res < eggFloor[i][j])
                        eggFloor[i][j] = res;
                }
            }
        }  
       return eggFloor[n][k];
    }

public static void main(String[] args)
{
     int n = 2, k = 10;
    System.out.println("Minimum number of trials in worst case with "+n+"  eggs and "+k+"                   floors is "+eggDrop(n, k));
}
}

Output: Minimum number of trials in worst case with 2  eggs and 10 floors is 4

Time Complexity:  O(nk^2)
Auxiliary Space: O(nk)

Dynamic Programming - Coin Change

Dynamic Programming -- Coin Change Problem

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

For example, 
for N = 4 and S = {1,2,3},
there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4.
 For N = 10 and S = {2, 5, 3, 6}
 there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}.
 So the output should be 5.

 Solution:

 To count total number solutions, we can divide all set solutions in two sets.

1) Solutions that do not contain mth coin (or Sm).
2) Solutions that contain at least one Sm.

Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).

Sample Code:

import java.util.Arrays;
/**
 * @author Abhinaw.Tripathi
 *
 */
public class CoinChangeApp
{
public static long countWays(int S[], int m, int n)
{
       long[] table = new long[n+1];
       Arrays.fill(table, 0);         // this will take o(n)
       table[0] = 1;

       for (int i=0; i<m; i++)
           for (int j=S[i]; j<=n; j++)
               table[j] += table[j-S[i]];

       return table[n];
}
public static void main(String[] args)
{
int arr[] = {1, 2, 3};
        int m = arr.length;
        int n = 4;
        System.out.println("Output: "  +countWays(arr, m, n));
}
}


Output: 4

Time Complexity:O(mn)

Dynamic Programming - Min Cost Path

Dynamic Programming - Min Cost Path

Given a cost matrix cost[][] and a position (m, n) in cost[][],
write a function that returns cost of minimum cost path to reach (m, n) from (0, 0).

 Each cell of the matrix represents a cost to traverse through that cell. Total cost of a path to reach (m, n) is sum of all the costs on that path (including both source and destination). You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed. You may assume that all costs are positive integers.

 The path to reach (m, n) must be through one of the 3 cells:
 (m-1, n-1) or (m-1, n) or (m, n-1).

 So minimum cost to reach (m, n) can be written as “minimum of the 3 cells plus cost[m][n]”.

Solution: 

minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n]

Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class MinCostPathApp
{
private static int min(int x, int y, int z)
{
       if (x < y)
           return (x < z)? x : z;
       else
           return (y < z)? y : z;
 }

private static int minCost(int cost[][], int m, int n)
{
       int i, j;
       int tc[][]=new int[m+1][n+1];

       tc[0][0] = cost[0][0];

       /* Initialize first column of total cost(tc) array */
       for (i = 1; i <= m; i++)
           tc[i][0] = tc[i-1][0] + cost[i][0];

       /* Initialize first row of tc array */
       for (j = 1; j <= n; j++)
           tc[0][j] = tc[0][j-1] + cost[0][j];

       /* Construct rest of the tc array */
       for (i = 1; i <= m; i++)
           for (j = 1; j <= n; j++)
               tc[i][j] = min(tc[i-1][j-1],
                              tc[i-1][j],
                              tc[i][j-1]) + cost[i][j];

       return tc[m][n];
   }

public static void main(String[] args)
{
int cost[][]= {{1, 2, 3},{4, 8, 2},{1, 5, 3}};
        System.out.println("minimum cost to reach (2,2) == " + minCost(cost,2,2));
}

}

Output: minimum cost to reach (2,2) == 8

Time Complexity: O(mn) which is much better than Naive Recursive implementation.

Find common elements in three sorted arrays

Find common elements in three sorted arrays

Given three arrays sorted in non-decreasing order, print all common elements in these arrays.

Examples:

ar1[] = {1, 5, 10, 20, 40, 80}
ar2[] = {6, 7, 20, 80, 100}
ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}

Output: 20, 80

ar1[] = {1, 5, 5}
ar2[] = {3, 4, 5, 5, 10}
ar3[] = {5, 5, 10, 20}

Output: 5, 5

A simple solution is to first find intersection of two arrays and store the intersection in a temporary array, then find the intersection of third array and temporary array.

Time complexity of this solution is O(n1 + n2 + n3) where n1, n2 and n3 are sizes of ar1[], ar2[] and ar3[] respectively.

The above solution requires extra space and two loops, we can find the common elements using a single loop and without extra space. The idea is similar to intersection of two arrays. Like two arrays loop, we run a loop and traverse three arrays.

Let the current element traversed in ar1[] be x, in ar2[] be y and in ar3[] be z. We can have following cases inside the loop.

1) If x, y and z are same, we can simply print any of them as common element and move ahead in all three arrays.
2) Else If x < y, we can move ahead in ar1[] as x cannot be a common element
3) Else If y < z, we can move ahead in ar2[] as y cannot be a common element
4) Else (We reach here when x > y and y > z), we can simply move ahead in ar3[] as z cannot be a common element.

Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class FindCommonElement
{
public void findcommonElement(int arr1[],int arr2[],int arr3[])
{
int i=0, j=0 , k=0;

while(i < arr1.length && j<arr2.length && k<arr3.length)
{
if(arr1[i] == arr2[j] && arr2[j]==arr3[k])
{
System.out.print(arr1[i]+" ");  
i++;
j++;
k++;
}
else if (arr1[i] < arr2[j])
                i++;

            else if (arr2[j] < arr3[k])
                j++;

            else
                k++;
}
}

public static void main(String[] args)
{
  FindCommonElement ob = new FindCommonElement();
          int ar1[] = {1, 5, 10, 20, 40, 80};
          int ar2[] = {6, 7, 20, 80, 100};
          int ar3[] = {3, 4, 15, 20, 30, 70, 80, 120};
          System.out.print("Common elements are :");
          ob.findcommonElement(ar1, ar2, ar3);
}
}

Output:  Common elements are :20 80

Time complexity of the above solution is O(n1 + n2 + n3). 
In worst case, the largest sized array may have all small elements and middle sized array has all middle elements.

Find k closest elements to a given value in java

Find k closest elements to a given value

Examples:

Input: K = 4, X = 35
       arr[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56}
 
Output: 30 39 42 45

Note that if the element is present in array, then it should not be in output, only the other closest elements are required.

In the following solutions, it is assumed that all elements of array are distinct.

A simple solution is to do linear search for k closest elements but Binary Search would be an
optimized Solution for it.

1) Start from the first element and search for the crossover point (The point before which elements are smaller than or equal to X and after which elements are greater). This step takes O(n) time.
2) Once we find the crossover point, we can compare elements on both sides of crossover point to print k closest elements. This step takes O(k) time.

The time complexity of the above solution is O(n).

An Optimized Solution is to find k elements in O(Logn + k) time. The idea is to use Binary Search to find the crossover point. Once we find index of crossover point, we can print k closest elements in O(k) time.

Sample Code Solution:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class KClosest
{

public int crossOver(int arr[],int low,int high,int x)
{
if (arr[high] <= x) // x is greater than all
           return high;
       if (arr[low] > x)  // x is smaller than all
           return low;
     
       int mid = (low + high)/2;
     
       if (arr[mid] <= x && arr[mid+1] > x)
           return mid;
     
       if(arr[mid] < x)
           return crossOver(arr, mid+1, high, x);
     
       return crossOver(arr, low, mid - 1, x);

}

public void printKclosest(int arr[], int x, int k, int n)
      {  
        int l = crossOver(arr, 0, n-1, x);
        int r = l+1;  
        int count = 0;            
        if (arr[l] == x)
        l--;

        while (l >= 0 && r < n && count < k)
        {
            if (x - arr[l] < arr[r] - x)
                System.out.print(arr[l--]+" ");
            else
                System.out.print(arr[r++]+" ");
            count++;
        }
        while (count < k && l >= 0)
        {
            System.out.print(arr[l--]+" ");
            count++;
        }

        while (count < k && r < n)
        {
            System.out.print(arr[r++]+" ");
            count++;
        }
    }

public static void main(String[] args)
{
   KClosest ob = new KClosest();
       int arr[] = {12, 16, 22, 30, 35, 39, 42,45, 48, 50, 53, 55, 56};
       int n = arr.length;
       int x = 35, k = 4;
       ob.printKclosest(arr, x, 4, n);
}
}

Output:

39 30 42 45

The time complexity of this method is O(Logn + k).

Sorting Algorithm - Merge Sort

Merge Sort

MergeSort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

MergeSort(arr[], l,  r)

If r > l
     1. Find the middle point to divide the array into two halves:
             middle m = (l+r)/2
     2. Call mergeSort for first half:  
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)


Example : The complete merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}.

  we can see that the array is recursively divided in two halves till the size becomes 1. Once the size becomes 1, the merge processes comes into action and starts merging arrays back till the complete array is merged.
 
  Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class MergeSortApp
{

   public void merge(int arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int L[] = new int [n1];
        int R[] = new int [n2];

        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i)
            L[i] = arr[l + i];
        for (int j=0; j<n2; ++j)
            R[j] = arr[m + 1+ j];


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
   public void sort(int arr[], int l, int r)
    {
        if (l < r)
        {
            // Find the middle point
            int m = (l+r)/2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr , m+1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    public void printArray(int arr[])
{
for(int i=0;i<arr.length;i++)
{
System.out.println(arr[i] + " ");
}
System.out.println(" ");
}

public static void main(String[] args)
{
int arr[] = {12, 11, 13, 5, 6, 7};
MergeSortApp ob = new MergeSortApp();
               System.out.println("Given Array");
               ob.printArray(arr);
               ob.sort(arr, 0, arr.length-1);
              System.out.println("\nSorted array");
             ob.printArray(arr);
}
}

Output:

Given Array
12
11
13
5
6
7
Sorted array
5
6
7
11
12
13

Time Complexity: Sorting arrays on different machines. Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation.

T(n) = 2T(n/2) + Theta(n)

The above recurrence can be solved either using Recurrence Tree method or Master method. It falls in case II of Master Method and solution of the recurrence is Theta(nLogn).
Time complexity of Merge Sort is Theta(nLogn) in all 3 cases (worst, average and best) as merge sort always divides the array in two halves and take linear time to merge two halves.

Auxiliary Space: O(n)
Algorithmic Paradigm: Divide and Conquer
Sorting In Place: No in a typical implementation
Stable: Yes





  

Sorting Algorithm - Insertion Sort

Insertion Sort

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

For Example:

Algorithm:

// Sort an arr[] of size n
insertionSort(arr, n);
Loop from i = 1 to n-1.
Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

Another Example: 

12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 5 (Size of input array)
i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6
i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6
i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13

Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class InsertionSortApp
{
public void printArray(int arr[])
{
for(int i=0;i<arr.length;i++)
{
System.out.println(arr[i] + " ");
}
System.out.println(" ");
}

public void insertionSort(int arr[])
{
       int n = arr.length;
     
       for (int i=1; i<n; ++i)
       {
           int key = arr[i];
           int j = i-1;

           while (j>=0 && arr[j] > key)
           {
               arr[j+1] = arr[j];
               j = j-1;
           }
           arr[j+1] = key;
       }
}

public static void main(String[] args)
{
       int arr[] = {12, 11, 13, 5, 6};
               InsertionSortApp ob = new InsertionSortApp();      
              ob.insertionSort(arr);  
              ob.printArray(arr);
}
}

Output:

5
6
11
12
13

Time Complexity: O(n*n)

Auxiliary Space: O(1)

Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.

Algorithmic Paradigm: Incremental Approach

Sorting In Place: Yes

Stable: Yes

Uses: Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.

Sorting Algorithm - Bubble Sort

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in some random order.

For Example:

First Pass:

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 )

Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Java implementations of Bubble Sort:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class BubbleSortApp
{
public void printArray(int arr[])
{
for(int i=0;i<arr.length;i++)
{
System.out.println(arr[i] + " ");
}
System.out.println(" ");
}

public  void bubbleSort(int arr[])
   {
       int n = arr.length;
       for (int i = 0; i < n-1; i++)
           for (int j = 0; j < n-i-1; j++)
               if (arr[j] > arr[j+1])
               {                  
                   int temp = arr[j];
                   arr[j] = arr[j+1];
                   arr[j+1] = temp;
               }
   }

public static void main(String[] args)
{
BubbleSortApp ob = new BubbleSortApp();
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        ob.bubbleSort(arr);
        System.out.println("Sorted array");
        ob.printArray(arr);
}

}

Output: 

Sorted array
11
12
22
25
34
64
90

Worst and Average Case Time Complexity: O(n*n).
Worst case occurs when array is reverse sorted.

Best Case Time Complexity: O(n).
Best case occurs when array is already sorted.

Auxiliary Space: O(1)
Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.

Sorting In Place: Yes

Stable: Yes

Due to its simplicity, bubble sort is often used to introduce the concept of a sorting algorithm.
In computer graphics it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n).

For example, it is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at a specific scan line (a line parallel to x axis) and with incrementing y their order changes (two elements are swapped) only at intersections of two lines