Trying to code Strassen's Matrix Multiplication Algorithm (JAVA)

Originally beneficial to reduce the running time 0(n³) of normal matrix multiplication. Strassen's Matrix Multiplication is really useful and produces a recurrence

T(n) = 7T(n/2) + 0(n²)

which is yet to be learnt to solve.

Right now I have managed to do this much. Will hopefully upload the complete code. Right now I have accomplished making the intermediate submatrices.

The Steps involved in Strassen's Matrix Multiplication are:

1. Divide the input matrices A and B and Output matrix C into n/2 x n/2 submatrices. This step takes     0(1) time (We'll not make new arrays but will do the index calculations to search for appropriate         elements).
2. Create 10 matrices S1,S1,....S10, each of which is n/2xn/2.

Since I have just reached until this step, I am going to share this much.
The matrices would be the following:

S1=B₁₂-B₂₂
S2=A₁₁+A₁₂
S3=A₂₁+A₂₂
S4=B₂₁-B₁₁
S5=A₁₁+A₂₂
S6=B₁₁+B₂₂
S7=A₁₂-A₂₂
S8=B₂₁+B₂₂
S9=A₁₁-A₂₁
S10=B₁₁+B₁₂

Here is the code:



package javaapplication1;
import java.util.*;
public class StrassensMatrixMultiply {

    public static void main(String[] args) {
        Scanner obj=new Scanner(System.in);
        System.out.println("Enter the order of Matrices you wanna multiply.<Note - Enter only a power of 2> : ");
        int n=obj.nextInt();
        int A[][]=new int[n][n];
        int B[][]=new int[n][n];
       
        System.out.println("Enter the elements of the 1st Matrix: ");
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                A[i][j]=obj.nextInt();
            }
        }
       
        System.out.println("Enter the elements of the 2nd Matrix: ");
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                B[i][j]=obj.nextInt();
            }
        }
       
        int s1[][]=new int[n/2][n/2];
        int s2[][]=new int[n/2][n/2];
        int s3[][]=new int[n/2][n/2];
        int s4[][]=new int[n/2][n/2];
        int s5[][]=new int[n/2][n/2];
        int s6[][]=new int[n/2][n/2];
        int s7[][]=new int[n/2][n/2];
        int s8[][]=new int[n/2][n/2];
        int s9[][]=new int[n/2][n/2];
        int s10[][]=new int[n/2][n/2];
       
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n/2;j++){
                s1[i][j]=B[i][j+(n/2)]-B[i+(n/2)][j+(n/2)];
            }
        }
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n/2;j++){
                s2[i][j]=A[i][j]+A[i][j+(n/2)];
            }
        }
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n/2;j++){
                s3[i][j]=A[i+(n/2)][j]+A[i+(n/2)][j+(n/2)];
            }
        }
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n/2;j++){
                s4[i][j]=B[i+(n/2)][j]-B[i][j];
            }
        }
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n/2;j++){
                s5[i][j]=A[i][j]+A[i+(n/2)][j+(n/2)];
            }
        }
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n/2;j++){
                s6[i][j]=B[i][j]+B[i+(n/2)][j+(n/2)];
            }
        }
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n/2;j++){
                s7[i][j]=A[i][j+(n/2)]-A[i+(n/2)][j+(n/2)];
            }
        }
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n/2;j++){
                s8[i][j]=B[i+(n/2)][j]+B[i+(n/2)][j+(n/2)];
            }
        }
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n/2;j++){
                s9[i][j]=A[i][j]-A[i+(n/2)][j];
            }
        }
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n/2;j++){
                s10[i][j]=B[i][j]+B[i][j+(n/2)];
            }
        }
       
       
       
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n/2;j++){
                int sum=0;                                       //Here I am just trying to perform the multiplication,
                for(int k=0;k<n/2;k++){                 //which is just the next step and will be upfdating soon.
                    sum=sum+s1[i][k]*A[k][j];
                }
                s1[i][j]=sum;
            }
        }
       
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n/2;j++){
                System.out.println(s1[i][j]);
            }
        }
       
       
       
    }
   
}

Bubble Sort (Java Program)

Bubble Sort: In this algorithm, we compare two consequent elements in the list from the beginning till the end. For example - A[1]  and A[2] are compared and if A[1]>A[2], we swap them. we do this for n-1 passes, where n is number of elements. At the end of 1st pass we set the last element that is the largest of all. In the 2nd pass we set the second last element and so on. Also with every pass the number of elements to be compared becomes one less than before.

Program:

import java.util.*;
public class BubbleSort {

    public static void main(String[] args) {
        Scanner obj=new Scanner(System.in);
        int n=obj.nextInt();
        int z=n;
        double arr[]=new double[n];
        for(int i=0;i<n;i++){
            arr[i]=obj.nextDouble();
        }
        double temp;
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-1;j++){
                if(arr[j]>arr[j+1]){
                 temp=arr[j];
                 arr[j]=arr[j+1];
                 arr[j+1]=temp;
                }
            }
            n--;
        }
        for(int i=0;i<z;i++)
            System.out.println(arr[i]);
    }
 
}

Insertion Sort (Java Program)

Insertion Sort: This sorting algorithm is same as sorting a deck of cards. We pickup a card in one hand and then compare each subsequent card with it and insert the card into the sorted deck. That is we pick one card at a time and insert it into sorted deck at the right place.

Program:

import java.util.Scanner;
public class InsertionSort {
 
    public static void main(String[] args) {
        System.out.println("Enter the number of elements : ");
        Scanner obj=new Scanner(System.in);
        int n=obj.nextInt();
        double arr[]=new double[n];
        System.out.println("Enter "+n+" elements : ");
        for(int i=0;i<n;i++){
            arr[i]=obj.nextDouble();
            }
     
        int i;double key;                        
        for(int j=1;j<n;j++){
            key=arr[j];
            i=j-1;
            while(i>=0&&arr[i]>key){
         
                arr[i+1]=arr[i];
                arr[i]=key;
             
                i--;
         
            }
         
        }

        for(i=0;i<n;i++){
            System.out.println(arr[i]);
        }
     

    }
}