MANAV RACHNA UNIVERSITY
SCHOOL OF ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE &
TECHNOLOGY
LAB FILE
ANALYSIS & DESIGN OF ALGORITHMS LAB
(CSH204BP)
Submitted to: Submitted by:
Ms. Babita Yadav Name: Khushboo Mehta
Assistant Roll No: 2K23CSUN01155
Professor MRU- Class: B. TECH CSE 6C
DoCST
MANAV RACHNA UNIVERSITY
SCHOOL OF ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE & TECHNOLOGY
INDEX
S. No. Lab Name Signature
1. Merge Sort
2. Heap Sort
3. Activity Selection
4. Job Scheduling with Deadline
5. Fractional Knapsack
6. 0/1 Knapsack
7. All-Pairs Shortest Path
8. Travelling Salesman Problem
9. Matrix Chain Multiplication
DIVIDE & CONQUER
1. MERGE SORT
OUTPUT
Time Complexity: O(n log n) (best, average, worst),Space Complexity: O(n)
2) HEAP SORT
OUTOUT
Time Complexity: O(n log n) (best, average, worst)
Space Complexity: O(1)
3) Greedy Algorithm
A)Activity Selection
1. Heap Sort
import [Link];
public class HeapSort {
public static void sort(int[]
arr) { int n = [Link];
for (int i = n / 2 - 1; i >= 0; i--)
{ heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
int temp =
arr[0]; arr[0] =
arr[i]; arr[i] =
temp;
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int
n, int i) { int largest = i; // Initialize
largest as root int left = 2 * i + 1; //
left child = 2*i + 1
int right = 2 * i + 2; // right child = 2*i + 2
// If left child is larger than root
if (left < n && arr[left] >
arr[largest]) { largest = left;
}
// If right child is larger than largest
so far if (right < n && arr[right] >
arr[largest]) {
largest = right;
}
// If largest is not
root if (largest != i)
{
int swap = arr[i];
arr[i] =
arr[largest];
arr[largest] =
swap;
// Recursively heapify the affected sub-
tree heapify(arr, n, largest);
}
}
public static void main(String[] args)
{ Random rand=new
Random();
[Link]("%-15s | %-20s | %-20s | %-20s \n", "Input Size (n)","Best
Case(ns)", "Average Case (ns)", "Worst Case (ns)");
[Link]("---------------------------------------------------------------------------------");
for(int
n=10;n<100000;n*=10){
int test=100;
long best=Long.MAX_VALUE;
long average=0;
long
worst=0;
while(test--
>0){
int arr[]=new int[n];
for(int i=0;i<n;i++){
arr[i]=[Link](100);
}
long startTime=[Link]();
sort(arr);
long endTime=[Link]();
long currentTime=endTime-startTime;
best=[Link](best,currentTime);
average+=currentTime;
worst=[Link](worst,currentTime);
}
average/=100;
[Link]("%-15d | %-20d | %-20d|%-20d\n", n, best,
average,worst);
}
}
Complexity: O(nlogn) across all cases.
2. Activity Selection
import [Link];
import
[Link];
import [Link];
public class ActivitySelection {
// Helper class to group an activity's start and finish
times static class Activity {
int start, finish;
public Activity(int start, int finish)
{ [Link] = start;
[Link] = finish;
}
}
// Function to calculate the maximum number of
activities public static int getMaxActivities(int[] start,
int[] finish, int n) {
Activity[] activities = new Activity[n];
// 1. Group the primitive arrays into
objects for (int i = 0; i < n; i++) {
activities[i] = new Activity(start[i], finish[i]);
}
// 2. Sort activities based on their finish time in
ascending order [Link](activities, new
Comparator<Activity>() {
@Override
public int compare(Activity a1, Activity
a2) { return [Link]([Link],
[Link]);
}
});
// 3. The first activity in the sorted array is always
selected int count = 1;
int lastSelectedFinishTime = activities[0].finish;
// 4. Greedily iterate through the remaining
activities for (int i = 1; i < n; i++) {
// If the current activity starts after or when the last one
finished, pick it if (activities[i].start >=
lastSelectedFinishTime) {
count++;
lastSelectedFinishTime = activities[i].finish;
}
}
return count;
}
public static void main(String[] args)
{ Random rand = new
Random();
[Link]("%-15s | %-20s | %-20s | %-20s \n", "Input Size (n)", "Best
Case(ns)", "Average Case (ns)", "Worst Case (ns)");
[Link]("---------------------------------------------------------------------------------");
for (int n = 10; n < 100000; n *=
10) { int test = 100;
long best = Long.MAX_VALUE;
long average = 0;
long worst = 0;
while (test-- > 0) {
int[] start = new
int[n]; int[] finish =
new int[n];
// Populating valid start and finish
times for (int i = 0; i < n; i++) {
start[i] = [Link](1000);
// Finish time must strictly be after start
time finish[i] = start[i] + [Link](500)
+ 1;
}
// Start timer
long startTime =
[Link]();
getMaxActivities(start, finish, n);
long endTime =
[Link]();
Complexity: O(nlogn) across all cases (assuming unsorted input).
3. Job Scheduling with Deadline
import [Link];
import
[Link];
import [Link];
public class JobScheduling {
static class Job {
int id, deadline, profit;
public Job(int id, int deadline, int
profit) { [Link] = id;
[Link] =
deadline; [Link] =
profit;
}
}
public static int scheduleJobs(int[] deadlines, int[] profits,
int n) { Job[] jobs = new Job[n];
int maxDeadline =
0; for (int i = 0; i <
n; i++) {
jobs[i] = new Job(i + 1, deadlines[i],
profits[i]); if (deadlines[i] >
maxDeadline) {
maxDeadline = deadlines[i];
}
}
[Link](jobs, new Comparator<Job>() {
@Override
public int compare(Job j1, Job j2) {
return [Link]([Link], [Link]);
}
});
boolean[] slot = new boolean[maxDeadline
+ 1]; int totalProfit = 0;
for (int i = 0; i < n; i++) {
// Find a free slot for this job (starting from the last possible slot)
// We greedily push it as close to its deadline as possible
for (int j = [Link](maxDeadline, jobs[i].deadline); j
> 0; j--) { if (!slot[j]) {
// Slot found!
slot[j] = true;
totalProfit +=
jobs[i].profit; break;
}
}
}
return totalProfit;
}
public static void main(String[]
args) { Random rand = new
Random();
[Link]("%-15s | %-20s | %-20s | %-20s \n", "Input Size (n)",
"Best Case(ns)", "Average Case (ns)", "Worst Case (ns)");
[Link]("---------------------------------------------------------------------------------");
// Note: Loop capped at 10,000 because O(n^2) gets extremely slow
beyond this for (int n = 10; n <= 10000; n *= 10) {
int test = 100;
long best =
Long.MAX_VALUE; long
average = 0;
long worst = 0;
while (test-- > 0) {
int[] deadlines = new
int[n]; int[] profits = new
int[n];
// Populating data
for (int i = 0; i < n; i++) {
profits[i] = [Link](100) + 1; // Profit up to 100
// Deadlines are spread out to create realistic slot collisions
deadlines[i] = [Link]([Link](1, n / 2)) + 1;
}
// Start timer
long startTime =
[Link]();
scheduleJobs(deadlines, profits, n);
long endTime =
[Link]();
long currentTime = endTime -
startTime; best = [Link](best,
currentTime); average +=
currentTime;
worst = [Link](worst, currentTime);
}
average /= 100;
Complexity: O(n2) in the average and worst cases (using the standard array implementation).
4. Fractional knapsack
import [Link];
import
[Link];
import [Link];
public class FractionalKnapsack {
// Helper class to store item
properties static class Item {
int value, weight;
Double ratio;
public Item(int value, int weight)
{ [Link] = value;
[Link] = weight;
[Link] = (double) value / weight;
}
}
// Function to calculate the maximum value we can get
public static double getMaxValue(int[] weights, int[] values, int
capacity) { int n = [Link];
Item[] items = new Item[n];
// 1. Populate the item
objects for (int i = 0; i < n;
i++) {
items[i] = new Item(values[i], weights[i]);
}
// 2. Sort items by value/weight ratio in descending
order [Link](items, new Comparator<Item>()
{
@Override
public int compare(Item o1, Item
o2) { return
[Link]([Link]);
}
});
double totalValue = 0d;
// 3. Greedily pick
items for (Item item :
items) {
if (capacity - [Link] >= 0) {
// Capacity permits adding the whole
item capacity -= [Link];
totalValue += [Link];
} else {
// Capacity cannot permit whole item, add the fractional
part double fraction = (double) capacity / [Link];
totalValue += ([Link] *
fraction); break; // The knapsack is
now exactly full
}
}
return totalValue;
}
public static void main(String[] args)
{ Random rand = new
Random();
[Link]("%-15s | %-20s | %-20s | %-20s \n", "Input Size (n)", "Best
Case(ns)", "Average Case (ns)", "Worst Case (ns)");
[Link]("---------------------------------------------------------------------------------");
for (int n = 10; n < 100000; n *=
10) { int test = 100;
long best = Long.MAX_VALUE;
long average = 0;
long worst = 0;
while (test-- > 0) {
int[] weights = new
int[n]; int[] values =
new int[n];
// Populating weights and
values for (int i = 0; i < n; i+
+) {
// +1 prevents a weight of 0 (which would cause division by
zero) weights[i] = [Link](100) + 1;
values[i] = [Link](100) + 1;
}
// Let capacity be roughly enough to hold half the
items int capacity = n * 25;
// Start timer
long startTime =
[Link]();
getMaxValue(weights, values,
capacity); long endTime =
[Link]();
long currentTime = endTime -
startTime; best = [Link](best,
currentTime); average +=
currentTime;
worst = [Link](worst, currentTime);
}
average /= 100;
Complexity: O(nlogn) across all cases.
5. Knapsack DP
import
[Link]; public
class Knapsack01 {
public static int knapsack(int capacity, int[] weights, int[]
values, int n) { int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
// We iterate backwards to ensure we don't pick the same
item twice for (int w = capacity; w >= weights[i]; w--) {
dp[w] = [Link](dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
public static void main(String[] args)
{ Random rand = new Random();
[Link]("%-15s | %-20s | %-20s | %-20s \n", "Input Size (n)", "Best Case(ns)",
"Average Case (ns)", "Worst Case (ns)");
[Link]("---------------------------------------------------------------------------------");
for (int n = 10; n <= 1000; n
*= 10) { int test = 100;
long best =
Long.MAX_VALUE; long
average = 0;
long worst = 0;
while (test-- > 0) {
int[] weights = new
int[n]; int[] values =
new int[n];
// Populating weights and
values for (int i = 0; i < n; i+
+) {
weights[i] = [Link](50) + 1; // Weights 1 to
50 values[i] = [Link](100) + 1; // Values 1 to
100
}
int capacity = n * 2;
// Start timer
long startTime =
[Link]();
knapsack(capacity, weights, values,
n); long endTime =
[Link]();
long currentTime = endTime -
startTime; best = [Link](best,
currentTime); average +=
currentTime;
worst = [Link](worst, currentTime);
}
average /= 100;
[Link]("%-15d | %-20d | %-20d|%-20d\n", n, best, average, worst);
}
}
}
Complexity: O(n×W) across all cases (where n is items, W is capacity).
6. All-Pairs Shortest Path
import [Link];
public class AllPairsShortestPath {
// A large value to represent infinity (no edge between nodes).
// We don't use Integer.MAX_VALUE to prevent integer overflow when adding
distances. final static int INF = 999999;
// Function to run the Floyd-Warshall
algorithm public static void
floydWarshall(int[][] graph, int V) {
int[][] dist = new int[V][V];
// 1. Initialize the solution matrix same as input graph
matrix for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
// 2. Add all vertices one by one to the set of intermediate
vertices. for (int k = 0; k < V; k++) {
// Pick all vertices as source one by
one for (int i = 0; i < V; i++) {
// Pick all vertices as destination for the above picked
source for (int j = 0; j < V; j++) {
// If vertex k is on the shortest path from i to j, then update
the value if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
public static void main(String[] args) {
Random rand = new Random();
[Link]("%-15s | %-20s | %-20s | %-20s \n", "Input Size (V)", "Best
Case(ns)", "Average Case (ns)", "Worst Case (ns)");
[Link]("---------------------------------------------------------------------------------");
// Note: V is the number of Vertices.
// Loop capped at 640 because O(V^3) gets extremely heavy
beyond this. for (int V = 10; V <= 640; V *= 2) {
int test = 10; // Reduced tests to 10 for larger matrices to
save time long best = Long.MAX_VALUE;
long average =
0; long worst = 0;
while (test-- > 0) {
int[][] graph = new int[V][V];
// Populating the adjacency matrix
randomly for (int i = 0; i < V; i++) {
for (int j = 0; j < V;
j++) { if (i == j) {
graph[i][j] = 0; // Distance to itself is 0
} else {
// 20% chance of NO direct edge (Infinity), otherwise
random weight if ([Link](5) == 0) {
graph[i][j] = INF;
} else {
graph[i][j] = [Link](100) + 1;
}
}
}
}
// Start timer
long startTime =
[Link]();
floydWarshall(graph, V);
long endTime = [Link]();
long currentTime = endTime -
startTime; best = [Link](best,
currentTime); average +=
currentTime;
worst = [Link](worst, currentTime);
}
average /= 10; // Averaged over 10 tests
[Link]("%-15d | %-20d | %-20d|%-20d\n", V, best, average, worst);
}
}
}
Complexity: O(V3) across all cases (where V is vertices).
7. Travelling Salesman Problem
import [Link];
import [Link];
public class TSPDynamicProgramming {
// A large value to represent
infinity final static int INF =
9999999;
// Top-down DP (Memoization) for TSP
// 'pos' is the current city.
// 'mask' is a binary sequence representing visited cities (e.g., 0101 means
cities 0 and 2 are visited)
public static int tsp(int[][] graph, int pos, int mask, int[][] memo, int n) {
// 1. Base Case: If all cities are visited
// (1 << n) - 1 creates a binary number with 'n' ones (e.g., for
n=3, it's 111) if (mask == (1 << n) - 1) {
// Return the cost to travel from the last city back to the
starting city (0) return graph[pos][0] == 0 ? INF : graph[pos]
[0];
}
// 2. Return memoized result if this state has already been
calculated if (memo[pos][mask] != -1) {
return memo[pos][mask];
}
int ans = INF;
// 3. Try visiting every other
city for (int city = 0; city < n;
city++) {
// Bitwise AND checks if the 'city' bit is currently 0
(unvisited) if ((mask & (1 << city)) == 0) {
// Recursively calculate the cost of visiting this new city
// Bitwise OR (mask | (1 << city)) sets the bit to 1, marking it as visited
int newCost = graph[pos][city] + tsp(graph, city, mask | (1 << city),
memo, n);
ans = [Link](ans, newCost);
}
}
// 4. Save the result in our DP table and
return return memo[pos][mask] = ans;
}
public static void main(String[] args)
{ Random rand = new Random();
[Link]("%-15s | %-20s | %-20s | %-20s \n", "Input Size (n)", "Best
Case(ns)", "Average Case (ns)", "Worst Case (ns)");
[Link]("---------------------------------------------------------------------------------");
// CAUTION: TSP DP is exponential.
// We step by 2 up to 16. Beyond N=18, it will crash due to
OutOfMemory! for (int n = 4; n <= 16; n += 1) {
int test = 10; // 10 tests per size is enough for exponential
algorithms long best = Long.MAX_VALUE;
long average =
0; long worst =
0;
while (test-- > 0) {
int[][] graph = new int[n][n];
// Populate adjacency matrix with random
distances for (int i = 0; i < n; i++) {
for (int j = 0; j < n;
j++) { if (i == j) {
graph[i][j] = 0;
} else {
graph[i][j] = [Link](100) + 1; // Distance 1 to 100
}
}
}
// DP Table initialization
// Rows = current city (n), Columns = visited state mask
(2^n) int[][] memo = new int[n][1 << n];
for (int[] row :
memo)
{ [Link](row, -
1);
}
// Start timer
long startTime = [Link]();
// Start at city 0. The mask is 1 (binary '00...01'), meaning city 0
is visited. tsp(graph, 0, 1, memo, n);
long endTime = [Link]();
long currentTime = endTime -
startTime; best = [Link](best,
currentTime); average +=
currentTime;
worst = [Link](worst, currentTime);
}
average /= 10;
[Link]("%-15d | %-20d | %-20d|%-20d\n", n, best, average, worst);
}
}
}
Complexity: O(n22n) across all cases.
8. Matrix Chain Multiplication
import [Link];
public class MatrixChainMultiplication {
// Function to find the minimum number of scalar multiplications needed
// p[] represents the dimensions of the matrices.
// Matrix A[i] has dimension p[i-1] x p[i]
public static int matrixChainOrder(int[] p, int n) {
// dp[i][j] = Minimum number of scalar multiplications needed
// to compute the matrix A[i]A[i+1]...A[j] = A[i..j] where
// dimension of A[i] is p[i-1] x
p[i] int[][] dp = new int[n][n];
// Cost is zero when multiplying one
matrix for (int i = 1; i < n; i++) {
dp[i][i] = 0;
}
// L is the chain length.
for (int L = 2; L < n;
L++) {
for (int i = 1; i < n - L + 1;
i++) { int j = i + L - 1;
// Prevent out of
bounds if (j == n)
continue;
dp[i][j] = Integer.MAX_VALUE;
// Try breaking the chain at every possible
position k for (int k = i; k <= j - 1; k++) {
// q = cost/scalar multiplications
int q = dp[i][k] + dp[k + 1][j] + p[i - 1] *
p[k] * p[j]; if (q < dp[i][j]) {
dp[i][j] = q;
}
}
}
}
return dp[1][n - 1];
}
public static void main(String[] args)
{ Random rand = new Random();
[Link]("%-15s | %-20s | %-20s | %-20s \n", "Input Size (n)", "Best
Case(ns)", "Average Case (ns)", "Worst Case (ns)");
[Link]("---------------------------------------------------------------------------------");
// Note: n is the size of the dimensions array.
// We cap the loop at 640 because O(n^3) gets incredibly heavy
beyond this. for (int n = 10; n <= 640; n *= 2) {
int test = 10; // 10 tests to smooth out the
data long best = Long.MAX_VALUE;
long average = 0;
long worst = 0;
while (test-- > 0) {
// Array to represent dimensions of n-1
matrices int[] p = new int[n];
// Populating the dimensions array
randomly for (int i = 0; i < n; i++) {
p[i] = [Link](100) + 1; // Dimensions between 1 and 100
}
// Start timer
long startTime =
[Link]();
matrixChainOrder(p, n);
long endTime = [Link]();
long currentTime = endTime -
startTime; best = [Link](best,
currentTime); average +=
currentTime;
worst = [Link](worst, currentTime);
}
average /= 10;
[Link]("%-15d | %-20d | %-20d|%-20d\n", n, best, average, worst);
}
}
}
Complexity: O(n3) across all cases.