Activity Selection Problem & Job Scheduling Problem – Lecture Note

Click on the following link to download the PDF of Activity Selection Problem & Job Scheduling Problem.

Activity Selection Problem & Job Scheduling Problem

Binary Search Algorithm – C Program

Introduction

In computer science, binary search or half-interval search algorithm finds the position of a specified value (the input “key”) within a sorted array. In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element’s key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special “Not found” indication is returned.

Implementation

//**********************************************************
// Binary Search Algorithm Implementation
//**********************************************************
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<dos.h>

int sequential(int *a, int n, int x)
{
int i;
for(i=0;i<n;i++)
if((*(a+i)) >= x) return i;
return n;
}

int divnconq(int *a,int n,int x)
{
if (n==0 || x>(*(a+(n-1)))) return n;
else return binrec(&a[0],0,n-1,x);
}

int binrec(int *a,int st, int n,int x)
{
int k;
if(st==n) return st;
k=(st+n)/2;
if(x<=(*(a+k))) return binrec(&a[0],st,k,x);
else return binrec(&a[0],k+1,n,x);
}

void main()
{
int a[100],x,n,i;
struct time t1,t2,t3,t4;
clrscr();

printf(“Enter the total Number of Elements: “);
scanf(“%d”,&n);
printf(“\nEnter %d elements in Ascending Order only: “,n);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);

printf(“\nNow, Enter the element you want to search: “);
scanf(“%d”,&x);

printf(“\n************** Search Element(SEQUENTIAL) **************”);
printf(“\nPosition (Index) for %d element is %d”,x,sequential(&a[0],n,x));
printf(“\n********************************************************\n”);

printf(“\n************** Binary Search (DIVIDE & CONQUER) **************”);
printf(“\nPosition (Index) for %d element is %d”,x,divnconq(&a[0],n,x));
printf(“\n********************************************************\n\n”);
getch();
}

Binary Search Algorithm – PPT

Click on the following link to download the PPT of Binary Search Algorithm.

BinarySearchAlgorithm

Heap Sort Algorithm – Lecture Note

Click following link to download PDF for Heap Sort Algorithm.

HeapSortAlgorithm.pdf

Heap Sort Algorithm – C Program

Introduction

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort.

The first loop, the Θ(n) “heapify” phase, puts the array into heap order. The second loop, the O(n·lg(n)) “sortdown” phase, repeatedly extracts the maximum and restores heap order.

For more details about Heap Sort click here:

Implementation

//**********************************************************
// Heap Sort Algorithm Implementation & Analysis.
//**********************************************************

#include<stdio.h>
#include<conio.h>
int t[25],tsize; /* GLOBAL TREE AS AN ARRAY WITH IT’S SIZE */

/* Find a Parent Node of a given node */
int parent(int i)
{ return (i/2); }

/* Find a Left Child of a given node */
int left(int i)
{ return (i*2); }

/* Find a Right Child of a given node */
int right(int i)
{ return ((i*2)+1); }

void max_heapify(int i)
{
int l,r,largest,temp,k;
l=left(i);
r=right(i);
/*
printf(“\n————————————\n”);
for(k=1;k<=tsize;k++)
printf(” %d -“,t[k]);
*/
if(l<=tsize && t[l] > t[i])
largest=l;
else largest=i;

if(r<=tsize && t[r] > t[largest])
largest=r;

if(largest!=i)
{
temp=t[i];
t[i]=t[largest];
t[largest]=temp;
max_heapify(largest);
}
}

void main()
{
int i,temp,tstemp;
clrscr();

printf(“Enter Size of Tree:”);
scanf(“%d”,&tsize);

printf(“Now Enter %d Elements of Binary Tree\n”,tsize);
for(i=1;i<=tsize;i++)
scanf(“%d”,&t[i]);

printf(“\n*************************\nInitial Random Binary Tree:\n”);
for(i=1;i<=tsize;i++)
printf(” %d -“,t[i]);
printf(“\n*************************\n”);

/* BUILD-MAX-HEAP PROCEDURE */
for(i=(int)(tsize/2);i>=1;i–)
max_heapify(i);

printf(“\n***********************************\n FINAL MAX-HEAP:\n”);
for(i=1;i<=tsize;i++)
printf(” %d -“,t[i]);
printf(“\n*************************\n”);

/* HEAP-SORT PROCEDURE */
tstemp=tsize;
for(i=tsize;i>=2;i–)
{
temp=t[i];
t[i]=t[1];
t[1]=temp;
tsize=tsize-1;
max_heapify(1);
}

printf(“\n*******************************\n FINAL HEAP-SORTED TREE:\n”);
for(i=1;i<=tstemp;i++)
printf(” %d -“,t[i]);
printf(“\n*************************\n”);
getch();
}