Notes

Program 1: Program to implement Insertion Sort
Source Code
#include <stdio.h>
#include <stdlib.h>
void insertionSort(int a[], int n)
{
int i,j,key;
for(j=1; j<n; j++)
{
key= a[j];
i=j-1;
while(i>=0 && key<a[i])
{
a[i+1]=a[i];
i--;
}
a[i+1]=key;
}
}
int main() {
int i, a[100],n;
printf("-------Insertion Sort-------");
printf("n Enter the size of the array: ");
scanf("%d", &n);
printf(" Enter the elements of the array: ");
for(i=0; i<n; i++)
scanf("%d", &a[i]);
printf("n Before Sorting: ");
for(i=0; i<n;i++)
printf("%d ",a[i]);
insertionSort(a,n);
printf("n After Sorting: ");
for(i=0; i<n; i++)
printf("%d ",a[i]);
return 0;
}
-------------------------------------------
Program 2: Program to implement Selection Sort
Source Code
#include <stdio.h>
void SelectSort(int a[],int n);
int main()
{
int a[100], n,i;
printf("--------------Selection Sort--------------n");
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d Numbers: ", n);
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
SelectSort(a,n);
return 0;
}
void SelectSort(int a[], int n)
{
int i, j, position, swap;
for(i = 0; i < (n - 1); i++)
{
position=i;
for(j = i + 1; j < n; j++)
{
if(a[position]>a[j])
position=j;
}
if(position != i)
{
swap=a[i];
a[i]=a[position];
a[position]=swap;
}
}
printf("nSorted Array: ");
for(i = 0; i < n; i++)
printf("%d ", a[i]);
}
--------------------------------------------

Program 3: Program to implement Bubble Sort algorithm
Source Code
#include <stdio.h>
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf(" %d ", arr[i]);
}
// Driver program to test above functions
int main(){
int arr[100],n,i;
printf("--------------Bubble Sort--------------n");
printf(" Enter the size of array: ");
scanf("%d",&n);
printf(" Enter the elements of array: ");
for(i=0;i<n;i++){
scanf("%d",&arr[i]);}
printf("n Before Sorting: ");
for(i=0; i<n;i++)
printf("%d ",arr[i]);
bubbleSort(arr, n);
printf("n After Sorting: ");
printArray(arr, n);
return 0;
}
-----------------------------------------------
Program 1: Program to implement Euclidean Algorithm.
Source Code
#include <stdio.h>
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
void main()
{
int a, b;
printf("--------------Euclidean Algorithm---------------");
printf("n Enter-two integer numbers: ");
scanf ("%d%d", &a, &b);
printf("n GCD(%d, %d) = %dn", a, b, gcd(a, b));
}

------------------------------------------------------------
Program 1: Program to implement Merge Sort
Source Code
#include <stdio.h>
#include <stdlib.h>
void Merge(int A[], int low, int mid, int high)
{
int i, j, k;
int n1 = mid - low + 1;
int n2 = high - mid;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = A[low + i];
for (j = 0; j < n2; j++)
R[j] = A[mid + 1 + j];
i = 0; j = 0; k = low;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
A[k] = L[i];
i++;
}
else
{
A[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
A[k] = L[i];
i++;
k++;
}
while (j < n2)
{
A[k] = R[j];
j++;
k++;
}
}
void MergeSort(int *A[],int low, int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
MergeSort(A, low, mid);
MergeSort(A, mid+1, high);
Merge(A, low, mid, high);
}
}
void printArray(int A[], int n)
{
int i;
for (i=0; i < n; i++)
printf(" %d ", A[i]);
printf("n");
}
void main()
{
int A[100], n, i;
printf("------------------Merge Sort------------------n");
printf(" Enter the size of array: ");
scanf("%d",&n);
printf(" Enter the elements of array: ");
for(i=0; i<n; i++)
{
scanf("%d",&A[i]);
}
MergeSort(A,0,n-1);
printf(" Sorted Array: ");
printArray(A, n);
}
----------------------------------------------------------------------------------
Program 2: Program to implement Quick Sort
Source Code
#include <stdio.h>
void swap(int *x, int *y)
{
int Temp;
Temp = *x;
*x = *y;
*y = Temp;
}
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high)
{
if (low < high) {
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
printf(" %d ", arr[i]);
printf("n");
}
// Driver Code
int main()
{
int arr[50],n,i;
printf("----------------Quick Sort---------------");
printf("n Enter the size of the array: ");
scanf("%d", &n);
printf(" Enter the elements of the array: ");
for(i=0; i<n; i++)
scanf("%d", &arr[i]);
quickSort(arr, 0, n - 1);
printf("n Sorted Array: ");
printArray(arr, n);
return 0;
}
------------------------------------------------------------------
Program 1: Program to implement Heap Sort
Source Code
#include <stdio.h>
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int N, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < N && arr[left] > arr[largest])
largest = left;
if (right < N && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, N, largest);
}
}
// Main function to do heap sort
void heapSort(int arr[], int N)
{
// Build max heap
for (int i = N / 2 - 1; i >= 0; i--)
heapify(arr, N, i);
// Heap sort
for (int i = N - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
// Heapify root element to get highest element at
// root again
heapify(arr, i, 0);
}
}
// A utility function to print array of size n
void printArray(int arr[], int N)
{
for (int i = 0; i < N; i++)
printf("%d ", arr[i]);
printf("n");
}
// Driver's code
int main()
{
int arr[50], N, i;
printf("-----------------Heap Sort-----------------");
printf("n Enter the size of the array: ");
scanf("%d", &N);
printf(" Enter the elements of the array: ");
for(i=0; i<N; i++)
scanf("%d", &arr[i]);
// Function call
heapSort(arr, N);
printf(" Sorted array is: ");
printArray(arr, N);}
-------------------------------------------------------------------------
Program: To implement 0-1 Knapsack
Source Code
#include<stdio.h>
int max(int a, int b) {
if(a>b){
return a;
} else {
return b;
}
}
int knapsack(int W, int wt[], int val[], int n) {
int i, w;
int knap[n+1][W+1];
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i==0 || w==0)
knap[i][w] = 0;
else if (wt[i-1] <= w)
knap[i][w] = max(val[i-1] + knap[i-1][w-wt[i-1]], knap[i-1][w]);
else
knap[i][w] = knap[i-1][w];
}
}
return knap[n][W];
}
int main() {
int val[] = {10, 20, 30};
int wt[] = {23, 26, 30};
int W = 50;
int n = sizeof(val)/sizeof(val[0]);
printf("The solution is : %d", knapsack(W, wt, val, n));
return 0;
}
-------------------------------------------------------------------------------
Program : To implement Matrix Chain Multiplication
Source Code
#include <stdio.h>
#include <limits.h>
int MatrixChainOrder(int p[], int n)
{
int m[n][n];
int i, j, k, L, q;
for (i = 1; i < n; i++)
m[i][i] = 0;
for (L = 2; L < n; L++)
{
for (i = 1; i < n - L + 1; i++)
{
j = i + L - 1;
m[i][j] = INT_MAX;
for (k = i; k <= j - 1; k++)
{
q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n - 1];
}
int main()
{
int arr[] = {3, 4,5,6,7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Minimum number of multiplications is %d ", MatrixChainOrder(arr, n));
return 0;}
-------------------------------------------------------------------------------
Program: To implement LCS
Source Code
#include<stdio.h>
#include<string.h>
int i,j,m,n,c[20][20];
char x[20],y[20],b[20][20];
void print(int i,int j)
{
if(i==0 || j==0)
return;
if(b[i][j]=='c')
{
print(i-1,j-1);
printf("%c",x[i-1]);
}
else if(b[i][j]=='u')
print(i-1,j);
else
print(i,j-1);
}
void lcs()
{
m=strlen(x);
n=strlen(y);
for(i=0;i<=m;i++)
c[i][0]=0;
for(i=0;i<=n;i++)
c[0][i]=0;
//c, u and l denotes cross, upward and downward directions respectively
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(x[i-1]==y[j-1])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]='c';
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]='u';
}
else
{
c[i][j]=c[i][j-1];
b[i][j]='l';
}
}
}
int main()
{
printf("Enter 1st sequence:");
scanf("%s",x);
printf("Enter 2nd sequence:");
scanf("%s",y);
printf("nThe Longest Common Subsequence is ");
lcs();
print(m,n);
return 0;
}


---------------------------------------------------------------------
Program: To implement Heap Sort
Source Code
// Floyd-Warshall Algorithm in C
#include <stdio.h>
// defining the number of vertices
#define nV 4
#define INF 999
void printMatrix(int matrix[][nV]);
// Implementing floyd warshall algorithm
void floydWarshall(int graph[][nV]) {
int matrix[nV][nV], i, j, k;
for (i = 0; i < nV; i++)
for (j = 0; j < nV; j++)
matrix[i][j] = graph[i][j];
// Adding vertices individually
for (k = 0; k < nV; k++) {
for (i = 0; i < nV; i++) {
for (j = 0; j < nV; j++) {
if (matrix[i][k] + matrix[k][j] < matrix[i][j])
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
}
printMatrix(matrix);
}
void printMatrix(int matrix[][nV]) {
for (int i = 0; i < nV; i++) {
for (int j = 0; j < nV; j++) {
if (matrix[i][j] == INF)
printf("%4s", "INF");
else
printf("%4d", matrix[i][j]);
}
printf("n");
}
}
int main() {
int graph[nV][nV] = {{0, 3, 8, INF},
{INF, 0, INF, 1},
{INF, 4, 0, INF},
{2, INF, -5, 0}};
floydWarshall(graph);
}