Lab - 1

Title: WAP to find the Greatest Common Divisor (GCD) of two numbers.
Theory:
The Greatest Common Divisor (GCD) of two numbers is the largest number that divides
both numbers exactly without leaving a remainder. It is also called the Highest Common
Factor (HCF).
The Euclidean algorithm is an efficient method to compute the GCD by repeatedly
replacing the larger number with the remainder when divided by the smaller number. The
process continues until the remainder becomes zero, at which point the non-zero number is
the GCD.
Algorithm:
Step 1: Start
Step 2: Input two integers a and b.
Step 3: Repeat steps 4 to 6 while b ≠ 0.
Step 4: Compute remainder = a mod b.
Step 5: Assign a = b.
Step 6: Assign b = remainder.
Step 7: When b = 0, a is the GCD.
Step 8: Output a as the GCD.
Step 9: End
Source Code:
#include <stdio.h>
// Function to compute GCD using the Euclidean algorithm
int gcd(int a, int b)
{
while (b != 0)
{
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main()
{
int num1, num2;
printf("\t----------------------\n");
printf("\t\tG.C.D\n");
printf("\t----------------------\n");
printf("Enter the first number: ");
scanf("%d", &num1);
printf("Enter the second number: ");
scanf("%d", &num2);

// Compute and display the GCD

printf("GCD of %d and %d is %d\n", num1, num2, gcd(num1, num2));
printf("\nCompiled By: DEVRAJ SILWAL");
return 0;
}

Output:
 Lab - 2
Title: WAP to find the factorial of two numbers.
Theory:
The factorial of a non-negative integer n (denoted as n!) is the product of all positive integers
from 1 to n.
Mathematically, it is defined as:
 n! = n × (n - 1) × (n - 2) × ... × 1
 0! = 1 (by definition)

Algorithm:
Step 1: Start
Step 2: Input an integer n
Step 3: If n = 0 or n = 1, set factorial = 1 and go to Step 7
Step 4: Initialize factorial = 1
Step 5: Repeat step 6 for i = 2 to n
Step 6: Multiply factorial = factorial × i
Step 7: Output factorial as the result
Step 8: End
Source Code:
#include <stdio.h>

int factorial(int n)
{
if (n == 0 || n == 1)
return 1;
else
return n * factorial(n - 1);
}

int main()
{
printf("\t----------------------\n");
printf("\t\tFactorial\n");
printf("\t----------------------\n");

int num;
printf("Enter a number: ");
scanf("%d", &num);

if (num < 0)
printf("Factorial is not defined for negative numbers.\n");
else
printf("Factorial of %d = %d.\n", num, factorial(num));

printf("\nCompiled By: DEVRAJ SILWAL\n");

return 0;
}

Output:
 Lab - 3
Title: WAP to generate the Fibonacci series upto nth term.
Theory:
The Fibonacci sequence is a series of numbers in which each number is the sum of the two
preceding ones, typically starting with 0 and 1. Mathematically, the sequence can be
represented as:
 F(0) = 0
 F(1) = 1
 F(n) = F(n-1) + F(n-2) for n > 1
The Fibonacci sequence begins as: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Algorithm:
Step 1: Start
Step 2: Input the number of terms in series, n.
Step 3: If n = = 0, return 0.
Step 4: If n = = 1, return 1.
Step 5: Initialize two variables a = 0 and b = 1.
Step 6: For each number i from 2 to n, calculate the next Fibonacci number as c = a + b.
Step 7: Update the values a = b and b = c for the next iteration.
Step 8: After the loop, b will contain the Fibonacci number at index n.
Step 9: Output b as the Fibonacci number.
Step 10: End.
Source Code:
#include <stdio.h>

int main()
{
printf("\t--------------------------\n");
printf("\t\tFibonacci Series\n");
printf("\t--------------------------\n");

int i,num, first = 0, second = 1, next;

printf("Enter the number of terms to display in the Fibonacci
series: ");
scanf("%d", &num);

if (num <= 0)
printf("Please enter a positive integer.\n");
else if (num == 1)
{
printf("Fibonacci Series up to 1 term: \n");
printf("%d ", first);
}
else
{
printf("Fibonacci Series up to %d terms: \n", num);
printf("%d, %d, ", first, second);
for (i = 2; i < num; i++)
{
next = first + second;
printf("%d, ", next);
first = second;
second = next;
}
}
printf("\n\nCompiled By: DEVRAJ SILWAL\n");
return 0;
}

Output:
 Lab - 4
Title: WAP to search an element in a given array using sequential search.
Theory:
Sequential Search is a simple algorithm used to search for a specific element in a list or
array. It works by checking each element in the list one by one in a linear fashion, starting
from the first element and moving towards the last. The search continues until the element is
found or the entire list is traversed.
Algorithm:
Step 1: Start from the first element of the list.
Step 2: Compare the target element with the current element in the list.
Step 3: If the target element matches the current element, return the index of the
element.
Step 4: If the target element does not match, move to the next element in the list.
Step 5: Repeat steps 2-4 until the element is found or the list is fully traversed.
Step 6: If the element is not found after checking all the elements, return -1 to indicate
that the element is not present in the list.
Characteristics:
 Time Complexity: O(n) in the worst case, where n is the number of elements in the
array.
 Space Complexity: O(1), as it only requires a single variable to store the result.
 Best Case: O(1) (if the first element is the key).
 Worst Case: O(n) (if the key is not in the array or is at the last position).
Source Code:
#include <stdio.h>

int main()
{
printf("\t---------------------------\n");
printf("\tSequential Search\n");
printf("\t---------------------------\n");

int n, target, found = -1;

printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];
printf("Enter the elements of the array: \n");
for (int i = 0; i < n; i++)
{
printf("a[%d]=",i);
scanf("%d", &arr[i]);
}

printf("Enter the element to search: ");

scanf("%d", &target);
for (int i = 0; i < n; i++)
{
if (arr[i] == target)
{
found = i;
break;
}
}

if (found != -1)
{
printf("Element %d found at index %d.\n", target, found);
}
else
{
printf("Element %d not found in the array.\n", target);
}

printf("\nCompiled By: DEVRAJ SILWAL\n");

return 0;
}
Output:
 Lab - 5
Title: WAP to sort an array using bubble sort.
Theory:
Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly stepping
through the list to be sorted, comparing each pair of adjacent elements, and swapping them if
they are in the wrong order. The process continues until no more swaps are needed,
indicating that the array is sorted.
Algorithm:
Step 1: Start from the first element of the array.
Step 2: Compare the current element with the next element.
Step 3: If the current element is greater than the next element, swap them.
Step 4: Move to the next pair of adjacent elements and repeat the process.
Step 5: Continue traversing the array until no more swaps are required, indicating that
the array is sorted.
Step 6: The sorting process completes after multiple passes through the array.
Characteristics:
 Time Complexity: O(n²) in the worst and average case, where n is the number of
elements in the array.
 Space Complexity: O(1), as it requires only a constant amount of additional space.
 Best Case: O(n) if the array is already sorted (with an optimized version).
 Worst Case: O(n²) when the array is in reverse order.
Source Code:
#include <stdio.h>

int main()
{
printf("\t---------------------------\n");
printf("\t\tBubble Sort\n");
printf("\t---------------------------\n");

int n,i,j;
printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];
printf("Enter the elements of the array: \n");
for (i = 0; i < n; i++)
{
printf("a[%d]=",i);
scanf("%d", &arr[i]);
}

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

{
for (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;
}
}

printf("Sorted array: \n");

for (i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");

printf("\nCompiled By: DEVRAJ SILWAL\n");

return 0;
}
Output:
 Lab - 6
Title: WAP to sort an array using Selection Sort.
Theory:
Selection Sort is a comparison-based sorting algorithm. It works by dividing the array into
two parts: the sorted part and the unsorted part. Initially, the sorted part is empty, and the
unsorted part contains the entire array. In each iteration, the smallest (or largest) element
from the unsorted part is selected and swapped with the first unsorted element. This process
is repeated until the unsorted part becomes empty, resulting in a fully sorted array.
Algorithm:
Step 1: Start from the first element of the array.
Step 2: Find the smallest element in the unsorted part of the array.
Step 3: Swap the smallest element with the first unsorted element.
Step 4: Move the boundary of the sorted part by one element.
Step 5: Repeat steps 2-4 until the entire array is sorted.
Characteristics:
 Time Complexity: O(n²) in both the worst and average case, where n is the number
of elements in the array.
 Space Complexity: O(1), as it requires only a constant amount of additional space.
 Best Case: O(n²) (there is no improvement even if the array is sorted).
 Worst Case: O(n²) when the array is in reverse order.
Source Code:
#include <stdio.h>

int main()
{
printf("\t---------------------------\n");
printf("\t\tSelection Sort\n");
printf("\t---------------------------\n");

int n;
printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];
printf("Enter the elements of the array: \n");
for (int i = 0; i < n; i++)
{
printf("a[%d]=", i);
scanf("%d", &arr[i]);
}

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

{
int minIndex = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}

if (minIndex != i)
{
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}

printf("Sorted array: \n");

for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");

printf("\nCompiled By: DEVRAJ SILWAL\n");

 return 0;
}
Output:
 Lab - 7
Title: WAP to sort an array using Insertion Sort.
Theory:
Insertion Sort is a simple comparison-based sorting algorithm that builds the sorted array
one element at a time. It works by iterating through the array from the second element
onward. For each element, it is compared with the elements in the sorted part of the array
(which starts with the first element), and it is inserted into its correct position. This process
continues until all elements are sorted. Insertion Sort is efficient for small datasets or nearly
sorted arrays.
Algorithm:
Step 1: Start from the second element (index 1) of the array.
Step 2: Compare the current element with the previous elements of the sorted part of the
array.
Step 3: Shift all elements that are greater than the current element one position to the
right.
Step 4: Insert the current element at its correct position.
Step 5: Repeat steps 2-4 for all elements in the array.
Step 6: The array will be sorted once the algorithm completes.
Characteristics:
 Time Complexity: O(n²) in the worst and average case, where n is the number of
elements in the array.
 Space Complexity: O(1), as it only requires a constant amount of additional space.
 Best Case: O(n) when the array is already sorted.
 Worst Case: O(n²) when the array is in reverse order.
Source Code:
#include <stdio.h>

int main()
{
printf("\t---------------------------\n");
printf("\t\tInsertion Sort\n");
printf("\t---------------------------\n");

int n;
printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];
printf("Enter the elements of the array: \n");
for (int i = 0; i < n; i++)
{
printf("a[%d]=", i);
scanf("%d", &arr[i]);
}

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 = j - 1;
}

arr[j + 1] = key;
}

printf("Sorted array: \n");

for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");

printf("\nCompiled By: DEVRAJ SILWAL\n");

return 0;
}
Output:
 Lab - 8
Title: WAP to search an element in a given sorted array using Binary Search.
Theory:
Binary Search is an efficient algorithm for finding an element in a sorted array. Unlike
Sequential Search, which checks each element one by one, Binary Search works by
repeatedly dividing the search interval in half. The search begins by comparing the target
element with the middle element of the array:
 If the target element is equal to the middle element, the search is complete.
 If the target element is smaller than the middle element, the search continues in the
left half of the array.
 If the target element is larger than the middle element, the search continues in the
right half of the array. This process repeats until the target element is found or the
search interval is empty.
Algorithm:
Step 1: Start with two pointers: low (first index) and high (last index) of the array.
Step 2: Find the middle element using the formula: mid = (low + high) / 2.
Step 3: Compare the middle element with the target element:
 If the middle element is equal to the target, return the index.
 If the target is smaller, repeat the search on the left half (high = mid - 1).
 If the target is larger, repeat the search on the right half (low = mid + 1).
Step 4: Repeat steps 2-3 until the target is found or the search interval becomes invalid
(low > high).
Step 5: If the element is not found, return -1 to indicate that the element is not present in
the array.
Characteristics:
 Time Complexity: O(log n), where n is the number of elements in the array.
 Space Complexity: O(1), as it only requires a constant amount of extra space.
 Best Case: O(1), if the middle element is the target.
 Worst Case: O(log n), if the target element is not present or located at the end.
Source Code:
#include <stdio.h>

int main()
{
printf("\t---------------------------\n");
printf("\t\tBinary Search\n");
printf("\t---------------------------\n");

int n, target, low, high, mid, found = -1;

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

scanf("%d", &n);

int arr[n];
printf("Enter the elements of the array (must be sorted): \n");
for (int i = 0; i < n; i++)
{
printf("a[%d]=", i);
scanf("%d", &arr[i]);
}

printf("Enter the element to search: ");

scanf("%d", &target);
low = 0;
high = n - 1;

while (low <= high)

{
mid = (low + high) / 2;

if (arr[mid] == target)
{
found = mid;
break;
}
else if (arr[mid] < target)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}

if (found != -1)
{
 printf("Element %d found at index %d.\n", target, found);
}
else
{
printf("Element %d not found in the array.\n", target);
}

printf("\nCompiled By: DEVRAJ SILWAL\n");

return 0;
}

Output:
 Lab - 9
Title: WAP to find smallest and largest number in an array using Min-Max algorithm.
Theory:
The Min-Max algorithm is used to find the smallest (minimum) and largest (maximum)
elements in an array. It is a simple and efficient algorithm that scans through the entire array
to determine both the minimum and maximum values simultaneously. This can be done in a
single pass through the array, making the process efficient with a time complexity of O(n),
where n is the number of elements in the array.
Algorithm:
Step 1: Start by initializing two variables, min and max. Set both to the value of the first
element of the array.
Step 2: Traverse through the array from the second element to the last element.
Step 3: For each element:
 If the element is smaller than the current min, update min.
 If the element is larger than the current max, update max.
Step 4: Continue until all elements have been checked.
Step 5: After completing the traversal, min will hold the smallest element and max will
hold the largest element in the array.
Characteristics:
 Time Complexity: O(n), where n is the number of elements in the array, as the
algorithm traverses the array only once.
 Space Complexity: O(1), as only a constant amount of extra space is used.
 Best Case: O(n), as the array must be fully traversed to find both minimum and
maximum.
 Worst Case: O(n), same as best case.
Source Code:
#include <stdio.h>

int main()
{
printf("\t---------------------------\n");
printf("\t\tMin-Max Finding\n");
printf("\t---------------------------\n");

int n;
printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];
printf("Enter the elements of the array: \n");
for (int i = 0; i < n; i++)
{
printf("a[%d]=", i);
scanf("%d", &arr[i]);
}

int min = arr[0];

int max = arr[0];

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

{
if (arr[i] < min)
{
min = arr[i];
}
if (arr[i] > max)
{
max = arr[i];
}
}

printf("The minimum element is: %d\n", min);

printf("The maximum element is: %d\n", max);

printf("\nCompiled By: DEVRAJ SILWAL\n");

return 0;
}
Output:
 Lab - 10
Title: WAP to sort an array using Merge Sort.
Theory:
Merge Sort is a divide-and-conquer algorithm that divides the array into two halves,
recursively sorts both halves, and then merges the two sorted halves into a single sorted array.
It is an efficient sorting algorithm with a time complexity of O(n log n) in all cases (best,
average, and worst), making it suitable for large datasets. The algorithm works by recursively
dividing the array into smaller sub-arrays and merging them back in sorted order.
Algorithm:
Step 1: Divide the array into two halves (left and right).
Step 2: Recursively apply Merge Sort to the left half and the right half.
Step 3: Merge the two sorted halves by comparing elements and placing them in the
correct order.
Step 4: Repeat the merging process until the entire array is sorted.
Step 5: Return the sorted array.
Characteristics:
 Time Complexity: O(n log n), where n is the number of elements in the array.
 Space Complexity: O(n), due to the additional space required for the temporary
arrays during the merge step.
 Best Case: O(n log n)
 Worst Case: O(n log n)
Source Code:
#include <stdio.h>

void merge(int arr[], int left, int right)

{
if (left < right)
{
int mid = (left + right) / 2;

merge(arr, left, mid);

merge(arr, mid + 1, right);
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];

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

L[i] = arr[left + i];
for (int i = 0; i < n2; i++)
R[i] = arr[mid + 1 + i];

int i = 0, j = 0, k = left;

while (i < n1 && j < n2)

{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
 }
}

int main()
{
printf("\t---------------------------\n");
printf("\t\tMerge Sort\n");
printf("\t---------------------------\n");

int arr[] = {12, 11, 13, 5, 6, 7, 43, 23, 19};

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

printf("Given array:\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n\nSorted array:\n");
merge(arr, 0, n - 1);

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

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

printf("\nCompiled By: DEVRAJ SILWAL\n");

return 0;
}

Output:
 Lab - 11
Title: WAP to sort an array using Quick Sort.
Theory:
Quick Sort is an efficient, comparison-based, divide-and-conquer sorting algorithm. It works
by selecting a 'pivot' element from the array and partitioning the other elements into two sub-
arrays, according to whether they are smaller or larger than the pivot. The sub-arrays are then
sorted recursively.
Algorithm:
Step 1: Choose a pivot element from the array.
Step 2: Partition the array into two sub-arrays:
 One with elements smaller than the pivot.
 One with elements greater than the pivot.
Step 3: Recursively apply Quick Sort to the sub-arrays.
Step 4: Continue the process until the entire array is sorted.
Step 5: Return the sorted array.
Characteristics:
 Time Complexity: O(n log n), where n is the number of elements in the array.
 Space Complexity: O(log n), due to the recursion stack.
 Best Case: O(n log n)
  Worst Case: O(n²)

Source Code:
#include <stdio.h>

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

{
int pivot = arr[high];
int i = low - 1;

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

{
if (arr[j] <= pivot)
{
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

int temp = arr[i + 1];

arr[i + 1] = arr[high];
arr[high] = temp;

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);
}
}

int main()
{
printf("\t---------------------------\n");
printf("\t\tQuick Sort\n");
printf("\t---------------------------\n");

int arr[] = {12, 11, 13, 5, 6, 7, 43, 23, 19};

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

printf("Given array:\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n\n");

quickSort(arr, 0, n - 1);

printf("Sorted array:\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");

printf("\nCompiled By: DEVRAJ SILWAL\n");

return 0;
}

Output:
 Lab – 12
Title: WAP to sort an array using Heap Sort.
Theory:
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to
create a max heap or min heap. It works by building a heap from the input array and then
repeatedly extracting the maximum (or minimum) element from the heap to form the sorted
array. It is an efficient sorting algorithm, especially when we need to sort large datasets. It is
an in-place sorting algorithm, which means it does not require additional storage except for
the input array.
Algorithm:
 Step 1: Build a max heap from the given array.

Step 2: Swap the root (maximum) element with the last element of the array.

Step 3: Reduce the heap size by 1 (exclude the last element).

Step 4: Heapify the root element to maintain the heap property.

Step 5: Repeat steps 2-4 until the heap size is reduced to 1.

Step 6: The array will be sorted once the algorithm completes.

Characteristics:
 Time Complexity: O(n log n), where n is the number of elements in the array.
 Space Complexity: O(1), as it is an in-place sorting algorithm.

Source Code:
#include <stdio.h>

void heapify(int arr[], int n, int i)

{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
int temp;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;
 if (largest != i)
{
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;

heapify(arr, n, largest);
}
}

void heapSort(int arr[], int n)

{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

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

{
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

heapify(arr, i, 0);
}
}

int main()
{
printf("\t---------------------------\n");
printf("\t\tHeap Sort\n");
printf("\t---------------------------\n");

int arr[] = {12, 11, 13, 5, 6, 7, 43, 23, 19};

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

printf("Given array:\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n\n");

heapSort(arr, n);

printf("Sorted array:\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");

printf("\nCompiled By: DEVRAJ SILWAL\n");

return 0;
}

Output:

Lab – 13
Title: WAP to solve the Fractional Knapsack problem.
Theory:
The Fractional Knapsack problem is a variation of the Knapsack problem where we can
take fractions of an item. The objective is to maximize the total value of the knapsack by
selecting items (or fractions of items) based on their value-to-weight ratio. This problem can
be solved using a greedy approach. The approach is to sort the items by their value-to-weight
ratio in descending order, and then select items (or parts of them) until the knapsack's
capacity is full.
Algorithm:
Step 1: Calculate the value-to-weight ratio for each item.
 Step 2: Sort the items by their value-to-weight ratio in descending order.

Step 3: Select the items in the sorted order, adding the whole item if it fits in the
knapsack or the fraction of it if it doesn’t.

Step 4: Update the remaining capacity of the knapsack after each selection.

Step 5: Repeat until the knapsack is full or all items have been considered.

Characteristics:
 Time Complexity:
 Sorting: O(n log n)
 Selecting items: O(n)
 Overall Time Complexity: O(n log n)
 Space Complexity: O(n), as we need space to store the items.

Source Code:
#include <stdio.h>

struct Item
{
int value;
int weight;
float ratio;
};

void swap(struct Item* a, struct Item* b)

{
struct Item temp = *a;
*a = *b;
*b = temp;
}

void sort(struct Item arr[], int n)

{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (arr[j].ratio < arr[j + 1].ratio)
swap(&arr[j], &arr[j + 1]);
}
}
}

float fractionalKnapsack(int capacity, struct Item arr[], int n)

{
int currentWeight = 0;
float finalValue = 0.0;

printf("\n\nStep-by-Step Decision Process:\n");

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

{
printf("\nItem %d -> Value: %d, Weight: %d, Ratio: %.2f\n",
i + 1, arr[i].value, arr[i].weight, arr[i].ratio);

if (currentWeight + arr[i].weight <= capacity)

{
currentWeight += arr[i].weight;
finalValue += arr[i].value;
printf("Item %d fully included in the knapsack.\n",i+1);
}

else
{
int remainingWeight = capacity - currentWeight;
finalValue += arr[i].value * ((float)remainingWeight /
arr[i].weight);
printf("Item %d partially included (fractional part).\
n", i + 1);
break;
}
printf("Current knapsack weight: %d, Total value: %.2f\n",
currentWeight, finalValue);
}
return finalValue;
}

int main()
{
printf("\t---------------------------\n");
printf("\t\tFractional Knapsack\n");
printf("\t---------------------------\n");
 int n = 5;
struct Item arr[] = {
{60, 10, 6.0},
{100, 20, 5.0},
{120, 30, 4.0},
{80, 25, 3.2},
{90, 35, 2.5}
};

int capacity = 50;

printf("Given knapsack capacity: %d\n\n", capacity);

printf("Given items (value, weight, ratio):\n");

for (int i = 0; i < n; i++)
{
printf("Item %d -> Value: %d, Weight: %d, Ratio: %.2f\
n" ,i+1, arr[i].value, arr[i].weight, arr[i].ratio);
}

sort(arr, n);

float maxValue = fractionalKnapsack(capacity, arr, n);

printf("\nMaximum value we can obtain: %.2f\n", maxValue);

printf("\nCompiled By: DEVRAJ SILWAL\n");

return 0;
}

Output:
 Lab – 14
Title: WAP to demonstrate Job sequencing with deadlines.
Theory:
Job Sequencing with Deadlines is a scheduling problem where the goal is to select and
schedule jobs in such a way that the total profit is maximized, and each job must be
completed by its given deadline. Each job has a deadline and a profit, and we need to
sequence the jobs so that the maximum number of jobs are completed within their deadlines,
while also maximizing the total profit. The process involves sorting jobs based on profit in
descending order and then scheduling the jobs one by one. The jobs are assigned to time slots
before their respective deadlines, and if a slot is already filled, the job is discarded.
Algorithm:
Step 1: Sort the jobs in descending order of profit.

Step 2: Initialize an array to keep track of the time slots (deadlines).

Step 3: For each job, try to find a time slot for it, starting from its deadline and moving
backwards to 1.

Step 4: If a free time slot is found, schedule the job and add its profit to the total profit.

Step 5: If no free time slot is available, discard the job.

Step 6: Return the total profit and the sequence of jobs scheduled.

Characteristics:
 Time Complexity: O(n log n), where n is the number of jobs, due to the sorting step.
 Space Complexity: O(n), for storing the scheduled jobs and time slots.

Source Code:
#include <stdio.h>

struct Job
{
int id;
int deadline;
int profit;
};

void sortJobs(struct Job arr[], int n)

{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (arr[j].profit < arr[j + 1].profit)
{
struct Job temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void jobSequencing(struct Job arr[], int n)
{
int maxDeadline = 0;

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

{
if (arr[i].deadline > maxDeadline)
maxDeadline = arr[i].deadline;
}

int slots[maxDeadline];
for (int i = 0; i < maxDeadline; i++)
{
slots[i] = -1;
}

int totalProfit = 0;
int jobCount = 0;

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

{
for (int j = arr[i].deadline - 1; j >= 0; j--)
{
if (slots[j] == -1)
{
slots[j] = arr[i].id;
totalProfit += arr[i].profit;
jobCount++;
 break;
}
}
}
printf("Initial Jobs Data (id, deadline, profit):\n");
for (int i = 0; i < n; i++)
{
printf("Job %d -> Deadline: %d, Profit: %d\n", arr[i].id,
arr[i].deadline, arr[i].profit);
}
printf("\nJob sequence to maximize profit:\n");
for (int i = 0; i < maxDeadline; i++)
{
if (slots[i] != -1)
printf("Job %d -> ", slots[i]);
}
printf("\nTotal profit: %d\n", totalProfit);
}

int main()
{
printf("\t---------------------------\n");
printf("\tJob Sequencing with Deadlines\n");
printf("\t---------------------------\n");
struct Job arr[] = {
{1, 4, 20},
{2, 1, 10},
{3, 1, 40},
{4, 1, 30},
{5, 3, 50}
};
int n = sizeof(arr) / sizeof(arr[0]);
sortJobs(arr, n);

jobSequencing(arr, n);

printf("\nCompiled By: DEVRAJ SILWAL\n");

return 0;
}

Output: