INDIRA GANDHI NATIONAL

OPEN UNIVERSITY

LABORATORY RECORD
Month &Year : ………………………………………………….….
Name : …………………………………………………………………
Study Center : 1402, SH College, Thevara, Kochi-13
Course : …………….……
Course Title : ………………………………………………………..…….….
…………………………………………………………..……..

Course Code: ……………………..

Enrolment No: ……………………………………………………………..……..

External Examiner Staff In-Charge

MCSL216 (PART I)
Ques 1:
Implement Fractional Knapsack algorithm and find out optimal result for the
problem instance given below:
(P1, P2, P3, P4, Ps) = (20, 30, 40, 32, 55) (W1, W2, W3, W4, Ws) = (5, 8, 10,
12, 15) Given Maximum Knapsack capacity = 20

Source Code

#include<stdio.h>
#include<stdlib.h>
int w[10], p[10], v[10][10], n, i, j, cap, x[10] = {0};
int max(int i, int j) {
return ((i > j) ? i : j);
}
int knap(int i, int j) {
int value;
if (v[i][j] < 0) {
if (j < w[i])
value = knap(i - 1, j);
else
value = max(knap(i - 1, j), p[i] + knap(i - 1, j - w[i]));
v[i][j] = value;
}
return v[i][j];
}

int main() {
int profit, count = 0;
printf("\nEnter the number of elements\n");
scanf("%d", &n);
printf("Enter the profit and weights of the elements\n");
for (i = 1; i <= n; i++) {
printf("For item no %d\n", i);
scanf("%d%d", &p[i], &w[i]);
}

printf("\nEnter the capacity \n");

scanf("%d", &cap);
for (i = 0; i <= n; i++)
for (j = 0; j <= cap; j++)
if ((i == 0) || (j == 0))
v[i][j] = 0;
else
v[i][j] = -1;

profit = knap(n, cap);

i = n;
j = cap;
while (j != 0 && i != 0) {
if (v[i][j] != v[i - 1][j]) {
x[i] = 1;
j = j - w[i];
i--;
} else
i--;
}

printf("Items included are\n");

printf("Sl.no\tweight\tprofit\n");
for (i = 1; i <= n; i++)
 if (x[i])
printf("%d\t%d\t%d\n", ++count, w[i], p[i]);
printf("Total profit = %d\n", profit);
// Clear the screen (Windows)
system("cls");
// Clear the screen (Unix-like)
// system("clear");
return 0;
}

Output
Ques 2
Implement multiplication of two matrices A[4, 4] and B[4, 4] and calculate
following: (i) How many times the innermost and the outermost loop will run?
(ii) Total number of multiplication and additions in computing the
multiplication of given matrices.

Source Code
#include<stdio.h>
int main()
{
int m, n, p, q, i, j, k;
int a[10][10], b[10][10], res[10][10];

printf("Enter the order of first matrix\n");

scanf("%d%d", & m, & n);
printf("Enter the order of second matrix\n");
scanf("%d%d", & p, & q);

if (n != p)
{
printf("Matrix is incompatible for multiplication\n");
}
else
{
printf("Enter the elements of Matrix-A:\n");
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", & a[i][j]);
}
}

printf("Enter the elements of Matrix-B:\n");

for (i = 0; i < p; i++)
{
for (j = 0; j < q; j++)
{
scanf("%d", & b[i][j]);
}
}
int outer=0,inner=0,count=0;
for (i = 0; i < m; i++)
{
outer++;
for (j = 0; j < q; j++)
{
res[i][j] = 0;
for (k = 0; k < p; k++)
{
res[i][j] += a[i][k] * b[k][j];
count++;
inner++;
}
}
}

printf("The product of the two matrices is:-\n");

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

{
for (j = 0; j < q; j++)
 {
printf("%d\t", res[i][j]);
}
printf("\n");
}
printf("Innermost loop:%d \n Outermost loop:%d \n Number of addition and
multiplication:%d",inner,outer,count);
}

return 0;
}

Output
Ques 3:
Implement Huffman's coding algorithm and run on the problem instance given
below:
Letters: A B I M S X Z
Frequency: 10 7 15 8 10 5 2

Source Code

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

class Huffman_Codes
{
struct New_Node
{
char data;
size_t freq;
New_Node* left;
New_Node* right;
New_Node(char data, size_t freq) : data(data),
freq(freq),
left(NULL),
right(NULL)
{}
~New_Node()
{
 delete left;
delete right;
}
};

struct compare
{
bool operator()(New_Node* l, New_Node* r)
{
return (l->freq > r->freq);
}
};

New_Node* top;

void print_Code(New_Node* root, string str)

{
if(root == NULL)
return;

if(root->data == '$')
{
print_Code(root->left, str + "0");
print_Code(root->right, str + "1");
}

if(root->data != '$')
{
cout << root->data <<" : " << str << "\n";
 print_Code(root->left, str + "0");
print_Code(root->right, str + "1");
}
}

public:
Huffman_Codes() {};
~Huffman_Codes()
{
delete top;
}
void Generate_Huffman_tree(vector<char>& data, vector<size_t>& freq, size_t size)
{
New_Node* left;
New_Node* right;
priority_queue<New_Node*, vector<New_Node*>, compare > minHeap;

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

{
minHeap.push(new New_Node(data[i], freq[i]));
}

while(minHeap.size() != 1)
{
left = minHeap.top();
minHeap.pop();

right = minHeap.top();
minHeap.pop();
 top = new New_Node('$', left->freq + right->freq);
top->left = left;
top->right = right;
minHeap.push(top);
}
print_Code(minHeap.top(), "");
}
};

int main()
{
int n, f;
char ch;
Huffman_Codes set1;
vector<char> data;
vector<size_t> freq;
cout<<"Enter the number of elements \n";
cin>>n;
cout<<"Enter the characters \n";

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

{
cin>>ch;
data.insert(data.end(), ch);
}
cout<<"Enter the frequencies \n";

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

{
cin>>f;
freq.insert(freq.end(), f);
 }
size_t size = data.size();
set1.Generate_Huffman_tree(data, freq, size);
return 0;
}

OUTPUT 3
Ques 4
Implement Selection sort algorithm to sort the following list of numbers
55, 25, 15, 40, 60, 35, 17, 65, 75, 10
Calculate the following:
(i) Number of exchange operations performed.
(ii) Number of times comparison operation performed.

Source Code

#include <stdio.h>
void selection_sort();
int a[30], n;
void main()
{
int i;
printf("\nEnter size of an array: ");
scanf("%d", &n);
printf("\nEnter elements of an array:\n");
for(i=0; i<n; i++)
scanf("%d", &a[i]);
selection_sort();
printf("\n\nAfter sorting:\n");
for(i=0; i<n; i++)
printf("\n%d", a[i]);
}
void selection_sort()
{
int i, j, min, temp;
int comp=0,swap=0;
for (i=0; i<n; i++)
 {
min = i;
for (j=i+1; j<n; j++)
{
comp=comp+1;
if (a[j] < a[min])
min = j;
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
swap=swap+1;
}
printf("Number of comparisons:%d \n Number of exchanges:%d",comp,swap);
}

OUTPUT 4
Ques 5
Examine implemented the performance of Quick soot algorithm on the set of
elements.
12 20 22 16 25 18 8 10 6 15
for the following list in terms of Comparisons, exchange operations and the
loop will iterate.

Source code
#include <stdio.h>
int scount = 0;
int count = 0;
// function to swap elements
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
scount++;
}

// function to find the partition position

int partition(int array[], int low, int high) {
// select the rightmost element as pivot
int pivot = array[high];
// pointer for the greater element
int i = low - 1;
// traverse each element of the array
// compare them with the pivot
for (int j = low; j < high; j++) {
count++;
if (array[j] <= pivot) {
// if an element smaller than the pivot is found
 // swap it with the greater element pointed by i
i++;
// swap element at i with element at j
swap(&array[i], &array[j]);
}
}

// swap the pivot element with the greater element at i

swap(&array[i + 1], &array[high]);
// return the partition point
return (i + 1);
}
void quickSort(int array[], int low, int high) {
count++;
if (low < high) {
// find the pivot element such that
// elements smaller than the pivot are on the left of the pivot
// elements greater than the pivot are on the right of the pivot
int pi = partition(array, low, high);

// recursive call on the left of pivot

quickSort(array, low, pi - 1);
// recursive call on the right of pivot
quickSort(array, pi + 1, high);
}
}

// function to print array elements

void printArray(int array[], int size) {
 for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// main function
int main() {
int data[50];
int n;
printf("Enter the number of elements\n");
scanf("%d", &n);
printf("Enter the elements of the array\n");
for (int i = 0; i < n; i++) {
scanf("%d", &data[i]);
}
printf("Unsorted Array\n");
printArray(data, n);

// perform quicksort on data

quickSort(data, 0, n - 1);
printf("Sorted array in ascending order: \n");
printArray(data, n);
printf("count of comparison:%d\n", count);
printf("count of swapping:%d\n", scount);

return 0;
}
OUTPUT 5
MCSL216 (PART II)
Ques 1:
Write a Javascript program to print current date and time
Source Code
<!DOCTYPE html>
<html>
<head></head>
<body>
<h1>Current Date & time</h1>
<p id="p1"></p>
<script>
var date = new Date();
document.getElementById("p1").innerHTML = date;
</script>
</body>
</html>

OUTPUT
Ques 2:
write a program to calculate addition subtraction multiplication and division
Source Code
<!doctype html>
<html>
<head>
<script>
var numOne, numTwo, res, temp;
function fun()
{
numOne = parseInt(document.getElementById("one").value);
numTwo = parseInt(document.getElementById("two").value);
if(numOne && numTwo)
{
temp = document.getElementById("res");
temp.style.display = "block"; res = numOne + numTwo;
document.getElementById("add").value = res; res = numOne - numTwo;
document.getElementById("subtract").value = res; res = numOne * numTwo;
document.getElementById("multiply").value = res; res = numOne / numTwo;
document.getElementById("divide").value = res;
}
}
</script>
</head>
<body>
<p id="input">Enter First Number: <input id="one"> <br/><br/>
Enter Second Number: <input id="two">
</p>
<p>
<button onclick="fun()">Add, Subtract, Multiply, Divide</button>
</p>
<p id="res" style="display:none;">
Addition Result = <input id="add"><br/><br/>
Subtraction Result = <input id="subtract"><br/><br/>
Multiplication Result = <input id="multiply"><br/><br/>
Division Result = <input id="divide">
</p>
</body>
</html>

OUTPUT
Question:3
Write a javascript code to change the contents of an element like header tag or
paragraph tag or division tag etc when user clicks on it.
Source Code
<!DOCTYPE html>
<html>
<head>
</head>
<body>
<h3> Javascript can change the content of an html element. </h3>
<p> Click the following text to see the effect. </p>
<p id = "para">Click me</p>
<script>
document.getElementById("para").onclick = function()
{
fun()
};
function fun()
{

document.getElementById("para").innerHTML = "Smile Please 😊";

document.getElementsByTagName("body")[0].style.color = "pink";
document.getElementsByTagName("body")[0].style.backgroundColor = "blue";
document.getElementsByTagName("body")[0].style.fontSize = "25px";
document.getElementById("para").style.border = "4px solid red";
}
</script>
</body>
</html>
OUTPUT
Question:4
Create a registration form with a attributes name, Password, email id, phone number and
validate and Username field as only having the Phone number Username the name characters,
validate e-mail-id and with a length of 10.

Source Code

<html>
<head>
<script>
function VALIDATION()
{
var name = document.forms.RegForm.Name.value;
var email = document.forms.RegForm.EMail.value;
var phone = document.forms.RegForm.Telephone.value;
var password = document.forms.RegForm.Password.value;
var uname =document.forms.RegForm.Uname.value;

//Javascript for Email Validation.

var regEmail= /^\w+([\.-]?\w+)*@\w+([\.-]?\w+)*(\.\w{2,3})+$/g;
// Javascript for Phone Number validation
var regPhone=/^\d{10}$/; .
var regName = /\d+$/g;
// Javascript for Name validation
var regUName = /\d+$/g;

if (name == "" || regName.test(name))

{
window.alert("Please enter your name properly.");
name.focus();
return false;
}
if (uname == "" || regUName.test(uname))
{
window.alert("Please enter your username properly.");
uname.focus();
return false;
}
if (email == "" || !regEmail.test(email))
{
window.alert("Please enter a valid e-mail address.");
email.focus();
return false;
}
if (password == "")
{
alert("Please enter your password");
password.focus();
return false;
}
if(password.length <6)
{
alert("Password should be atleast 6 character long");
password.focus();
return false;
}

if (phone == "" || !regPhone.test(phone))

{
alert("Please enter valid phone number.");
phone.focus();
return false;
}
 return true;
}
</script>

<style>
div {
box-sizing: border-box;
width: 100%;
border: 100px solid black;
float: left;
align-content: center;
align-items: center;
}

form {
margin: 0 auto;
width: 600px;
}
</style>
</head>
<body>
<h1 style="text-align: center;">REGISTRATION FORM</h1>
<form name="RegForm" onsubmit="return VALIDATION()" method="post">

<p>Name: <input type="text" size="65" name="Name" /></p>

<br />
<p>Username: <input type="text" size="65" name="Uname" />
</p>
<br />
<p>E-mail Address: <input type="text" size="65" name="EMail" /></p>
<br />
 <p>Password: <input type="text" size="65" name="Password" /></p>
<br />
<p>Telephone: <input type="text" size="65" name="Telephone" /></p>
<br />
<br />
<br />
<p>
<input type="submit" value="Register" name="Submit" />
<input type="reset" value="Reset" name="Reset" />
</p>

</form>
</body>
</html>

OUTPUT