Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
Thakur Shivkumarsingh Memorial
Engineering College, Burhanpur
Practical File
Analysis and Design of Algorithms
CS 402
Student Name
Roll no. Page 1
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
Submitted By: Submitted To:
Student Name Prof. Neha Koge
(roll no.) Asst. Professor TSEC
INDEX
[Link] Name of Experiment Date of Date of Page. No. Remark
Experiment Submission
01 Write a program for
Iterative and Recursive
Binary Search.
02 Write a program for
Merge Sort.
03 Write a program for
Quick Sort.
04 Write a program for
Optimal Merge
Patterns.
05 Write a program for
Huffman Coding.
06 Write a program for
Minimum Spanning
Trees using Prim’s
Algorithm.
07 Write a program for
KNAPSACK Problem.
Student Name
Roll no. Page 2
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
LAB-EXPERIMENT 01
AIM
Write a program for Iterative and Recursive Binary Search.
INTRODUCTION
Search a sorted array by repeatedly dividing the search interval in half. Begin with an
interval covering the whole array. If the value of the search key is less than the item
in the middle of the interval, narrow the interval to the lower half. Otherwise narrow
it to the upper half. Repeatedly check until the value is found or the interval is empty.
ALGORITHM
ITERATIVE ALGORITHM
int find (ArrayList list, Double target)
// Iterative binary search will return the index of the target element, else list
length
{
Boolean found = false;
int mid;
int first = 0;
int last = [Link]( ) - 1;
while (first <= last && !found)
{
mid = (first + last) / 2;
if ([Link](mid).equals(target))
found = true;
else if ([Link](mid) > target)
last = mid - 1;
else
first = mid + 1;
}
if (found)
return mid;
return -1;
}
Student Name
Roll no. Page 3
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
RECURSIVE ALGORITHM
int Find (ArrayList list, Double target, Double first, Double last)
// Recursive binary search will return the index of the target element, else list
length
{
int mid;
if (first > last)
return -1;
mid = (first + last) / 2;
if ([Link](mid).equals(target))
return mid;
if ([Link](mid) < target)
return find(list, target, mid+1, last);
return find(list, target, first, mid-1);
}
PROGRAM
Student Name
Roll no. Page 4
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
Student Name
Roll no. Page 5
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
OUTPUT
Student Name
Roll no. Page 6
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
LAB-EXPERIMENT 02
AIM
Write a program for Merge Sort.
INTRODUCTION
Merge sort is a sorting technique based on divide and conquer technique. With worst-
case time complexity being Ο(n log n), it is one of the most respected algorithms.
Merge sort first divides the array into equal halves and then combines them in a
sorted manner.
ALGORITHM
Steps:
1. If the list is of length 0 or 1, then it is already sorted. Otherwise
2. Divide the unsorted list into two sublists of about half the size
3. Sort each sublist recursively by re-applying merge sort.
4. Merge the two sublists back into one sorted list
MergeSort (arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
Student Name
Roll no. Page 7
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
PROGRAM
Student Name
Roll no. Page 8
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
Student Name
Roll no. Page 9
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
OUTPUT
Student Name
Roll no. Page 10
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
LAB-EXPERIMENT 03
AIM
Write a program for Quick Sort.
INTRODUCTION
Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element
as pivot and partitions the given array around the picked pivot. There are many
different versions of quickSort that pick pivot in different ways.
Always pick first element as pivot.
Always pick last element as pivot (implemented below)
Pick a random element as pivot.
Pick median as pivot.
The key process in quickSort is partition(). Target of partitions is, given an array and
an element x of array as pivot, put x at its correct position in sorted array and put all
smaller elements (smaller than x) before x, and put all greater elements (greater than
x) after x. All this should be done in linear time.
ALGORITHM
procedure
quicksort(array, left, right)
if right > left
select a pivot index //(e.g. pivotIndex := left+(right-left)/2)
pivotNewIndex := partition(array, left, right, pivotIndex)
quicksort(array, left, pivotNewIndex - 1)
quicksort(array, pivotNewIndex + 1, right)
function partition(array, left, right, pivotIndex)
pivotValue := array[pivotIndex]
swap array[pivotIndex] and array[right] // Move pivot to end
storeIndex := left
Student Name
Roll no. Page 11
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
for i from left to right - 1 // left = i < right
if array[i] = pivotValue
swap array[i] and array[storeIndex]
storeIndex := storeIndex + 1
swap array[storeIndex] and array[right] // Move pivot to its final place
return storeIndex
PROGRAM
Student Name
Roll no. Page 12
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
Student Name
Roll no. Page 13
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
OUTPUT
Student Name
Roll no. Page 14
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
LAB-EXPERIMENT 04
AIM
Write a program for Optimal Merge Patterns.
INTRODUCITON
ALGORITHM
At every stage we merge the files of the least length.
Steps:
Create a min heap of the set of elements.
While(heap has more than one element)
{
Delete a minimum element from the heap, and store it in min1;
Delete a minimum element from the heap, and store it in min2;
Create a node with the fields (info, left_link, right_ink);
Let [Link] = min1 + min2;
Let left_link.node = min1;
Let right_link_node = min2;
Insert node with valued info into the heap;
}
struct treenode {
struct treenode *lchild, *rchild;
int weight;
};
typedef struct treenode Type;
Type *Tree(int n)
// list is a global list of n single node
// binary trees as described above.
{
for (int i=1; i<n; i++) {
Type *pt = new Type;
// Get a new tree node.
pt -> lchild = Least(list); // Merge two trees with
pt -> rchild = Least(list); // smallest lengths.
Student Name
Roll no. Page 15
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
pt -> weight = (pt->lchild)->weight
+ (pt->rchild)->weight;
Insert(list, *pt);
}
return (Least(list)); // Tree left in l is the merge tree.
}
PROGRAM
Student Name
Roll no. Page 16
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
Student Name
Roll no. Page 17
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
OUTPUT
Student Name
Roll no. Page 18
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
LAB-EXPERIMENT 05
AIM
Write a program for Huffman Coding.
INTRODUCTION
Huffman coding is a lossless data compression algorithm. The idea is to assign
variable-length codes to input characters, lengths of the assigned codes are based on
the frequencies of corresponding characters. The most frequent character gets the
smallest code and the least frequent character gets the largest code.
The variable-length codes assigned to input characters are Prefix Codes, means the
codes (bit sequences) are assigned in such a way that the code assigned to one
character is not prefix of code assigned to any other character. This is how Huffman
Coding makes sure that there is no ambiguity when decoding the generated bit
stream.
ALGORITHM
1. Sort source outputs in decreasing order of their probabilities
2. Merge the two least-probable outputs into a single output whose probability is the
sum of the corresponding probabilities.
3. If the number of remaining outputs is more than 2, then go to step 1.
4. Arbitrarily assign 0 and 1 as codewords for the two remaining outputs.
5. If an output is the result of the merger of two outputs in a preceding step, append
the current codeword with a 0 and a 1 to obtain thecodeword the the preceding
outputs and repeat step 5. If no output ispreceded by another output in a preceding
step, then stop.
Student Name
Roll no. Page 19
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
PROGRAM
Student Name
Roll no. Page 20
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
Student Name
Roll no. Page 21
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
Student Name
Roll no. Page 22
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
Student Name
Roll no. Page 23
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
Student Name
Roll no. Page 24
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
OUTPUT
Student Name
Roll no. Page 25
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
Student Name
Roll no. Page 26
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
LAB-EXPERIMENT 06
AIM
Write a program for Minimum Spanning Trees using Prim’s algorithm.
INTRODUCTION
Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a
weighted undirected graph. This means it finds a subset of the edges that forms a tree
that includes every vertex, where the total weight of all the edges in the tree is
minimized. The algorithm operates by building this tree one vertex at a time, from an
arbitrary starting vertex, at each step adding the cheapest possible connection from
the tree to another vertex.
ALGORITHM
Given a connected graph G=(V,E) and a weight d:E->R+, find a minimum
spanning tree.
Prim's algorithm is known to be a good algorithm to find a
minimum spanning tree.
1. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V| = 1 then
stop, otherwise go to step 2.
2. For each v in V\Si, replace L(v) by min{L(v), dvui}. If L(v) is replaced, put a
label (L(v), ui) on v.
3. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
4. Let Si+1 = Si cup {ui+1}.
5. Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2
Student Name
Roll no. Page 27
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
PROGRAM
Student Name
Roll no. Page 28
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
OUTPUT
Student Name
Roll no. Page 29
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
LAB-EXPERIMENT 07
AIM
Write a program for KNAPSACK Problem.
INTRODUCTION
The knapsack problem or rucksack problem is a problem in combinatorial
optimization: Given a set of items, each with a weight and a value, determine the
number of each item to include in a collection so that the total weight is less than or
equal to a given limit and the total value is as large as possible. It derives its name
from the problem faced by someone who is constrained by a fixed-size knapsack and
must fill it with the most valuable items.
ALGORITHM
Here,
n=number of items
i = items
W=maximum weight
w=weight of item
v=value/profit of item
Xi=fractions of items i
Greedy_fractional_knapsack (w, v, W)
FOR i =1 to n
do x[i] =0
weight = 0
while weight < W
do i = best remaining item
IF weight + w[i] ≤ W
then x[i] = 1
weight = weight + w[i]
else
Student Name
Roll no. Page 30
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
x[i] = (w - weight) / w[i]
weight = W
return x
PROGRAM
Student Name
Roll no. Page 31
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
Student Name
Roll no. Page 32
Thakur Shivkumarsingh Memorial Engineering College,Burhanpur ADA[CS 402]
OUTPUT
Student Name
Roll no. Page 33