OS-Shortest Job First-SJF Scheduling

 #include<stdio.h>

int main()

{

    int bt[20],p[20],wt[20],tat[20],i,j,n,total=0,totalT=0,pos,temp;

    float avg_wt,avg_tat;

    printf("Enter number of process:");

    scanf("%d",&n);

 

    printf("\nEnter Burst Time:\n");

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

    {

        printf("p%d:",i+1);

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

        p[i]=i+1;

    }

 

    //sorting of burst times

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

    {

        pos=i;

        for(j=i+1;j<n;j++)

        {

            if(bt[j]<bt[pos])

                pos=j;

        }

 

        temp=bt[i];

        bt[i]=bt[pos];

        bt[pos]=temp;

 

        temp=p[i];

        p[i]=p[pos];

        p[pos]=temp;

    }

 

    wt[0]=0;

 

    //finding the waiting time of all the processes

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

    {

        wt[i]=0;

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

             //individual WT by adding BT of all previous completed processes

            wt[i]+=bt[j];

 

        //total waiting time

        total+=wt[i];   

    }

 

    //average waiting time

    avg_wt=(float)total/n;  

 

    printf("\nProcess\t Burst Time \tWaiting Time\tTurnaround Time");

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

    {

        //turnaround time of individual processes

        tat[i]=bt[i]+wt[i]; 

 

        //total turnaround time

        totalT+=tat[i];      

        printf("\np%d\t\t %d\t\t %d\t\t\t%d",p[i],bt[i],wt[i],tat[i]);

    }

 

    //average turnaround time

    avg_tat=(float)totalT/n;     

    printf("\n\nAverage Waiting Time=%f",avg_wt);

    printf("\nAverage Turnaround Time=%f",avg_tat);

}

OS- First Come First Serve - FCFS Scheduling

 #include <stdio.h>

int main()

{

    int pid[15];

    int bt[15];

    int n,i;

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

    scanf("%d",&n);

 

    printf("Enter process id of all the processes: ");

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

    {

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

    }

 

    printf("Enter burst time of all the processes: ");

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

    {

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

    }

 

    int wt[n];

    wt[0]=0;

 

    //for calculating waiting time of each process

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

    {

        wt[i]= bt[i-1]+ wt[i-1];

    }

 

    printf("Process ID     Burst Time     Waiting Time     TurnAround Time\n");

    float twt=0.0;

    float tat= 0.0;

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

    {

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

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

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

 

        //calculating and printing turnaround time of each process

        printf("%d\t\t", bt[i]+wt[i]);

        printf("\n");

 

        //for calculating total waiting time

        twt += wt[i];

 

        //for calculating total turnaround time

        tat += (wt[i]+bt[i]);

    }

    float att,awt;

 

    //for calculating average waiting time

    awt = twt/n;

 

    //for calculating average turnaround time

    att = tat/n;

    printf("Avg. waiting time= %f\n",awt);

    printf("Avg. turnaround time= %f",att);

}

Program run command in Linux(Ubuntu)

 For Cpp

Create- gedit filename.cpp

Compile- g++ filename.cpp

Run- ./a.out

For C

Create- gedit filename.c

Compile- gcc filename.c

Run- ./a.out

For Java

Create- gedit filename.java

Compile- javac filename.java

Run- java filename

For python

Create- gedit filename.py

python3 filename.py  //only interpreter is used in python

Infix to prefix conversion

 ALGORITHM:

STEP 1:

Add " ( " at the beginning of the infix expression and then reverse.

STEP 2:

Push " ) " on to the stack.

STEP 3:

Scan every character and repeat step 4 to step 7 until " ( " is encountered.

STEP 4:

If input is operand add in the output.

STEP 5:

If input is " ) " push into the stack.

STEP 6:

If input is "(" pop all the operators from the stack and add in the output one by one until ")" is popped.

STEP 7:

If input is operator pop all the stack which is higher precedence than input operator .Push input operator into the stack.

STEP 8:

Reverse the output

EXAMPLE:

Infix to postfix conversion

 Step 1: Add " ) " to the end of the infix expression 

Step 2: Push " ( " on to the stack 

Step 3: Repeat until each character in the infix notation is scanned 

            - IF a " ( " is encountered, push it on the stack IF an operand (whether a digit or a character) is                      encountered, add it postfix expression. 

            - IF a " ) " is encountered, then 

                       a. Repeatedly pop from stack and add it to the postfix expression until a " ( " is                                             encountered. 

                       b. Discard the " ( " . That is, remove the " ( " from stack and do not add it to the postfix                              expression. 

           - IF an operator is encountered, then 

                      a. Repeatedly pop from stack and add each operator (popped from the stack) to the postfix expression which has the same precedence or a higher precedence than  0 .

                      b. Push the operator to the stack [END OF IF] 

Step 4: Repeatedly pop from the stack and add it to the postfix expression until the stack is empty 

Step 5: EXIT

Linked list push-pop

 #include<stdio.h>

#include<stdlib.h>

struct node {

    int data;

    struct node* link;

};

struct node* top = NULL;

void push() {

    struct node* temp = (struct node*) malloc(sizeof(struct node));

    printf("Enter a value: ");

    scanf("%d", &temp->data);

    temp->link = top;

    top = temp;

}

void pop() {

    if (top == NULL) {

        printf("Stack underflow\n");

    } else {

        struct node* temp = top;

        top = top->link;

        printf("Popped value = %d\n", temp->data);

        free(temp);

    }

}

void display() {

    if (top == NULL) {

        printf("Empty stack\n");

    } else {

        struct node* temp = top;

        while (temp != NULL) {

            printf("%d ", temp->data);

            temp = temp->link;

        }

        printf("\n");

    }

}

int main() {

    int choice;

    while (1) {

        printf("Enter 1 for push\n");

        printf("Enter 2 for pop\n");

        printf("Enter 3 for display\n");

        printf("Enter 4 for exit\n");

        printf("Enter your choice: ");

        scanf("%d", &choice);

        switch (choice) {

            case 1:

                push();

                break;

            case 2:

                pop();

                break;

            case 3:

                display();

                break;

            case 4:

                printf("Exiting the program\n");

                exit(0);

            default:

                printf("Wrong choice\n");

        }

    }

    return 0;

}

Array Insertion deletion

  #include<iostream>

using namespace std;

class array

{

int a[30], n;

public:

void input()

{

cout<<"Enter the length: ";

cin>>n;

cout<<"Enter a value for the array "<<endl;

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

cin>>a[i];

}

void insert_begin()

{

int value;

cout<<"Enter a value for insertion at the front "<<endl;

cin>>value;

n=n+1;

for(int i=n-1; i>=1; i--)

{

a[i]=a[i-1];

}

a[0]=value;

}

void insert_end()

{

int value;

cout<<"Enter a value for insertion at the end "<<endl;

cin>>value;

n=n+1;

a[n-1]=value;

}

void insert_position()

{

int pos;

cout<<"Enter the position "<<endl;

cin>>pos;

int value;

cout<<"Enter the value "<<endl;

cin>>value;

for(int i=n-1; i>=pos; i--)

{

a[i]=a[i-1];

}

a[pos-1]=value;

}

void display()

{

cout<<"The value of array "<<endl;

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

cout<<a[i]<<" ";

cout<<endl;

}

void delete_begin()

{

int value;

value=a[0];

cout<<"The deleted value is "<<value<<endl;

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

{

a[i-1]=a[i];

}

n=n-1;

}

void delete_end()

{

int value;

value=a[n-1];

cout<<"The deleted value is "<<value<<endl;

n=n-1;

}

void delete_position()

{

int value, pos;

cout<<"Enter position "<<endl;

cin>>pos;

value=a[pos-1];

cout<<"The deleted value is "<<value<<endl;

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

{

a[i-1]=a[i];

}

n=n-1;

}

};

int main()

{

array ob;

ob.input();

while(1)

{

cout<<"Enter 1 for displaying array "<<endl;

cout<<"Enter 2 for inserting element at the front "<<endl;

cout<<"Enter 3 for inserting element at the end "<<endl;

cout<<"Enter 4 for inserting element at the given position "<<endl;

cout<<"Enter 5 for deleting element from the front "<<endl;

cout<<"Enter 6 for deleting element from the end "<<endl;

cout<<"Enter 7 for deleting element from a given position "<<endl;

cout<<"Enter 8 for exit "<<endl;

int choice;

cin>>choice;

switch(choice)

{

case 1: 

ob.display();

break;

case 2:

cout<<"\nValue before insertion\n";

ob.display();

ob.insert_begin();

cout<<"\nValue after insertion\n";

ob.display();

break;

case 3:

cout<<"\nValue before insertion\n";

ob.display();

ob.insert_end();

cout<<"\nValue after insertion\n";

ob.display();

break;

case 4:

cout<<"\nValue before insertion\n";

ob.display();

ob.insert_position();

cout<<"\nValue after insertion\n";

ob.display();

break;

case 5:

cout<<"\nValue before deletion\n";

ob.display();

ob.delete_begin();

cout<<"\nValue after deletion\n";

ob.display();

break;

case 6:

cout<<"\nValue before deletion\n";

ob.display();

ob.delete_end();

cout<<"\nValue after deletion\n";

ob.display();

break;

case 7:

cout<<"\nValue before deletion\n";

ob.display();

ob.delete_position();

cout<<"\nValue after deletion\n";

ob.display();

break;

case 8:

cout<<"Exit from program";

break;

default:

cout<<"Enter a valid choice\n";

}

if(choice==8)

break;

}

return 0;

}

 

Sparse Matrix

 #include<iostream>

using namespace std;

int main()

{

int a[10][10],row,col,count=0,i,j,k=1;

int s[10][3];

cout<<"total number of row";

cout<<"total number of column";

cin>>row;

cin>>col;

cout<<"enter value";

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

{

for(j=0;j<col;j++)

{

cin>>a[i][j];

}

}

cout<<"matrix element\n";

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

{

for(j=0;j<col;j++)

{

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

}

cout<<"\n";

}

//count total number of nonzero elements

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

{

for(j=0;j<col;j++)

{

if(a[i][j]!=0)

{

count++;

}

}

}

cout<<count;

s[0][0]=row;

s[0][1]=col;

s[0][2]=count;

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

{

for(j=0;j<col;j++)

{

if(a[i][j]!=0)

{

s[k][0]=i;

s[k][1]=j;

s[k][2]=a[i][j];

k++;

}

}

}

cout<<"\n output array \n";

for(i=0;i<count+1;i++)

{

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

{

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

}

cout<<"\n";

}

}

Stack using linked list

 #include<stdio.h>

#include<malloc.h>

struct node

  {

    int data;

    struct node *link;

  };

 struct node * top= NULL;  //Initially stack is empty

  void push()

   {

       struct node*temp;

       temp=(struct node *)malloc(sizeof(struct node));

       printf("Enter a value");

       scanf("%d",&temp->data);

       temp->link=top;

       top=temp;

} 

   void pop()

    {

    if(top==NULL)

    {

    printf("Stack underflow");

}

else

{

struct node*temp=top;

top=top->link;

printf("poped value=%d",temp->data);

free(temp);

}

}

    void display()

  {

  struct node *temp=top;

  if(top==NULL)

  {

  printf("Empty stack");

   }

  else

   {

 while(temp!=NULL)

    {

    printf("%d",temp->data);

    temp=temp->link;

}

} 

  }

  

int main()

    {

    while(1)

    {

    printf("enter 1 for push\n");

    printf("enter 2 for pop\n");

    printf("enter 3 for display\n");

    printf("enter 4 for exit");

   

int choice;

    scanf("%d",&choice);

    switch(choice)

    {

    case 1:

    push();

break;

case 2:

pop();

break;

case 3:

display();

break;

case 4:

printf("end of the program");

break;

default:

printf("wrong choice\n"); 

  }

  if (choice==4)

  break;

}

}

Binary Search

 #include <iostream>

using namespace std;

int binarySearch(int array[], int value, int low, int high) 

{

  while (low <= high) 

  {

    int mid = (low + high) / 2;

    if (value==array[mid])

    {

      return mid;

    }

    else

    {

     if (value<array[mid])

       high = mid - 1;

     else

       low = mid + 1;

}

  }

  return 0;

}

int main() {

  int array[] = {3, 4, 5, 6, 7, 8, 9};

  int value = 4;

  int n = sizeof(array) / sizeof(array[0]);

  int result = binarySearch(array, value, 0, n - 1);

  cout<<"Value found in index "<<result;

}

Linear Search

 // Linear Search

#include <iostream>  

using namespace std;  

int linearSearch(int a[], int n, int val) {  

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

    {  

        if (a[i] == val)  

        return i+1;  

    }  

  return -1;  

}  

int main() {  

  int a[] = {69, 39, 29, 10, 56, 40, 24, 13, 51};

  int val = 56; // value to be searched  

  int n = sizeof(a) / sizeof(a[0]); // size of array  

  int result = linearSearch(a, n, val);

  cout<<"The elements of the array are - ";  

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

  cout<<a[i]<<" ";    

  cout<<"\nElement to be searched is - "<<val;    

  if (result == -1)  

  cout<<"\nElement is not present in the array";  

  else  

  cout<<"\nElement is present at "<<result<<" position of array";  

  return 0;  

}

Insertion Sort

 //Insertion Sort

#include <iostream>  

using namespace std;  

  

void insertionSort(int a[], int n)

{  

    int i, j, temp;  

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

        temp = a[i];  

        j = i - 1;  

  

        while(j>=0 && temp <= a[j]) 

        {    

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

            j = j-1;    

        }    

        a[j+1] = temp;    

    }  

}  

void displayArray(int a[], int n) 

{  

    int i;  

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

        cout << a[i] <<" ";  

}  

  

int main()  

{  

    int a[] = { 89, 45, 35, 8, 12, 2 };  

    int n = sizeof(a) / sizeof(a[0]);  

    cout<<"Before sorting array elements are - "<<endl;  

    displayArray(a, n);  

    insertionSort(a, n);  

    cout<<"\nAfter sorting array elements are - "<<endl;  

    displayArray(a, n);  

    return 0;  

}

Selection Sort

 //Selection Sort

#include<iostream>

using namespace std;

void selectionSort(int arr[], int n)

{

int i, j, min_idx;

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

min_idx = i;

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

if (arr[j] < arr[min_idx])

min_idx = j;

}

if (min_idx != i)

swap(arr[min_idx], arr[i]);

}

}

void DisplayArray(int arr[], int size)

{

int i;

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

cout << arr[i] << " ";

cout << endl;

}

}

int main()

{

int arr[] = { 64, 25, 12, 22, 11 };

int n = sizeof(arr) / sizeof(arr[0]);

selectionSort(arr, n);

cout << "Sorted array: \n";

DisplayArray(arr, n);

return 0;

}

Bubble Sort

 #include<iostream>

using namespace std;

class BubbleSort

{

int a[20],length,i,j;

public:

BubbleSort()

{

length=5;

}

void input_length()

{

cout<<"Enter length"<<endl;

cin>>length;

}

void input_array()

{

cout<<"Enter array elements"<<endl;

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

{

cin>>a[i];

}

}

void display_array()

{

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

{

cout<<a[i]<<" "<<endl;

}

}

void bubbleSort()

{

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

{

for(j=0;j<length-i-1;j++)

    {

     if(a[j]>a[j+1])

     {

      int temp=a[j];

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

      a[j+1]=temp;

}

    }

}

}

};

int main()

{

BubbleSort ob;

ob.input_length();

ob.input_array();

cout<<"Array elements before sorting"<<endl;

ob.display_array();

ob.bubbleSort();

cout<<"Array elements after sorting"<<endl;

ob.display_array();

return 0;

}

Linked list insert-delete-display-search-count

 #include<iostream>

using namespace std;

class Node

{

public:

int data;

Node *link;

};

class LinkedList

{

Node *head;

public:

LinkedList();

void myInsertBeg();

void myInsertEnd();

void myInsertPos(int p);

void myDeleteBeg();

void myDeleteEnd();

void myDeletePos(int p);

void mySreach();

void myCount();

void myShow();

};

LinkedList::LinkedList()

{

head=NULL;

}

void LinkedList::myInsertBeg()

{

Node *temp;

int n;

temp=new Node();

cout<<"Enter the value to insert: ";

cin>>n;

temp->data=n;

if(head==NULL)

{

temp->link=NULL;

head=temp;

}

else

{

temp->link=head;

head=temp;

}

}

void LinkedList::myInsertEnd()

{

Node *temp,*h;

int n;

temp=new Node();

cout<<"Enter the value to insert: ";

cin>>n;

temp->data=n;

temp->link=NULL;

h=head;

while((h->link)!=NULL)

{

h=h->link;

}

h->link=temp;

}

void LinkedList::myInsertPos(int p)

{

Node *temp,*h;

int n,c=1;

temp=new Node();

cout<<"Enter the value to insert:";

cin>>n;

temp->data=n;

h=head;

while(c<(p-1))

{

h=h->link;

c++;

}

temp->link=h->link;

h->link=temp;

}

void LinkedList::myDeleteBeg()

{

head=head->link;

cout<<"First element is deleted.";

}

void LinkedList::myDeleteEnd()

{

Node *h;

h=head;

while(((h->link)->link)!=NULL)

{

h=h->link;

}

h->link=NULL;

cout<<"Last element is deleted.";

}

void LinkedList::myDeletePos(int p)

{

Node *h;

h=head;

int c=1;

while(c<(p-1))

{

h=h->link;

c++;

}

h->link=(h->link)->link;

cout<<"The element is deleted.";

}

void LinkedList::mySreach()

{

Node *h;

h=head;

int num,c=1;

cout<<"Enter the value which you want to search:";

cin>>num;

while((h->link)!=NULL)

{

if((h->data)==num)

{

cout<<"The number is found at position:"<<c;

}

h=h->link;

c++;

}

if((h->data)==num)

{

cout<<"The number is found at position:"<<c;

}

else

{

cout<<"The number is not present in the linkedlist.";

}

}

void LinkedList::myShow()

{

Node *h;

h=head;

while(h!=NULL)

{

cout<<h->data<<" ";

h=h->link;

}

}

void LinkedList::myCount()

{

Node *h;

h=head;

int count=0;

while((h->link)!=NULL)

{

count++;

h=h->link;

}

cout << "Count of nodes is " <<++count;

}

int main()

{

LinkedList ob;

int a=0,b,pos;

while(a==0)

{

cout<<"\n--menu--\n1.add at the beg\n2.add at the end\n3.add at a position\n";

cout<<"4.delete from begining\n5.delete from end\n6.delete at a position\n";

cout<<"7.search\n8.count\n9.show\n10.exit\n";

cout<<"Enter your option:";

cin>>b;

switch(b)

{

case 1:

ob.myInsertBeg();

break;

case 2:

ob.myInsertEnd();

break;

case 3:

cout<<"Enter the position where you want to insert:";

cin>>pos;

ob.myInsertPos(pos);

cout<<"The value is inserted successfully.";

break;

case 4:

ob.myDeleteBeg();

break;

case 5:

ob.myDeleteEnd();

break;

case 6:

cout<<"Enter the position where you want to delete:";

cin>>pos;

ob.myDeletePos(pos);

break;

case 7:

ob.mySreach();

break;

case 8:

ob.myCount();

break;

case 9:

ob.myShow();

break;

default:

if(b==10)

{

a=1;

    cout<<"You are exit from the porgram!";

}

else

{

cout<<"You enter wrong option!";

}

}

}

}