Selection Sort

Insertion Sort: Sorting as the number comes from user.

Insertion sort is the adding of numbers coming from the user into a previously sorted array. The incoming digit is inserted to its relevant place by searching one place at a time in a sorted array. Following is the code to do just that. Hope it will be helpful. 

Click on the code below to see the image...

Quantitative Aptitude question - 25 non-parallel lines in a plane, How many intersections?

Ques - There are 25 lines in a plane such that no two of them are parallel to each other, so how many intersections?

Ans - Now since no line is parallel to any other 24 lines, this means that every line is cut by the remaining 24 lines.

Hence, All 25 lines will be cut by the others, Hence  25x24=600.

But sometimes the question a little bit more twisted. Here it is.

Ques - There are 25 lines in a plane such that no two of them are parallel to each other and no 3 are concurrent to each other, so how many intersections?

Ans - Now since we know that 3 or more lines are said to be concurrent only if they intersect at one point.

Since according to the question no more than 3 lines can intersect at one point. Hence we have the following

Now from the above picture it is quite clear that one line would be cut down by 2 other lines at one point. Hence giving us the condition that only 3 intersect at single point.

Now we know from the above question that there were 24 different points of intersection on  the 25th line but in this case we will have only 12.

Hence 12 points on each of 25 lines.

Therefore answer =25x12 =300.

Maximum SubArray Problem Part-1

Maximum Sub-Array:

A simple problem of figuring the maximum profit in investment over a given period can be calculated using maximum Maximum SubArray Problem. 

In Maximum subarray problem, we require to find out the subarray of a given array having the maximum sum.

For example if the problem is 

13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7

In the above array, we need to find the contiguous sequence that yields the maximum sum.

For this we need to find the sequence in the array to the right of middle element, the array to the left of the middle element and the array that crosses the middle element. In this 1st Part, we will present the code of finding the maximum subarray crossing the middle element.

Maximum Sub-Array Crossing Mid:

We find maximum subarray crossing the middle element by repetitive summing up the elements, First from mid towards the low, Second from the mid+1 towards the high. We output the sum of maximum subarray.

Maximum-SubArray Crossing Middle Element JAVA Program:

import java.util.Scanner;

public class FindMaxCrossingSubArray {

    public static void main(String[] args) {

        Scanner obj=new Scanner(System.in);

        int n=obj.nextInt();

        int arr[]=new int[n];

        for(int i=0;i<n;i++){

            arr[i]=obj.nextInt();

        }

        int low=0;

        int high=n-1;

        int mid;

        

            mid=low+high/2;

        

        Max_Sub_Arr(arr, low, mid, high);

    }

    static void Max_Sub_Arr(int arr[],int low, int mid, int high){

        int left_sum=arr[mid];

        int sum;

        int max_left;

        sum=0;

        for(int i=mid;i>=low;i--){

            sum=sum+arr[i];

            if(sum>left_sum){

                left_sum=sum;

                max_left=i;

            }  

        }

        int right_sum=arr[mid+1];

        int max_right;

        sum=0;

        for(int j=mid+1;j<=high;j++){

            sum=sum+arr[j];

            if(sum>right_sum){

                right_sum=sum;

                max_right=j;

            }

        }

        System.out.println(left_sum+right_sum);

    }

    

}

MERGE-SORT Algorithm (JAVA Program)

Today I am going to share the code for the Divide and Conquer Algorithm, Merge-Sort.
The Algorithm uses the Recursive call to itself and in the end a call to the merge subroutine that combines the two sorted lists.

For example if we have a list of 9 elements:
12, 34, 56, 97, 10, 5, 15, 45, 100

We pass the list to mergesort(int arr[], int p, int r) procedure/function/method where p is the start index (0 according to our example) and r is the end index (n-1, according to our example). This method in turn finds out the middle index as q=(p+r)/2, thus partitioning the original list into two halves for which the mergesort procedure is called recursively as mergesort(int arr[], int p, int q) and mergesort(int arr[], int q+1, int r). Finally we merge the elements in the absolute inner loop when only 2 elements are left to be  merged and then we keep on reaching the outer loop with the merge procedure in each step.
This can be expressed using the following diagram:

The Java Program for Merge sort is provided below:

Merge-Sort (JAVA Program)

package javaapplication1;

import java.util.Scanner;

public class MergeSort1 {

    public static void main(String[] args) {

        Scanner obj=new Scanner(System.in);

        System.out.println("Enter number of elements = ");

        int n=obj.nextInt();

        System.out.println("Enter "+n+" elements = ");

        int arr[]=new int[n];

        for(int i=0;i<n;i++){

            arr[i]=obj.nextInt();

        }

        int p=0;int r=n-1;

        mergesort(arr,p,r);

        for(int i=0;i<n;i++)

        System.out.println(arr[i]);

    }

    

    static void mergesort(int a[],int p, int r){

        if(p<r){

            int q=(p+r)/2;

            mergesort(a, p, q);

            mergesort(a, q+1, r);

            merge(a,p,q,r);

        }

       

    }

    

    static void merge(int a[],int p, int q, int r){

        int n1=q-p+1;

        int n2=r-q;

        int arr1[]=new int[n1];

        int arr2[]=new int[n2];

        for(int i=0;i<n1;i++){

            arr1[i]=a[p+i];

        }

        for(int j=0;j<n2;j++){

            arr2[j]=a[q+j+1];

        }

        

        int i=0;

        int j=0;

        for(int k=p;k<r+1;k++){

            if(i==n1){

                a[k]=arr2[j];

                j++;

                continue;

            }

            if(j==n2){

                a[k]=arr1[i];

                i++;

                continue;

            }

            if(arr1[i]<=arr2[j]&&i<n1){

                a[k]=arr1[i];

                i++;

            }

            else if(arr1[i]>arr2[j]&&j<n2){

                a[k]=arr2[j];

                j++;

            }

        }

    }

    

    

}

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]);
    }
 
}