Thursday, January 30, 2014

Matrix Multiplication in Java


package com.learning.ds.matrices;
import com.learning.ds.arrays.ArrayUtil;

/**
 * Created by Rajdeep on 28/1/14.
 */
public class MatrixMultiplicationDemo {
    public static void main(String[] args){
        //the temp1 and temp2 array values can be changed to test this program
        int[][] temp1 = {{2,0}};
        int[][] temp2 = {{1,1,1}, {2,2,2}};

        System.out.println("Matrix 1: ");
        ArrayUtil.print2DIntArray(temp1);
        System.out.println("Matrix 2: ");
        ArrayUtil.print2DIntArray(temp2);

        if( !( isFilledMatrix(temp1) && isFilledMatrix(temp2) ) ){
            System.out.println("One of the matrices is not filled completely and can't be used for multiplication.");
        }
        else{
            //check dimension
            if(!areMatricesMultipliable(temp1, temp2)){
                System.out.println("The number of columns in first matrix is unequal to number of rows in second matrix. The must be equal for dot product.");
            }
            else{
                System.out.println("can be multiplied");
                int[][] tempNew = multiplyMatrices(temp1, temp2);
                System.out.println("new matrix is: ");
                ArrayUtil.print2DIntArray(tempNew);
            }
        }
    }

    private static int[][] multiplyMatrices(int[][] temp1, int[][] temp2) {
        //
        int rowCount1 = temp1.length;
        int colCount1 = temp1[0].length;
        int colCount2 = temp2[0].length;

        int[][] tempNew = new int[rowCount1][colCount2];

        for(int i=0; i < rowCount1; i++){
            int k=0;
            while(k < colCount2){
                int tempVal = 0;
                for (int j=0; j < colCount1; j++){
                    tempVal = tempVal + ( temp1[i][j] * temp2[j][k] );
                }
                tempNew[i][k] = tempVal;
                k++;
            }

        }

        return tempNew;
    }

    //matrix multiplication rule is
    //no of columns of left matrix == no of rows in right matrix
    // (m x n) . (n x p) = (m x p)
    private static boolean areMatricesMultipliable(int[][] mat1, int[][] mat2){
        return (mat1[0].length == mat2.length);
    }

    //check the matrix has all elements filled or not
    //In other words, checking whether number of columns in each row is same
    private static boolean isFilledMatrix(int[][] mat){
        boolean retVal = false;
        int rows = mat.length;
        
        if(rows == 1){
            retVal = true;
        }
        else {
            for(int i=0; i < (rows-1); i++){
                if(mat[i].length != mat[i+1].length){
                    retVal = false;
                    break;
                }
                else
                    retVal = true;
            }
        }

        return retVal;
    }
}


The
ArrayUtil.print2DArray(int[][] args)
prints the array on screen through normal 'for' loops.
One sample output:
Matrix 1:
2 0
Matrix 2:
1 1 1
2 2 2
can be multiplied
new matrix is:
2 2 2
Another sample output by changing the temp1 and temp2 arrays in main() method:
Matrix 1::
2 0 3:
Matrix 2::
1 1 1:
2 2 2:
One of the matrices is not filled completely and can't be used for multiplication.

Monday, January 27, 2014

Matrix Operation in Java: Addition of two 2x2 matrices demonstrated


For addition or subtraction, the dimensions of the matrices must be same. This is just a demonstration code and can be rewritten in a far more optimized manner.
package com.learning.ds.matrices;

/**
 * Created by Rajdeep on 27/1/14.
 */
public class MatrixAdditionDemo {
    public static void main(String[] args){
        int[][] arr1 = {{1,2,3},{4,2,6}};
        int[][] arr2 = {{10,20,30},{40,50,60}};

        System.out.println("Matrix A:");
        for(int i=0; i < arr1.length; i++){
            for(int j=0; j < arr1[i].length; j++){
                System.out.print(arr1[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println("Matrix B:");
        for(int i=0; i < arr2.length; i++){
            for(int j=0; j < arr2[i].length; j++){
                System.out.print(arr2[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println("Addition of A and B:");
        int[][] tempArr = addMatrices(arr1,arr2);
        if(tempArr!=null){
            for(int i=0; i < tempArr.length; i++){
                for(int j=0; j < tempArr[i].length; j++){
                    System.out.print(tempArr[i][j] + " ");
                }
                System.out.println();
            }
        }

    }

    //add the matrices
    private static int[][] addMatrices(int[][] m1, int[][] m2){
        //check size
        if(!ofSameSize(m1, m2)){
            System.out.println("[Error] The matrices' dimension in operation do not match!");
            return null;
        }
        int len1 = m1.length;
        int[][] tempArr = new int[2][3];
        for(int i=0; i < tempArr.length; i++){
            for(int j=0; j < tempArr[i].length; j++){
                tempArr[i][j] = m1[i][j] + m2[i][j];
            }
        }
        return tempArr;
    }

    //for adding, the size must be same
    private static boolean ofSameSize(int[][] m1, int[][] m2) {
        int len1 = m1.length;
        int len2 = m2.length;
        boolean check = true;
        if(len1==len2 & len1!=0){
            //System.out.println("length is: " + len1 + " and " + len2);
            for(int i=0; i < len1; i++){
                if(!(m1[i].length == m2[i].length)){
                    check = false;
                }
            }
        }
        else
            check = false;

        return check;
    }
}

Sample output 1:
Matrix A:
1 2 3
4 2 6
Matrix B:
10 20 30
Addition of A and B:
[Error] The matrices' dimension in operation do not match!

Sample output 2:
Matrix A:
1 2 3
4 2 0 
 
Matrix B:
10 20 30
11 5 3 
 
Addition of A and B:
11 22 33
15 7 3 

Quick Sort Demo


This is a divide and conquer approach. Take a pivot as the last element of array, and place all numbers lesser than this to the left. This is done using partitioning as seen in the code.
Complexity:
Best - O(n logn); Average - O(n logn); Worst - O(n^2)