LAB Assignment - 1
Name: Atharva Honrao
Registration No: 21BDS0135
Course Title: DAA Lab
Faculty: Ebenezer Juliet
Greedy Strategy
A] Fractional Knapsack
Aim:
To write the algorithm, code, screenshot, test cases (2) and the
result of the Fractional Knapsack Problem using Greedy Strategy
C Language.
Algorithm:
Greedy-Fractional-Knapsack (w[1..n], p[1..n], W)
for i = 1 to n
do x[i] = 0
weight = 0
for i = 1 to n
if weight + w[i] ≤ W then
x[i] = 1
weight = weight + w[i]
else
x[i] = (W - weight) / w[i]
weight = W
break
return x
Code:
#include<stdio.h>
int n=4;
int c[10]={10,40,20,24};//weight
int v[10]={100,280,120,120};//profit
int W = 60;
void simple_fill() {
int cur_w;
float tot_v;
int i, maxi;
int used[10];
for (i = 0; i < n; ++i)
used[i] = 0;
cur_w = W;
while (cur_w > 0) {
maxi = -1;
for (i = 0; i < n; ++i)
if ((used[i] == 0) &&
((maxi == -1) || ((float)v[i]/c[i] >(float)v[maxi]/c[maxi])))
maxi = i;
used[maxi] = 1;
cur_w -= c[maxi];
tot_v += v[maxi];
if (cur_w >= 0)
printf("Added object %d (%d$, %dKg) completely in the bag. Space
left: %d.\n", maxi + 1, v[maxi], c[maxi], cur_w);
else {
printf("Added %d%% (%d$, %dKg) of object %d in the bag.\n",
(int)((1 + (float)cur_w/c[maxi]) * 100), v[maxi], c[maxi], maxi + 1);
tot_v -= v[maxi];
tot_v += (1 + (float)cur_w/c[maxi]) * v[maxi];
}
}
printf("Filled the bag with objects worth %.2f$.\n", tot_v);
}
int main(int argc, char *argv[]) {
simple_fill();
return 0;
}
Program:
Execution:
Result:
Thus, we successfully verified and drove output using Fractional
Knapsack Problem using Greedy Strategy C Language.
B] Huffman Coding
Aim:
To write the algorithm, code, screenshot, test cases (2) and the
result of the Huffman Coding using Greedy Strategy C Language.
Algorithm:
Procedure Huffman(C): // C is the set of n characters and related information
n = C.size
Q = priority_queue()
for i = 1 to n
n = node(C[i])
Q.push(n)
end for
while Q.size() is not equal to 1
Z = new node()
Z.left = x = Q.pop
Z.right = y = Q.pop
Z.frequency = x.frequency + y.frequency
Q.push(Z)
end while
Return Q
Code:
// C program for Huffman Coding
#include <stdio.h>
#include <stdlib.h>
#define MAX_TREE_HT 100
// A Huffman tree node
struct MinHeapNode {
// One of the input characters
char data;
// Frequency of the character
unsigned freq;
// Left and right child of this node
struct MinHeapNode *left, *right;
};
// A Min Heap: Collection of
// min-heap (or Huffman tree) nodes
struct MinHeap {
// Current size of min heap
unsigned size;
// capacity of min heap
unsigned capacity;
// Array of minheap node pointers
struct MinHeapNode** array;
};
// min heap node with given character
// and frequency of the character
struct MinHeapNode* newNode(char data, unsigned freq)
{
struct MinHeapNode* temp = (struct MinHeapNode*)malloc(
sizeof(struct MinHeapNode));
temp->left = temp->right = NULL;
temp->data = data;
temp->freq = freq;
return temp;
}
// A utility function to create
// a min heap of given capacity
struct MinHeap* createMinHeap(unsigned capacity)
{
struct MinHeap* minHeap
= (struct MinHeap*)malloc(sizeof(struct MinHeap));
// current size is 0
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (struct MinHeapNode**)malloc(
minHeap->capacity * sizeof(struct MinHeapNode*));
return minHeap;
}
// A utility function to
// swap two min heap nodes
void swapMinHeapNode(struct MinHeapNode** a,
struct MinHeapNode** b)
struct MinHeapNode* t = *a;
*a = *b;
*b = t;
}
// The standard minHeapify function.
void minHeapify(struct MinHeap* minHeap, int idx)
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < minHeap->size
&& minHeap->array[left]->freq
< minHeap->array[smallest]->freq)
smallest = left;
if (right < minHeap->size
&& minHeap->array[right]->freq
< minHeap->array[smallest]->freq)
smallest = right;
if (smallest != idx) {
swapMinHeapNode(&minHeap->array[smallest],
&minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
// A utility function to check
// if size of heap is 1 or not
int isSizeOne(struct MinHeap* minHeap)
{
return (minHeap->size == 1);
}
// A standard function to extract
// minimum value node from heap
struct MinHeapNode* extractMin(struct MinHeap* minHeap)
struct MinHeapNode* temp = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}
// A utility function to insert
// a new node to Min Heap
void insertMinHeap(struct MinHeap* minHeap,
struct MinHeapNode* minHeapNode)
{
++minHeap->size;
int i = minHeap->size - 1;
while (i
&& minHeapNode->freq
< minHeap->array[(i - 1) / 2]->freq) {
minHeap->array[i] = minHeap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->array[i] = minHeapNode;
}
// A standard function to build min heap
void buildMinHeap(struct MinHeap* minHeap)
int n = minHeap->size - 1;
int i;
for (i = (n - 1) / 2; i >= 0; --i)
minHeapify(minHeap, i);
}
// A utility function to print an array of size n
void printArr(int arr[], int n)
{
int i;
for (i = 0; i < n; ++i)
printf("%d", arr[i]);
printf("\n");
}
// Utility function to check if this node is leaf
int isLeaf(struct MinHeapNode* root)
{
return !(root->left) && !(root->right);
}
// Creates a min heap of capacity
// equal to size and inserts all character of
// data[] in min heap. Initially size of
// min heap is equal to capacity
struct MinHeap* createAndBuildMinHeap(char data[],
int freq[], int size)
struct MinHeap* minHeap = createMinHeap(size);
for (int i = 0; i < size; ++i)
minHeap->array[i] = newNode(data[i], freq[i]);
minHeap->size = size;
buildMinHeap(minHeap);
return minHeap;
}
// The main function that builds Huffman tree
struct MinHeapNode* buildHuffmanTree(char data[],
int freq[], int size)
{
struct MinHeapNode *left, *right, *top;
// Step 1: Create a min heap of capacity
// equal to size. Initially, there are
// modes equal to size.
struct MinHeap* minHeap
= createAndBuildMinHeap(data, freq, size);
// Iterate while size of heap doesn't become 1
while (!isSizeOne(minHeap)) {
// Step 2: Extract the two minimum
// freq items from min heap
left = extractMin(minHeap);
right = extractMin(minHeap);
// Step 3: Create a new internal
// node with frequency equal to the
// sum of the two nodes frequencies.
// Make the two extracted node as
// left and right children of this new node.
// Add this node to the min heap
top = newNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
insertMinHeap(minHeap, top);
}
// Step 4: The remaining node is the
// root node and the tree is complete.
return extractMin(minHeap);
}
// Prints huffman codes from the root of Huffman Tree.
// It uses arr[] to store codes
void printCodes(struct MinHeapNode* root, int arr[],
int top)
// Assign 0 to left edge and recur
if (root->left) {
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
// Assign 1 to right edge and recur
if (root->right) {
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
// If this is a leaf node, then
// it contains one of the input
// characters, print the character
// and its code from arr[]
if (isLeaf(root)) {
printf("%c: ", root->data);
printArr(arr, top);
}
}
// The main function that builds a
// Huffman Tree and print codes by traversing
// the built Huffman Tree
void HuffmanCodes(char data[], int freq[], int size)
{
// Construct Huffman Tree
struct MinHeapNode* root
= buildHuffmanTree(data, freq, size);
// Print Huffman codes using
// the Huffman tree built above
int arr[MAX_TREE_HT], top = 0;
printCodes(root, arr, top);
}
int main()
{
char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
int freq[] = { 5, 9, 12, 13, 16, 45 };
int size = sizeof(arr) / sizeof(arr[0]);
HuffmanCodes(arr, freq, size);
return 0;
}
Program:
Execution:
Test Case 1:
Test Case :
Result:
Thus, we successfully verified and drove output using Huffman
Coding using Greedy Strategy C Language.
Dynamic Programming
A] Matrix Chain Multiplication
Aim:
To write the algorithm, code, screenshot, test cases (2) and the
result of the Matrix Chain Multiplication using Dynamic
Programming C Language.
Algorithm:
Begin
define table minMul of size n x n, initially fill with all 0s
for length := 2 to n, do
fir i:=1 to n-length, do
j := i + length – 1
minMul[i, j] := ∞
for k := i to j-1, do
q := minMul[i, k] + minMul[k+1, j] + array[i-1]*array[k]*array[j]
if q < minMul[i, j], then minMul[i, j] := q
done
done
done
return minMul[1, n-1]
End
Code:
#include <stdio.h>
#include<limits.h>
#define INFY 999999999
long int m[20][20];
int s[20][20];
int p[20],i,j,n;
void print_optimal(int i,int j)
{
if (i == j)
printf(" A%d ",i);
else
{
printf("( ");
print_optimal(i, s[i][j]);
print_optimal(s[i][j] + 1, j);
printf(" )");
}
}
void matmultiply(void)
{
long int q;
int k;
for(i=n;i>0;i--)
{
for(j=i;j<=n;j++)
{
if(i==j)
m[i][j]=0;
else
{
for(k=i;k<j;k++)
{
q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(q<m[i][j])
{
m[i][j]=q;
s[i][j]=k;
}
}
}
}
}
}
int MatrixChainOrder(int p[], int i, int j)
{
if(i == j)
return 0;
int k;
int min = INT_MAX;
int count;
for (k = i; k <j; k++)
{
count = MatrixChainOrder(p, i, k) +
MatrixChainOrder(p, k+1, j) +
p[i-1]*p[k]*p[j];
if (count < min)
min = count;
}
// Return minimum count
return min;
}
void main()
{
int k;
printf("Enter the no. of elements: ");
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
m[i][i]=0;
m[i][j]=INFY;
s[i][j]=0;
}
printf("\nEnter the dimensions: \n");
for(k=0;k<=n;k++)
{
printf("P%d: ",k);
scanf("%d",&p[k]);
}
matmultiply();
printf("\nCost Matrix M:\n");
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
printf("m[%d][%d]: %ld\n",i,j,m[i][j]);
i=1,j=n;
printf("\nMultiplication Sequence : ");
print_optimal(i,j);
printf("\nMinimum number of multiplications is : %d ",
MatrixChainOrder(p, 1, n));
}
Program:
Execution:
Test Case 1:
Test Case: 2
Result:
Thus, we successfully verified and drove output using Matrix
Chain Multiplication using Dynamic Programming C Language.
B] Longest Common Subsequence
Aim:
To write the algorithm, code, screenshot, test cases (2) and the
result of the Longest Common Subsequence using Dynamic
Programming C Language.
Algorithm:
X and Y be two given sequences
Initialize a table LCS of dimension X.length * Y.length
X.label = X
Y.label = Y
LCS[0][] = 0
LCS[][0] = 0
Start from LCS[1][1]
Compare X[i] and Y[j]
If X[i] = Y[j]
LCS[i][j] = 1 + LCS[i-1, j-1]
Point an arrow to LCS[i][j]
Else
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
Point an arrow to max(LCS[i-1][j], LCS[i][j-1])
Code:
#include<stdio.h>
#include<string.h>
int max(int a, int b);
void findLCS(char *X, char *Y, int XLen, int YLen);
int max(int a, int b) {
return (a > b)? a : b;
}
void findLCS(char *X, char *Y, int XLen, int YLen) {
int L[XLen + 1][YLen + 1];
int r, c, i;
/*
* find the length of the LCS
*/
for(r = 0; r <= XLen; r++) {
for(c = 0; c <= YLen; c++) {
if(r == 0 || c == 0) {
L[r][c] = 0;
} else if(X[r - 1] == Y[c - 1]) {
L[r][c] = L[r - 1][c - 1] + 1;
} else {
L[r][c] = max(L[r - 1][c], L[r][c - 1]);
}
}
}
/*
* Print LCS
*/
r = XLen;
c = YLen;
i = L[r][c];
char LCS[i+1];
/*
* setting the NULL character at the end of LCS character array.
* as we know in C programming language, NULL character is used
* to denote the end of a string
*/
LCS[i] = '\0';
while(r > 0 && c > 0) {
if(X[r - 1] == Y[c - 1]) {
LCS[i - 1] = X[r - 1];
i--;
r--;
c--;
} else if(L[r - 1][c] > L[r][c - 1]) {
r--;
} else {
c--;
//print result
printf("Length of the LCS: %d\n", L[XLen][YLen]);
printf("LCS: %s\n", LCS);
int q,w;
for (q=0;q<YLen;q++)
{
for (w=0;w<XLen;w++)
{
printf("%d ",L[q][w]);
}
printf ("\n");
}
}
int main(void) {
//the two sequences
char X[] = "ABCF";
char Y[] = "ABCDEF";
//length of the sequences
int XLen = strlen(X);
int YLen = strlen(Y);
findLCS(X, Y, XLen, YLen);
return 0;
}
Program:
Execution:
Test Case 1:
Test Case 2:
Result:
Thus, we successfully verified and drove output using Longest
Common Subsequence using Dynamic Programming C Language.
Divide And Conquer
A] Maximum Subarray
Aim:
To write the algorithm, code, screenshot, test cases (2) and the
result of the Maximum Subarray using Divide and Conquer C
Language.
Algorithm:
int maxSubarraySum ( int A [] , int n)
{
int max_sum = 0
for(i = 0 to n-1)
{
for(j = i to n-1)
{
int sum = 0
for(k = i to j)
sum = sum + A[k]
if(sum > max_sum)
max_sum = sum
}
}
return max_sum
}
Code:
#include <stdio.h>
#include <limits.h>
// Utility function to find the maximum of two numbers
int max(int x, int y) {
return (x > y) ? x : y;
}
// Function to find the maximum subarray sum using divide-and-conquer
int maximum_sum(int nums[], int low, int high)
{
// If the array contains 0 or 1 element
if (high <= low) {
return nums[low];
}
// Find the middle array element
int mid = (low + high) / 2;
// Find maximum subarray sum for the left subarray,
// including the middle element
int left_max = INT_MIN;
int sum = 0;
for (int i = mid; i >= low; i--)
{
sum += nums[i];
if (sum > left_max) {
left_max = sum;
}
}
// Find maximum subarray sum for the right subarray,
// excluding the middle element
int right_max = INT_MIN;
sum = 0; // reset sum to 0
for (int i = mid + 1; i <= high; i++)
{
sum += nums[i];
if (sum > right_max) {
right_max = sum;
}
}
// Recursively find the maximum subarray sum for the left
// and right subarray, and take maximum
int max_left_right = max(maximum_sum(nums, low, mid),
maximum_sum(nums, mid + 1, high));
// return the maximum of the three
return max(max_left_right, left_max + right_max);
}
int main(void)
{
int arr[] = { 2, -4, 1, 9, -6, 7, -3 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("The maximum sum of the subarray is %d",
maximum_sum(arr, 0, n - 1));
return 0;
}
Program:
Execution:
Test Case 1:
Test Case 2:
Result:
Thus, we successfully verified and drove output using Maximum
Subarray using Divide and Conquer C Language.
B] Karatsuba faster integer multiplication
Aim:
To write the algorithm, code, screenshot, test cases (2) and the
result of the Karatsuba faster integer multiplication using Divide
and Conquer C Language.
Algorithm:
procedure karatsuba(num1, num2)
if (num1 < 10) or (num2 < 10)
return num1*num2
*calculates the size of the numbers*
m = max(size_base10(num1), size_base10(num2))
m2 = m/2
*split the digit sequences about the middle*
high1, low1 = split_at(num1, m2)
high2, low2 = split_at(num2, m2)
*3 calls made to numbers approximately half the size*
z0 = karatsuba(low1, low2)
z1 = karatsuba((low1 + high1), (low2 + high2))
z2 = karatsuba(high1, high2)
return (z2 * 10 ^ (2 * m2)) + ((z1 - z2 - z0) * 10 ^ (m2)) + (z0)
Code:
// C++ implementation of Karatsuba algorithm for bit string multiplication.
#include<iostream>
#include<stdio.h>
using namespace std;
int makeEqualLength(string &str1, string &str2)
{
int len1 = str1.size();
int len2 = str2.size();
if (len1 < len2)
{
for (int i = 0 ; i < len2 - len1 ; i++)
str1 = '0' + str1;
return len2;
}
else if (len1 > len2)
{
for (int i = 0 ; i < len1 - len2 ; i++)
str2 = '0' + str2;
}
return len1; // If len1 >= len2
}
// The main function that adds two bit sequences and returns the addition
string addBitStrings( string first, string second )
{
string result; // To store the sum bits
// make the lengths same before adding
int length = makeEqualLength(first, second);
int carry = 0; // Initialize carry
// Add all bits one by one
for (int i = length-1 ; i >= 0 ; i--)
{
int firstBit = first.at(i) - '0';
int secondBit = second.at(i) - '0';
// boolean expression for sum of 3 bits
int sum = (firstBit ^ secondBit ^ carry)+'0';
result = (char)sum + result;
// boolean expression for 3-bit addition
carry = (firstBit&secondBit) | (secondBit&carry) | (firstBit&carry);
}
// if overflow, then add a leading 1
if (carry) result = '1' + result;
return result;
}
// A utility function to multiply single bits of strings a and b
int multiplyiSingleBit(string a, string b)
{ return (a[0] - '0')*(b[0] - '0'); }
// The main function that multiplies two bit strings X and Y and returns
// result as long integer
long int multiply(string X, string Y)
{
// Find the maximum of lengths of x and Y and make length
// of smaller string same as that of larger string
int n = makeEqualLength(X, Y);
// Base cases
if (n == 0) return 0;
if (n == 1) return multiplyiSingleBit(X, Y);
int fh = n/2; // First half of string, floor(n/2)
int sh = (n-fh); // Second half of string, ceil(n/2)
// Find the first half and second half of first string.
// Refer http://goo.gl/lLmgn for substr method
string Xl = X.substr(0, fh);
string Xr = X.substr(fh, sh);
// Find the first half and second half of second string
string Yl = Y.substr(0, fh);
string Yr = Y.substr(fh, sh);
// Recursively calculate the three products of inputs of size n/2
long int P1 = multiply(Xl, Yl);
long int P2 = multiply(Xr, Yr);
long int P3 = multiply(addBitStrings(Xl, Xr), addBitStrings(Yl, Yr));
// Combine the three products to get the final result.
return P1*(1<<(2*sh)) + (P3 - P1 - P2)*(1<<sh) + P2;
}
// Program to test above functions
int main()
{
printf ("%ld\n", multiply("1100", "1010"));
printf ("%ld\n", multiply("110", "1010"));
printf ("%ld\n", multiply("11", "1010"));
printf ("%ld\n", multiply("1", "1010"));
printf ("%ld\n", multiply("0", "1010"));
printf ("%ld\n", multiply("111", "111"));
printf ("%ld\n", multiply("11", "11"));
}
Program:
Execution:
Result:
Thus, we successfully verified and drove output using Karatsuba
faster integer multiplication using Divide and Conquer C
Language.
