Activity Selection

#include<stdio.h>

int main(){

int start[] = {1 , 5 , 3};

int finish[] = {2, 15, 6};

int activities = 3, temp = 0;

int i,j;

for (i = 0; i <= 2; i++) {

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

if (finish[i]> finish[j])

temp = finish[j];

finish[j] = finish[i];

finish[i] = temp;

temp = start[j];

start[j] = start[i];

start[i] = temp;

i=0;

int k = 0;

printf("%d\t", k);

for (i = 0; i < 3; i++)

if (start[i] >= finish[k])

printf("%d\t", i);

k=i;

return 0;

Binary Search

#include<stdio.h>

#include<stdlib.h>

int searc(int arr[], int size, int num){

int low = 0;

int high = size-1;

int k=0;

int mid = low + (high - low)/2;

while(low<=high){

if(num > arr[mid]){

low = mid+1;

if(num < arr[mid]){

high = mid-1;

if(num == arr[mid]){

k++;
 break;

mid = (low+high)/2;

return mid;

int rbs(int arr[], int low, int high, int num){

if(low > high){

return -1;

int mid = low + (high - low) / 2;

if(arr[mid] == num){

return mid;

if(arr[mid] < num){

return rbs(arr, mid + 1, high, num);

return rbs(arr, low, mid - 1, num);

void main(){

int arr[10];

int num;

printf("Enter array elements");

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

scanf("%d", &arr[i]);

printf("Enter a number to search");

scanf("%d", &num);

int k = searc(arr, 10, num);

if(k){

printf("Number was found at %d th position\n", k);

else {

printf("Number was not found\n");

int r = rbs(arr, 0, 9, num);

if(r){

printf("Number was found at %d th position", r);

else {

printf("Number was not found");

Fractional knapsack

#include <stdio.h>

// Quicksort for parallel arrays

void quicksort(float ratio[], float weight[], float profit[], int low, int high) {

if (low < high) {

float temp;
 int i = low, j = high;

float pivot = ratio[(low + high) / 2];

while (i <= j) {

while (ratio[i] > pivot) i++;

while (ratio[j] < pivot) j--;

if (i <= j) {

temp = ratio[i]; ratio[i] = ratio[j]; ratio[j] = temp;

temp = weight[i]; weight[i] = weight[j]; weight[j] = temp;

temp = profit[i]; profit[i] = profit[j]; profit[j] = temp;

i++; j--;

quicksort(ratio, weight, profit, low, j);

quicksort(ratio, weight, profit, i, high);

#include<stdio.h>

int main()

float weight[50], profit[50], ratio[50], Totalvalue = 0, temp, capacity, amount;

int n, i;

printf("Enter the number of items :");

scanf("%d", &n);

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

printf("Enter Weight and Profit for item[%d] :\n", i);

scanf("%f %f", &weight[i], &profit[i]);

}
 printf("Enter the capacity of knapsack :\n");

scanf("%f", &capacity);

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

ratio[i] = profit[i] / weight[i];

quicksort(ratio, weight, profit, 0, n - 1);

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

if (weight[i] > capacity)

break;

else {

Totalvalue = Totalvalue + profit[i];

capacity = capacity - weight[i];

if (i < n)

Totalvalue = Totalvalue + (ratio[i] * capacity);

printf("\nThe maximum value is :%f\n", Totalvalue);

return 0;

Least common subsequence

#include<stdio.h>

#include<stdlib.h>

#include<math.h>
int main(){

char a[11] = {'e','t','d','s','g','v','h','t','d','f','s'};

char b[9] = {'e','t','f','c','k','l','y','s','t'};

int dp[12][10];

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

dp[i][0] = 0;

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

dp[0][i] = 0;

for (int i = 1; i < 12; i++)

for (int j = 1; j < 10; j++)

if (a[i-1] == b[j-1])

dp[i][j] = 1 + dp[i-1][j-1];

else if(a[i-1] != b[j-1])

dp[i][j] = dp[i-1][j] < dp[i][j-1]? dp[i][j-1]: dp[i-1][j];

}
 }

int i = 12;

int j = 10;

while (i>0 && j>0)

if (a[i-1] == b[j-1])

printf("%c \n", a[i-1]);

i=i-1;

j=j-1;

else

if (dp[i-1][j] >= dp[i][j-1])

i=i-1;

else if (dp[i-1][j] < dp[i][j-1])

j=j-1;

}
 }

printf("%d", dp[11][9]);

return 0;

Matrix multiplication

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

void print_paren(int *s, int cols, int i, int j){

if(i==j){

printf("A%d", i);

return;

printf("(");

int k = s[i*cols + j];

print_paren(s, cols, i, k);

print_paren(s, cols, k+1, j);

printf(")");

int main(void){

int n;

if(scanf("%d", &n) != 1) return 0;

if(n < 1) return 0;

int *p = malloc(sizeof(int)*cols);

if(!p) return 0;

for(int i = 0; i <= n; i++) scanf("%d", &p[i]);

long long *m = malloc(sizeof(long long)*cols*cols);

int *s = malloc(sizeof(int)*cols*cols);

if(!m || !s){ free(p); free(m); free(s); return 0; }

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

for(int j = 1; j <= n; j++){

if(i == j) m[i*cols + j] = 0;

else m[i*cols + j] = LLONG_MAX/4;

s[i*cols + j] = 0;

for(int L = 2; L <= n; L++){

for(int i = 1; i <= n - L + 1; i++){

int j = i + L - 1;

for(int k = i; k <= j - 1; k++){

long long q = m[i*cols + k] + m[(k+1)*cols + j] + (long long)p[i-1] * p[k] * p[j];

if(q < m[i*cols + j]){

m[i*cols + j] = q;

s[i*cols + j] = k;

printf("Minimum number of multiplications: %lld\n", m[1*cols + n]);

printf("Optimal parenthesization: ");

printf("\n");

free(p);

free(m);

free(s);

return 0;

Merge sort

#include<stdio.h>

#include<stdlib.h>

void conquer(int arr[], int left, int mid, int right){

int i = left;

int j = mid + 1;

int temparr[100];

int k = 0;

while(i <= mid && j <= right){

if(arr[i] <= arr[j]){

temparr[k] = arr[i];

i++;

k++;

else{

temparr[k] = arr[j];

j++;

k++;
 }

while(i <= mid){

temparr[k] = arr[i];

i++;

k++;

while(j <= right){

temparr[k] = arr[j];

j++;

k++;

for (int i = left, j=0; i <= right; i++, j++)

arr[i] = temparr[j];

void divide(int arr[], int left, int right){

if(left < right){

int mid = left + (right- left)/2;

divide(arr, left, mid);

divide(arr, mid+1, right);

conquer(arr, left, mid, right);

}
 return;

int main(){

int arr[] = {1,3,63,6,8,9,4,6,4,78,2,6,99,2,3};

int left = 0;

int right = 14;

divide(arr, left, right);

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

printf("%d ", arr[i]);

return 0;

Nqueen

#include <stdio.h>

#include <stdlib.h>

#define MAX_N 10

int n;

int pos[MAX_N];

int solutions = 0;
int isSafe(int row, int col) {

for (int r = 0; r < row; ++r) {

int c = pos[r];

if (c == col) return 0;

if (abs(c - col) == abs(r - row)) return 0;

return 1;

void placeQueen(int row) {

if (row == n) {

printf("Solution %d:\n", ++solutions);

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

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

if (pos[r] == c) putchar('Q');

else putchar('.');

putchar('\n');

putchar('\n');

return;

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

if (isSafe(row, c)) {
 pos[row] = c;

placeQueen(row + 1);

int main(void) {

printf("Enter N (<= %d): ", MAX_N);

if (scanf("%d", &n) != 1 || n <= 0 || n > MAX_N) {

printf("Invalid input. Enter integer 1..%d\n", MAX_N);

return 1;

placeQueen(0);

printf("Total solutions found: %d\n", solutions);

return 0;

Quicksort

#include<stdio.h>

#include<stdlib.h>

int partition(int arr[], int low, int high){

int i = low-1;

int pivot = arr[high];

int temp;
 for (int j = low; j < high; j++)

if(arr[j] <= pivot){

i++;

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

i++;

temp = arr[i];

arr[i] = arr[high];

arr[high] = temp;

return i;

int quicksort(int arr[], int low, int high){

if(low >= high)

return 0;

int pivot = partition(arr, low, high);

quicksort(arr, pivot+1, high);

quicksort(arr, low, pivot-1);

int main(){

int arr[] = {1,8,23,4,6,8,2,6,9,3,2,6,8,0,1};

int low = 0;

int high = 14;

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

printf("%d ", arr[i]);

return 0;

Sorting technique

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

void sort(int arr[], int size){

for (int i = 0; i < size - 1; i++) {

for (int j = i + 1; j < size; j++) {

if (arr[i] > arr[j]) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

void rsort(int arr[], int size){

for (int i = 0; i < size - 1; i++) {

for (int j = i + 1; j < size; j++) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

void bubbleSort(int arr[], int n) {

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

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

if (arr[j] > arr[j + 1]) {

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

void rbubbleSort(int arr[], int n) {

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

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

if (arr[j] < arr[j + 1]) {

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;
 }

void insertionSort(int arr[], int n) {

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

int key = arr[i];

int j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j--;

arr[j + 1] = key;

void rinsertionSort(int arr[], int n) {

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

int key = arr[i];

int j = i - 1;

while (j >= 0 && arr[j] < key) {

arr[j + 1] = arr[j];

j--;

arr[j + 1] = key;

}
}

int main(){

FILE *fptr;

int arr[1000];

int arr2[1000];

int arr3[1000];

int arr4[1000];

int arr5[1000];

int arr6[1000];

int n = 0;

srand(time(NULL));

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

int random = rand()%1000 + 1;

arr[i] = random;

arr2[i] = random;

arr3[i] = random;

arr4[i] = random;

arr5[i] = random;

arr6[i] = random;

fptr = fopen("[Link]", 'w');

clock_t beforeexe, afterexe;

beforeexe = clock();

sort(arr, 1000);
afterexe = clock();

double diff = (double) (afterexe - beforeexe);

diff = diff/ CLOCKS_PER_SEC;

printf("time difference with random numbers= %f", diff );

rsort(arr2, 1000);

beforeexe = clock();

sort(arr2, 1000);

afterexe = clock();

diff = (double) (afterexe - beforeexe);

diff = diff/ CLOCKS_PER_SEC;

printf("time difference with reverse sorted array= %f", diff );

beforeexe = clock();

sort(arr, 1000);

afterexe = clock();

diff = (double) (afterexe - beforeexe);

diff = diff/ CLOCKS_PER_SEC;

printf("time difference with sorted numbers= %f", diff );

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

printf("%d\t", arr[i]);
}

beforeexe = clock();

bubbleSort(arr3, 1000);

afterexe = clock();

diff = (double) (afterexe - beforeexe);

diff = diff/ CLOCKS_PER_SEC;

printf("time difference with random numbers in bubble sort= %f", diff );

beforeexe = clock();

bubbleSort(arr3, 1000);

afterexe = clock();

diff = (double) (afterexe - beforeexe);

diff = diff/ CLOCKS_PER_SEC;

printf("time difference with sorted numbers in bubble sort= %f\n", diff );

rbubbleSort(arr3, 1000);

beforeexe = clock();

bubbleSort(arr3, 1000);

afterexe = clock();

diff = (double) (afterexe - beforeexe);

diff = diff/ CLOCKS_PER_SEC;

beforeexe = clock();

insertionSort(arr4, 1000);

afterexe = clock();

diff = (double) (afterexe - beforeexe);

diff = diff/ CLOCKS_PER_SEC;

printf("time difference with random numbers in insertion sort= %f", diff );

beforeexe = clock();

insertionSort(arr3, 1000);

afterexe = clock();

diff = (double) (afterexe - beforeexe);

diff = diff/ CLOCKS_PER_SEC;

printf("time difference with sorted numbers in insertion sort= %f", diff );

rinsertionSort(arr3, 1000);

beforeexe = clock();

insertionSort(arr3, 1000);

afterexe = clock();

diff = (double) (afterexe - beforeexe);

diff = diff/ CLOCKS_PER_SEC;

printf("time difference with reverse sorted numbers in insertion sort= %f", diff );

return 0;
};