University of Science and Technology Chittagong

Batch: 42nd

Department of Computer Science & Engineering

Course Title: Algorithm

Course Code: CSE-221

Submitted To

Forkan Karim Mazumder

Lecturer

CSE, FSET, USTC

Submitted by:

Name: Abdul Mifthaul Sabid

Roll: 24010166

Reg. No: 1150

Section: B

 Submission Date: 20.11.2025

Experiment Name : Establishing a program to demonstrate Fractional Knapsack problem using c

Input Implementation

#include <stdio.h>

void fractionalKnapsack(int val[], int wt[], int count, int maxCap) {

float ratio[count];

int i, j;

// Compute ratio (value per weight)

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

ratio[i] = (float)val[i] / wt[i];

// Sort items by descending ratio

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

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

if (ratio[i] < ratio[j]) {

float rTemp = ratio[i];

ratio[i] = ratio[j];

ratio[j] = rTemp;

int vTemp = val[i];

val[i] = val[j];
 val[j] = vTemp;

int wTemp = wt[i];

wt[i] = wt[j];

wt[j] = wTemp;

float maxValue = 0.0;

int usedWeight = 0;

// Pick items greedily

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

if (usedWeight + wt[i] <= maxCap) {

// take the whole item

usedWeight += wt[i];

maxValue += val[i];

} else {

// take fraction

int spaceLeft = maxCap - usedWeight;

float part = (float)spaceLeft / wt[i];

maxValue += val[i] * part;

break;

}
 }

printf("\nTotal Maximum Value: %.2f\n", maxValue);

int main() {

int values[] = {55, 70, 170};

int weights[] = {20, 40, 80};

int capacity = 90;

int itemCount = sizeof(values) / sizeof(values[0]);

fractionalKnapsack(values, weights, itemCount, capacity);

return 0;

Output
Experiment no 2

Experiment Name : Constructing a program to solve word breaking problem using c

Input Implementation

#include <stdio.h>

#include <string.h>

// Check whether a piece exists in dictionary

int existsInDict(char piece[], char dict[][20], int total) {

for (int i = 0; i < total; i++) {

if (strcmp(piece, dict[i]) == 0)

return 1;

return 0;

// Break string into valid dictionary words

void splitWords(char text[], char dict[][20], int total) {

int length = strlen(text);

char temp[50];

printf("Input String: %s\n", text);

printf("Word Break Result: ");

int pos = 0;
 while (pos < length) {

int matched = 0;

for (int end = length; end > pos; end--) {

int segLen = end - pos;

strncpy(temp, text + pos, segLen);

temp[segLen] = '\0';

if (existsInDict(temp, dict, total)) {

printf("%s ", temp);

pos = end;

matched = 1;

break;

if (!matched) {

printf("\nNo valid word break possible!\n");

return;

printf("\n");

int main() {
 // Updated dictionary for the sentence

char dict[][20] = {

"I", "love", "eating", "and", "sleeping",

"in", "my", "leisure"

};

int size = sizeof(dict) / sizeof(dict[0]);

// Input string without spaces

char text[] = "Iloveeatingandsleepinginmyleisure";

splitWords(text, dict, size);

return 0;

Output
Experiment no 3

Experiment Name : Building a program to calculate fibonacci number for 20 using c

Input Implementation

#include <stdio.h>

// Function to calculate nth Fibonacci number

long long fibonacci(int n) {

if (n == 0) return 0;

if (n == 1) return 1;

long long a = 0, b = 1, next;

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

next = a + b;

a = b;

b = next;

return b;

int main() {

int n = 44; // Change to 44

long long result = fibonacci(n);

printf("The 44th Fibonacci number is: %lld\n", result);

Output

Experiment no 4

Experiment Name : Creating a program to sort an array using merge sort algorithm that will
demonstrate Divide and Conquer technique using c programming language

Input Implementation

#include <stdio.h>

// Function to merge two sorted sections of the array

void combine(int numbers[], int leftStart, int middle, int rightEnd) {

int leftIndex = leftStart, rightIndex = middle + 1, tempIndex = 0;

int temp[rightEnd - leftStart + 1];

while (leftIndex <= middle && rightIndex <= rightEnd) {

if (numbers[leftIndex] <= numbers[rightIndex]) {

} else {

temp[tempIndex++] = numbers[rightIndex++];

while (leftIndex <= middle) temp[tempIndex++] = numbers[leftIndex++];

while (rightIndex <= rightEnd) temp[tempIndex++] = numbers[rightIndex++];

for (int i = leftStart, k = 0; i <= rightEnd; i++, k++)

numbers[i] = temp[k];

// Recursive Merge Sort function

void divideAndSort(int numbers[], int start, int end) {

if (start < end) {

int middle = start + (end - start) / 2;

divideAndSort(numbers, start, middle);

divideAndSort(numbers, middle + 1, end);

combine(numbers, start, middle, end);

// Helper function to print the array

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

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

printf("\n");

int main() {

int data[] = {100, 77, 33, 67, 10, 92, 55};

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

printf("Before sorting:\n");

showArray(data, n);

divideAndSort(data, 0, n - 1);

printf("After sorting using Merge Sort:\n");

showArray(data, n);

return 0;

Output