Algorithm and Program for Strassen's matrix multiplication

Algorithm

If the sizes of A and B are less than the threshold

Compute C = AB using the traditional matrix multiplication algorithm.
Else use Strassen's algorithm
Split matrices A and B
For each of

Mi i = 1 to 7

Create a new thread to compute

Mi = A'i B'i

If the sizes of the matrices are less than the threshold
Compute C using the traditional matrix multiplication algorithm.
Else use Strassen's algorithm
Split matrices A'

i and B'i

For each of M

ij j = 1 to 7

If i=7 and j=7 go to step 1 with A = A'77

and

B = B'77

Get a thread from the thread pool to compute

M= A'ij B'ij

Execute the recursive version of Strassen's algorithm in this thread
Wait for the Mij

threads to complete execution

Compute MiWait for the Mi

threads to complete execution

Compute C

Program

#include<iostream.h>

#include<conio.h>

void main()

{

int a[2][2],b[2][2],c[2][2],i,j;

int p1,p2,p3,p4,p5,p6,p7;

clrscr();

cout<<"enter the first matrix";

for(i=1;i<=2;i++)

for(j=1;j<=2;j++)

cin>>a[i][j];

cout<<"enter the second matrix";

for(i=1;i<=2;i++)

for(j=1;j<=2;j++)

cin>>b[i][j];

p1=a[1][1]*(b[1][2]-b[2][2]);

p2=(a[1][1]+a[1][2])*b[2][2];

p3=(a[2][1]+a[2][2])*b[1][1];

p4=a[2][2]*(b[2][1]-b[1][1]);

p5=(a[1][1]+a[2][2])*(b[1][1]+b[2][2]) ;

p6=(a[1][2]-a[2][2])*(b[2][1]+b[2][2]) ;

p7=(a[1][1]-a[2][1])*(b[1][1]+b[1][2]) ;

c[1][1]=p5+p4-p2+p6;

c[1][2]=p1+p2;

c[2][1]=p3+p4;

c[2][2]=p5+p1-p3-p7;

for(i=1;i<=2;i++)

{

for(j=1;j<=2;j++)

{

cout<<c[i][j]<<" ";

}

cout<<"\n" ;

}

getch();

}

Algorithm and Program for Depth First Search(DFS)

Algorithm
1  procedure DFS(G,v):
2      label v as explored
3      for all edges e in G.incidentEdges(v) do
4          if edge e is unexplored then
5              w ← G.opposite(v,e)
6              if vertex w is unexplored then
7                  label e as a discovery edge
8                  recursively call DFS(G,w)
9          else
10             label e as a back edge
Program
#include<stdio.h>
#include<conio.h>
#define MAX 5
int dfs(int adj[][MAX],int visited[],int start)
{
    int stack[MAX];
    int top=-1,i;
   
    printf("%c-",start+65);
    visited[start]=1;
    stack[++top]=start;
    while(top!=-1)
    {
    start=stack[top];
    for(i=0;i<MAX;i++)
    {  if(adj[start][i]&&visited[i]==0)
    {stack[++top]=i;
      printf("%c-",i+65);
        visited[i]=1;
        break;                                                            
        }}
      if(i==MAX)
      top--;
    }
    return 0;
}
int main()
{
    int adj[MAX][MAX]={{0,0,1,1,0},{0,0,0,0,0},{0,1,0,1,1},{0,0,0,0,1},{0,0,0,1,0}};
    int visited[MAX]={0};
     printf("DFS Traversal : ");
    dfs(adj,visited,0);
 printf("\n");
    getch();
    return 0;
}

Algorithm and Program for Merge Short

Algorithm

function merge(left,right)

    var list result

    while length(left) > 0 or length(right) > 0

        if length(left) > 0 and length(right) > 0

            if first(left) ≤ first(right)

                append first(left) to result

                left = rest(left)

            else

                append first(right) to result

                right = rest(right)

        else if length(left) > 0

            append first(left) to result

            left = rest(left)

        else if length(right) > 0

            append first(right) to result

            right = rest(right)

    end while

    return result

Program

#include <stdio.h>
#include<conio.h>
int a[50];
void merge(int,int,int);
void merge_sort(int low,int high)
{ int mid;
  if(low<high)
 {mid=(low+high)/2;
  merge_sort(low,mid);
  merge_sort(mid+1,high);
  merge(low,mid,high);
 }
}

void merge(int low,int mid,int high)
{
 int h,i,j,b[50],k;
 h=low;
 i=low;
 j=mid+1;

 while((h<=mid)&&(j<=high))
 {if(a[h]<=a[j])
  {b[i]=a[h];
   h++;
  }
  else
  {b[i]=a[j];
   j++;
  }
  i++;
 }
 if(h>mid)
 {
  for(k=j;k<=high;k++)
  {b[i]=a[k];
   i++;
  }
 }
 else
 {  for(k=h;k<=mid;k++)
       {b[i]=a[k];
        i++;
       }
 }
 for(k=low;k<=high;k++) a[k]=b[k];
}
int main()
{int num,i;
 printf("Please Enter THE NUMBER OF ELEMENTS you want to sort :\n");
 scanf("%d",&num);
 printf("\n");
 printf("Now, Please Enter the ( %d ) numbers :\n",num);
 for(i=1;i<=num;i++)
 {  scanf("%d",&a[i]); }
 merge_sort(1,num);
 printf("\n");
 printf("So, the sorted list (using MERGE SORT) will be :\n");
 printf("\n\n");
 for(i=1;i<=num;i++)
 printf("%d  ",a[i]);
 printf("\n\n\n\n");
getch();
return 0;
}

Algorithm and Program for Quick Short

Algorithm

// left is the index of the leftmost element of the array
  // right is the index of the rightmost element of the array (inclusive)
  // number of elements in subarray: right-left+1
  function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right]  // Move pivot to end
     storeIndex := left
     for i from left to right - 1 // left ≤ i < right
         if array[i] < pivotValue
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right]  // Move pivot to its final place
     return storeIndex

Program
#include<conio.h>
#include<stdio.h>
void quickshort(int ,int,int);
int partition(int arr[], int left, int right)
{  int i = left, j = right;
   int tmp;
   int pivot = arr[i];
   while (i <= j)
         { while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                   j--;
            if (i <= j)
               { tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
               }
         };
   return i;
}
void quickSort(int arr[], int left, int right)
{  int index = partition(arr, left, right);
      if (left < index - 1)
      quickSort(arr, left, index - 1);
      if (index < right)
            quickSort(arr, index, right);
}
int main()
{printf("enter the no of elements in the list\n");
int n,i;
scanf("%d",&n);
int arr[n];
printf("now enter the %d elements of the list ",n);
for(i=0;i<n;i++)
    scanf("%d",&arr[i]);
quickSort(arr,0,7);
printf("\n The shorted list is ");
for(i=0;i<n;i++)
printf("  %d  ",arr[i]);
getch();
    return 0;}

Algorithm and Program for Binary Search

implementation of the algorithm

limitations :
entered list must be pre shorted;
there must be only one element in the list which is to be searched;

#include<stdio.h>
#include<conio.h>
int mid;
int BinarySearch(int A[], int key, int low,int high)
{
       if (high < low)
        return -1;
      mid =low + (high - low)/2;
       if (A[mid] > key)
          return BinarySearch(A,key, low, mid-1);
       else if (A[mid] < key)
          return BinarySearch(A, key, mid+1, high);
       else
           return mid ;
   };
  
   int main()
   {
     
      int j,low=0,high=9,key,k=0;
      int A[9];
       printf("enter the 12 elements of array");
      for(j=0;j<9;j++)
      scanf("%d",&A[j]);
       printf("\n enter the element to be searched for");
      scanf("%d",&key);
      j=BinarySearch(A,key,low,high);
      if (j>=0)
      printf("\element %d is found at position %d",key,j+1); 
      else
      printf("\n element not found");
      getch();
      return 0;
   }

BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = low + (high - low) / 2
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
   }

Program to saving data to a database

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Data.SqlClient;
namespace WindowsFormsApplication1
{
  public partial class Form1 : Form
{
  public Form1()
{
InitializeComponent();
}private void button1_Click(object sender, EventArgs e)
{
SqlConnection cn =new SqlConnection("PASTE CONNECTION STRING HERE");

cn.Open();
SqlCommand cmd = new SqlCommand("insert into emp values ('"+textBox1.Text+"', '"+textBox2.Text+"', "+textBox3.Text+")",cn); 

cmd.ExecuteNonQuery();
MessageBox.Show(" your entries are saved into the database");
}
}

connection string is found in database properties

example of a connection string


("Data Source=.\\SQLEXPRESS;AttachDbFilename=C:\\Users\\manish\\Documents\\niist.mdf;Integrated Security=True;Connect Timeout=30;User Instance=True")

Program to add two numbers in c#

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;using System.Drawing;
using System.Linq;using System.Text;
using System.Windows.Forms;
namespace WindowsFormsApplication1
{public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}

private void button1_Click(object sender, EventArgs e)
{int a,b,c;
a=Convert.ToInt32(textBox1.Text);
b=Convert.ToInt32(textBox2.Text);
c=a+b;
textBox3.Text = (c.ToString());

}
}
}

Program to retrieve data from a table

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Data.SqlClient;

namespace WindowsFormsApplication1
{ 
   public partial class Form1 : Form
{
   public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
 SqlCommand cmd = new SqlCommand(" select * from EMP where ENAME='" + textBox1.Text + "'",cn);
 SqlDataReader dr = cmd.ExecuteReader();
cn.Open();
dr.Read();
if (dr.HasRows)
{
label2.Text = dr["DESIG"].ToString();
label3.Text = dr["SAL"].ToString();
}
if (!dr.HasRows)
{
MessageBox.Show("ERROR IN RETRIEVING","Error Message",  MessageBoxButtons.OKCancel ,  MessageBoxIcon.Warning,  MessageBoxDefaultButton.Button1);
}
}
}
}

connection string can be found in database properties

example of a connection string

("Data Source=.\\SQLEXPRESS;AttachDbFilename= C:\\Users\\manish\\Documents\\niist.mdf; Integrated Security=True;Connect Timeout=30;User Instance=True")SqlConnection cn = new SqlConnection("PASTE CONNECTION STRING HERE");