int main() {
int n, key; cout << "Enter number
of elements: ";
cin >> n;
int arr[n]; cout << "Enter " << n <<
" elements: ";
for (int i = 0; i < n; i++)
{ cin >> arr[i];
}
// Sort the array before binary search
bubbleSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
{ cout << arr[i] << " ";
}
cout << endl;
cout << "Enter the element to search: ";
cin >> key;
int result = binarySearch(arr, 0, n - 1, key);
if (result != -1) cout << "Element found at index "
<< result << endl; else cout << "Element not
found" << endl;
return 0;
}
OUTPUT:
1
Program Code (for graph Plot):
2
EXPERIMENT 3
Date: 19th Aug 2025
Objective: Implement Knapsack Problem using Greedy Approach.
Software Used: C++, VS Code,
Theory: Knapsack Problem using Greedy Approach
The Knapsack Problem is a classic optimization problem in computer science and
operations research. It deals with selecting items, each having a weight and a profit (value),
to include in a knapsack of limited capacity such that the total profit is maximized.
There are different variants of the problem, the two main ones being:
1. 0/1 Knapsack Problem o An item can either be taken
completely or not at all.
o Solved using Dynamic Programming, not greedy.
2. Fractional Knapsack Problem o Items can be
divided; we can take fractions of an item.
o Solved efficiently using a Greedy Algorithm.
Greedy Approach
The greedy strategy works for the Fractional Knapsack Problem.
Steps:
1. Compute profit-to-weight ratio (value density) for each item.
Ratio=ProfitWeightRatio = \frac{Profit}{Weight}Ratio=WeightProfit
2. Sort items in descending order of profit-to-weight ratio.
3. Select items one by one:
o If the current item fits entirely in the knapsack → take it.
o Otherwise, take the fraction of the item that fits in the remaining capacity.
4. Repeat until the knapsack is full.
Why Greedy Works Here
• For the fractional knapsack, taking items with the highest value per unit weight
first always leads to an optimal solution.
• Unlike the 0/1 knapsack, the greedy choice property and optimal substructure hold
true here.
Applications
• Resource allocation problems.
• Budget management.
• Cargo loading and transport optimization.
• Job scheduling with deadlines.
3
Program:
4
Output:
5
Internal Assessment (Mandatory Experiment) Sheet for Lab Experinemt
Department of Computer Science & Engineering Amity
University, Noida (UP)
[Link] CSE
Programme Course Name ADA Lab
Data Science
Course Code CSE303 Semester 5th
A023167023102
Student Name Aryan Tomar Enrolment No.
Marking Criteria
Criteria Total Marks Marks Obtained Comments
Concept (A) 2
Implementation (B) 2
Performance (C) 2
Total 6
6
EXPERIMENT 4
Date: 12th Aug 2025
Objective: Implement 0/1 Knapsack Problem using Dynamic Programming method.
Software Used: C++, VS Code,
Theory
The 0/1 Knapsack Problem is a classic optimization problem in computer science and
operations research.
It is defined as:
• We are given n items, each with a weight (w[i]) and a value (v[i]).
• A knapsack has a maximum capacity (W).
• The objective is to maximize the total value of items included in the knapsack
without exceeding the capacity.
In the 0/1 knapsack, an item can either be:
• Taken (1) → included in the knapsack, or
• Not taken (0) → excluded from the knapsack.
No fractional inclusion is allowed.
Dynamic Programming Approach
Dynamic Programming (DP) is used because the problem has:
1. Overlapping subproblems – the same subproblems are solved multiple times.
2. Optimal substructure – the solution to the overall problem depends on solutions
to smaller subproblems.
DP State Definition
Let dp[i][w] represent the maximum value achievable with the first i items and knapsack
capacity w.
Recurrence Relation
For each item i (1 to n):
• If the item is not included: dp[i][w] = dp[i-1][w]
• If the item is included (only if w[i] ≤ w):
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])
So,
dp[i][w] = max( dp[i-1][w], value[i] + dp[i-1][w - weight[i]] )
Base Case
• If i = 0 (no items), or w = 0 (zero capacity),
then: dp[i][w] = 0
Algorithm Steps
1. Initialize a DP table of size (n+1) x (W+1).
2. Fill the table using the recurrence relation.
3. The final answer will be in dp[n][W].
7
Program:
Output:
8
Internal Assessment (Mandatory Experiment) Sheet for Lab Experinemt
Department of Computer Science & Engineering Amity
University, Noida (UP)
[Link] CSE
Programme Course Name ADA Lab
Data Science
Course Code CSE303 Semester 5th
Student Name Aryan Tomar Enrolment No. A023167023102
Marking Criteria
Criteria Total Marks Marks Obtained Comments
Concept (A) 2
Implementation (B) 2
Performance (C) 2
Total 6
9
EXPERIMENT 6(A)
Date: 26th Aug 2025
Objective: Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s
algorithm.
Software Used: C++,VS code
Theory:
A Spanning Tree of a connected, undirected, weighted graph is a subgraph that
includes all the vertices of the graph and a subset of the edges such that it forms a tree (no
cycles) and connects all vertices. Among all possible spanning trees, a Minimum Cost
Spanning Tree (MST) is the one where the sum of the edge weights is minimized.
There are two popular algorithms to find an MST: Prim’s Algorithm and Kruskal’s
Algorithm.
Prim’s Algorithm builds the MST step by step by starting from an arbitrary vertex and
growing the tree by repeatedly adding the smallest edge that connects a vertex in the tree to
a vertex outside the tree.
It always picks the edge with the minimum weight available at each step while avoiding
cycles.
Time Complexity: Using an adjacency matrix → O(V²)
Using Min-Heap/Priority Queue → O(E log V)
Prim’s Algorithm guarantees an optimal MST for connected, weighted, undirected graphs.
Algorithm:
Start with any vertex as the root of the MST.
1. Initialize all vertices as unselected, and set the cost of reaching each vertex
to infinity,
2. except the starting vertex which is set to 0.
3. Select the vertex with the minimum cost that is not yet included in the MST.
4. Add the selected vertex to the MST.
5. Update the cost of adjacent vertices if a smaller edge weight is found.
6. Repeat steps 3–5 until all vertices are included in the MST.
7. Output the edges chosen and the total minimum cost.
10
Program Code:
11
Output:
Input Graph:
Output graph:
12
EXPERIMENT 6(b)
Date: 26th Aug 2025
Objective: Find Minimum Cost Spanning Tree of a given undirected graph using khruskal’s
algorithm.
Software Used: C++, VS code
Theory:
A spanning tree of a connected, undirected graph is a subgraph that includes all the
vertices with minimum possible edges (V–1 edges if there are V vertices) andwithout
forming any cycle.
The Minimum Cost Spanning Tree (MST) is a spanning tree where the total weight of the
edges is minimum among all spanning [Link]’s Algorithm is a greedy algorithm used
to find an MST.
It works as follows:
1. Sort all edges in non-decreasing order of their weights.
2. Pick the smallest edge. Check if including this edge forms a cycle using
Disjoint Set Union (Union-Find).
Algorithm:
1. Sort edges by weight.
2. Initialize parent array for Union-Find.
3. For each edge (u, v, w) in sorted order:
4. If find(u) != find(v):
5. Include (u, v) in MST.
6. Union the sets of u and v.
7. Stop when MST contains (V–1) edges.
Time complexity:
1. Sorting edges → O(E log E)
2. Union-Find operations → O(E log V) (almost constant with
path compression
13
Program code:
14
Output:
15
Input graph:
Output Graph:
16
Internal Assessment (Mandatory Experiment) Sheet for Lab Experinemt
Department of Computer Science & Engineering Amity
University, Noida (UP)
[Link] CSE
Programme Course Name ADA Lab
Data Science
Course Code CSE303 Semester 5th
Student Name Aryan Tomar Enrolment No. A023167023102
Marking Criteria
Criteria Total Marks Marks Obtained Comments
Concept (A) 2
Implementation (B) 2
Performance (C) 2
Total 6
17
Experiment 7
Date: 2nd September 2025
Objective: From a given vertex in a weighted connected graph, find shortest paths to other
vertices using Dijkstra's algorithm.
Software Used: C++, VS Code
Software Used: C++, VS code
Theory:
Dijkstra’s algorithm is a greedy algorithm used to find the shortest path from a source
vertex to all other vertices in a weighted connected graph. The algorithm maintains a set of
vertices whose shortest distance from the source is known and repeatedly selects the vertex
with the smallest tentative distance, updates the distances of its neighbors, and continues
this process until all vertices have their shortest path finalized.
The algorithm works as follows:
1. Initialize distances from the source to all vertices as infinite, except for the
source which is initialized to 0.
2. Select the vertex with the minimum distance which has not been visited yet.
3. For the selected vertex, update the distance of its adjacent vertices if a shorter path
is found.
4. Repeat until all vertices have been visited and shortest distances finalized.
Algorithm:
1. Initialize distance array with infinity and distance[source] = 0.
2. Use a priority queue to select the vertex with the minimum distance.
3. While the queue is not empty:
o Extract vertex u with minimum distance.
o For each neighbour v of u:
If distance[u] + weight(u, v) < distance[v], update distance[v].
Output the shortest distances from the source to all vertices.
Time complexity:
1. Using a priority queue → O((V + E) log V), where
o V = number of vertices
o E = number of edges
2. Finding the minimum distance vertex → O(log V) per operation.
18
Program Code:
19
Output:
input graph:
output graph:
20
Internal Assessment (Mandatory Experiment) Sheet for Lab Experinemt
Department of Computer Science & Engineering Amity
University, Noida (UP)
[Link] CSE
Programme Course Name ADA Lab
Data Science
Course Code CSE303 Semester 5th
Student Name Aryan Tomar Enrolment No. A023167023102
Marking Criteria
Criteria Total Marks Marks Obtained Comments
Concept (A) 2
Implementation (B) 2
Performance (C) 2
Total 6
21