Design and Analysis of Algorithm Lab( PCS 409)

TERM WORK

Submitted in partial fulfillment of the requirement for the IV semester

[Link] CSE
By
Name of the Student – AdityaPandey
University Roll No – 2361030
Section - C
…
Under the Guidance of
Miss. Rashmi Deopa
Assistant Professor
Deptt. of CS&E

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

GRAPHIC ERA HILL UNIVERSITY, BHIMTAL CAMPUS
SATTAL ROAD, P.O. BHOWALI,
DISTRICT- NAINITAL-263132
2024 - 2025
 CERTIFICATE

The Term Work being submitted by Aditya Pandey Enrollment no PV-23610030 Roll no

2361030 to Graphic Era Hill University Bhimtal Campus for the award of bonafide work

carried out by her. She has worked under my guidance and supervision and fulfilled the

requirement for the submission of report.

(…………………) (……………………)

Concerned Faculty (HOD, CSE Dept.)

 INDEX

WK DATE NAME OF THE PROGRAM PAGE SIGN

NO. NO
1 1.1 Given an array of nonnegative integers, design a linear
algorithm and implement it using a program to find whether
given key element is present in the array or not. Also, find total
number of comparisons for each input case. (Time Complexity
= O(n), where n is the size of input)
1.2 Given an already sorted array of positive integers, design an
algorithm and implement it using a program to find whether
given key element is present in the array or not. Also, find total
number of comparisons for each input case. (Time Complexity
= O(nlogn), where n is the size of input).
1.3 Given an already sorted array of positive integers, design an
algorithm and implement it using a program to find whether a
given key element is present in the sorted array or not. For an
array arr[n], search at the indexes arr[0], arr[2],
arr[4], .... ,arr[2k] and so on. Once the interval (arr[2k] < key <
arr[ 2k+1] ) is found, perform a linear search operation from the
index 2k to find the element key. (Complexity < O(n), where n
is the number of elements need to be scanned for searching):
Jump Search
2 2.1 Given a sorted array of positive integers containing few
duplicate elements, design an algorithm and implement it using
a program to find whether the given key element is present in
the array or not. If present, then also find the number of copies
of given key. (Time Complexity = O(log n))
2.2 Given a sorted array of positive integers, design an algorithm
and implement it using a program to find three indices i, j, k
such that arr[i] + arr[j] = arr[k].
2.3 Given an array of nonnegative integers, design an algorithm and
a program to count the number of pairs of integers such that
their difference is equal to a given key, K.
3 3.1 Given an unsorted array of integers, design an algorithm and a
program to sort the array using insertion sort. Your program
should be able to find number of comparisons and shifts ( shifts
total number of times the array elements are shifted from their
place) required for sorting the array.
3.2 Given an unsorted array of integers, design an algorithm and
implement a program to sort this array using selection sort. Your
program should also find number of comparisons and number of
swaps required.
 3.3 Given an unsorted array of positive integers, design an
algorithm and implement it using a program to find whether
there are any duplicate elements in the array or not. (use sorting)
(Time Complexity = O(n log n))
4 4.1 Given an unsorted array of integers, design an algorithm and
implement it using a program to sort an array of elements by
dividing the array into two subarrays and combining these
subarrays after sorting each one of them. Your program should
also find number of comparisons and inversions during sorting
the array.
4.2 Given an unsorted array of integers, design an algorithm and
implement it using a program to sort an array of elements by
partitioning the array into two subarrays based on a pivot
element such that one of the sub array holds values smaller than
the pivot element while another sub array holds values greater
than the pivot element. Pivot element should be selected
randomly from the array. Your program should also find number
of comparisons and swaps required for sorting the array
4.3 Given an unsorted array of integers, design an algorithm and
implement it using a program to find Kth smallest or largest
element in the array. (Worst case Time Complexity = O(n))
5 5.1 Given an unsorted array of alphabets containing duplicate
elements. Design an algorithm and implement it using a
program to find which alphabet has maximum number of
occurrences and print it. (Time Complexity = O(n)) (Hint: Use
counting sort)
5.2 Given an unsorted array of integers, design an algorithm and
implement it using a program to find whether two elements exist
such that their sum is equal to the given key element. (Time
Complexity = O(n log n))
5.3 You have been given two sorted integer arrays of size m and n.
Design an algorithm and implement it using a program to find
list of elements which are common to both. (Time Complexity =
O(m+n))
6 6.1 Given a (directed/undirected) graph, design an algorithm and
implement it using a program to find if a path exists between
two given vertices or not. (Hint: use DFS)
6.2 Given a graph, design an algorithm and implement it using a
program to find if a graph is bipartite or not. (Hint: use BFS)
6.3 Given a directed graph, design an algorithm and implement it
using a program to find whether cycle exists in the graph or not.
7 7.1 After end term examination, Akshay wants to party with his
friends. All his friends are living as paying guest and it has been
decided to first gather at Akshay’s house and then move towards
party location. The problem is that no one knows the exact
address of his house in the city. Akshay as a computer science
 wizard knows how to apply his theory subjects in his real life
and came up with an amazing idea to help his friends. He draws
a graph by looking in to location of his house and his friends’
location (as a node in the graph) on a map. He wishes to find out
shortest distance and path covering that distance from each of
his friend’s location to his house and then whatsapp them this
path so that they can reach his house in minimum time. Akshay
has developed the program that implements Dijkstra’s algorithm
but not sure about correctness of results. Can you also
implement the same algorithm and verify the correctness of Aks
hay’s results? (Hint: Print shortest path and distance from
friends’ location to Akshay’s house)
7.2 Design an algorithm and implement it using a program to solve
previous question's problem using Bellman- Ford's shortest path
algorithm.
7.3 Given a directed graph with two vertices ( source and
destination). Design an algorithm and implement it using a
program to find the weight of the shortest path from source to
destination with exactly k edges on the path.

8 8.1 Assume that a project of road construction to connect some

cities is given to your friend. Map of these cities and roads
which will connect them (after construction) is provided to him
in the form of a graph. Certain amount of rupees is associated
with construction of each road. Your friend has to calculate the
minimum budget required for this project. The budget should be
designed in such a way that the cost of connecting the cities
should be minimum and number of roads required to connect all
the cities should be minimum (if there are N cities then only N-1
roads need to be constructed). He asks you for help. Now, you
have to help your friend by designing an algorithm which will
find minimum cost required to connect these cities. (use Prim's
algorithm)
8.2 Implement the previous problem using Kruskal's algorithm.
8.3 Assume that same road construction project is given to another
person. The amount he will earn from this project is directly
proportional to the budget of the project. This person is greedy,
so he decided to maximize the budget by constructing those
roads who have highest construction cost. Design an algorithm
and implement it using a program to find the maximum budget
required for the project.
9 9.1 Given a graph, Design an algorithm and implement it using a
program to implement Floyd Warshall all pair shortest path
algorithm.
9.2 Given a knapsack of maximum capacity w. N items are
provided, each having its own value and weight. You have to
 Design an algorithm and implement it using a program to find
the list of the selected items such that the final selected content
has weight w and has maximum value. You can take fractions of
items,i.e. the items can be broken into smaller pieces so that you
have to carry only a fraction xi of item i, where 0 ≤xi≤ 1.
9.3 Given an array of elements. Assume arr[i] represents the size of
file i. Write an algorithm and a program to merge all these files
into single file with minimum computation. For given two files
A and B with sizes m and n, computation cost of merging them
is O(m+n). (Hint: use greedy approach)
10 10.1Given a list of activities with their starting time and finishing
time. Your goal is to select maximum number of activities that
can be performed by a single person such that selected activities
must be non-conflicting. Any activity is said to be non-
conflicting if starting time of an activity is greater than or equal
to the finishing time of the other activity. Assume that a person
can only work on a single activity at a time.
10.2Given a long list of tasks. Each task takes specific time to
accomplish it and each task has a deadline associated with it.
You have to design an algorithm and implement it using a
program to find maximum number of tasks that can be
completed without crossing their deadlines and also find list of
selected tasks.
10.3Given an unsorted array of elements, design an algorithm and
implement it using a program to find whether majority element
exists or not. Also find median of the array. A majority element
is an element that appears more than n/2 times, where n is the
size of array.
11 11.1Given a sequence of matrices, write an algorithm to find most
efficient way to multiply these matrices together. To find the
optimal solution, you need to find the order in which these
matrices should be multiplied.
11.2Given a set of available types of coins. Let suppose you have
infinite supply of each type of coin. For a given value N, you
have to Design an algorithm and implement it using a program
to find number of ways in which these coins can be added to
make sum value equals to N.
11.3Given a set of elements, you have to partition the set into two
subsets such that the sum of elements in both subsets is same.
Design an algorithm and implement it using a program to solve
this problem.
12 12.1Given two sequences, Design an algorithm and implement it
using a program to find the length of longest subsequence
present in both of them. A subsequence is a sequence that
appears in the same relative order, but not necessarily
contiguous.
 12.2 Given a knapsack of maximum capacity w. N items are
provided, each having its own value and weight. Design an
algorithm and implement it using a program to find the list of
the selected items such that the final selected content has
weight <= w and has maximum value. Here, you cannot break
an item i.e. either pick the complete item or don't pick it. (0-1
property).
12.3 Given a string of characters, design an algorithm and
implement it using a program to print all possible permutations
of the string in lexicographic order.
13 13.1Given an array of characters, you have to find distinct
characters from this array. Design an algorithm and implement
it using a program to solve this problem using hashing. (Time
Complexity = O(n))
13.2Given an array of integers of size n, design an algorithm and
write a program to check whether this array contains duplicate
within a small window of size k < n.
13.3Given an array of nonnegative integers, Design an algorithm
and implement it using a program to find two pairs (a,b) and
(c,d) such that a*b = c*d, where a, b, c and d are distinct
elements of array.
14 14.1Given a number n, write an algorithm and a program to find
nth ugly number. Ugly numbers are those numbers whose only
prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9,
10, 12, 15, 16, 18, 20, 24, ..... is sequence of ugly numbers.
14.2Given a directed graph, write an algorithm and a program to
find mother vertex in a graph. A mother vertex is a vertex v
such that there exists a path from v to all other vertices of the
graph.
CHAPTER 1: Week 1
1.1 Given an array of nonnegative integers, design a linear algorithm and implement it using
a program to find whether given key element is present in the array or not. Also, find
total number of comparisons for each input case. (Time Complexity = O(n), where n is
the size of input)
Sample I/O Problem - 1:
Input: Output:
3 Present 6
8 Present 3
34 35 65 31 25 89 64 30 Not Present 6
89
5
977 354 244 546 355
244
6
23 64 13 67 43 56
63

1.1.1 Source Code:

#include<bits/stdc++.h>
using namespace std;
void LinearSearch(vector<int>arr,int key){
int i,cnt=0;
int n=[Link]();
for(i=0;i<=n-1;i++){
cnt++;
if(arr[i]==key){
cout<<"Present "<<cnt<<endl;
return;
}
}
cout<<"Not present"<<cnt<<endl;
}
int main(){
int t;
cin>>t;
while(t--){
int n,i,key;
cin>>n;
vector<int>arr(n);
for(i=0;i<n;i++){
cin>>arr[i];
}
cin>>key;
 LinearSearch(arr,key);
}
}
1.1.2 Output Screenshot:

1.2 Given an already sorted array of positive integers, design an algorithm and implement it
using a program to find whether given key element is present in the array or not. Also, find
total number of comparisons for each input case. (Time Complexity = O(nlogn), where n is
the size of input).
Sample I/O Problem - 2, 3:
Input: Output:
3 Present 3
5 Not Present 4
12 23 36 39 41 Present 3
41
8
21 39 40 45 51 54 68 72
69
10
101 246 438 561 796 896 899 4644 7999
8545
7999

1.2.1 Source Code:

#include<bits/stdc++.h>
using namespace std;
void BinarySearch(vector<int>arr,int key){
int i,cnt=0;
int n=[Link]();
int low=0,high=n-1;
while(low<=high){
 int mid=(low+high)/2;
cnt++;
if(arr[mid]==key){
cout<<"Present"<<cnt<<endl;
return;
}
else if(arr[mid]>key){
high=mid-1;
}
else{
low=mid+1;
}
}

cout<<"Not present"<<cnt<<endl;
}
int main(){
int t;
cin>>t;
while(t--){
int n,i,key;
cin>>n;
vector<int>arr(n);
for(i=0;i<n;i++){
cin>>arr[i];
}
cin>>key;
int cnt=0;
BinarySearch(arr,key);
}
}
1.2.2 Output Screenshot:
1.3 Given an already sorted array of positive integers, design an algorithm and implement it
using a program to find whether given key element is present in the array or not. Also, find
total number of comparisons for each input case. (Time Complexity = O(nlogn), where n is
the size of input).
Sample I/O Problem - 2, 3:
Input: Output:
3 Present 3
5 Not Present 4
12 23 36 39 41 Present 3
41
8
21 39 40 45 51 54 68 72
69
10
101 246 438 561 796 896 899 4644 7999 8545
7999

1.3.1 Source Code:

#include<bits/stdc++.h>
using namespace std;
void LinearSearch(vector<int>arr,int i,int j,int cnt,int key){
int ind;
int n=[Link]();
//if j is out of bound
j=(j>=n)?n-1:j;
for(ind=i;ind<=j;ind++){
if(arr[ind]==key){
cout<<"Present "<<cnt<<endl;
return;
}
}
cout<<"Not present"<<endl;
}
void JumpSearch(vector<int>arr,int key){
int i,cnt=0;
int n=[Link]();
for(i=0;i<n;i++){
int indi=pow(2,i-1);
int indj=pow(2,i-1+1);
cnt++;
//edge cases
if(indi>=n || arr[indi]>key){
cout<<"Not Present"<<endl;
return;
}
 //key found
if(arr[indi]==key){
cout<<"Present "<<cnt<<endl;
return;
}
//arr[indi]<key
else{
// arr[indi]<key<arr[indj]
if(indj>=n || arr[indj]>key){
LinearSearch(arr,indi+1,indj,cnt,key);
return;
}
}
}
cout<<"Not present"<<endl;
}
int main(){
int t;
cin>>t;
while(t--){
int n,i,key;
cin>>n;
vector<int>arr(n);
for(i=0;i<n;i++){
cin>>arr[i];
}
cin>>key;
JumpSearch(arr,key);
}
}
1.3.2 Output Screenshot:

CHAPTER 2: Week 2
2.1 Given a sorted array of positive integers containing few duplicate elements, design an
algorithm and implement it using a program to find whether the given key element is present
in the array or not. If present, then also find the number of copies of given key. (Time
Complexity = O(log n))
Sample I/O Problem I:
Input: Output:
2 981 - 2
10 75 - 3
235 235 278 278 763 764 790 853 981 981
981
15
1 2 2 3 3 5 5 5 25 75 75 75 97 97 97
75

2.1.1 Source Code:

#include <bits/stdc++.h>
using namespace std;
int floor(vector<int>arr, int target){
int n=[Link]();
int low=0;
int high=n-1;
int floor=-1;
while(low<=high){
int mid=(low+high)/2;
if(arr[mid]<=target){
if(arr[mid]==target)
floor=mid;
low=mid+1;
}
else{
high=mid-1;
}
}
return floor;
}
int ceil(vector<int>arr, int target){
int n=[Link]();
int low=0;
int high=n-1;
int ceil=-1;
while(low<=high){
int mid=(low+high)/2;
if(arr[mid]>=target){
if(arr[mid]==target)
 ceil=mid;
high=mid-1;
}
else{
low=mid+1;
}
}
return ceil;
}
int count(vector<int>arr, int target) {
int first=ceil(arr,target);
if(first==-1)
return 0;
int last=floor(arr,target);
return last-first+1;
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
int target;
cin>>target;
cout<<target<<" - "<<count(arr,target)<<endl;
}
return 0;
}
2.1.2 Output Screenshot:

2.2 Given a sorted array of positive integers, design an algorithm and implement it using a
program to find three indices i, j, k such that arr[i] + arr[j] = arr[k].
 Sample I/O Problem II:
Input: Output:
3 No sequence found.
5 2, 7, 8
1 5 84 209 341 1, 6, 9
10
24 28 48 71 86 89 92 120 194 201
15
64 69 82 95 99 107 113 141 171 350 369 400 511 590 666

2.2.1 Source Code:

#include<bits/stdc++.h>
using namespace std;
void find_triplet(vector<int>arr){
int n=[Link]();
int i,j,k;
i=0;
while(i<n){
j=i+1;
while(j<n){
k=j+1;
while(k<n){
if(arr[i]+arr[j]==arr[k]){
cout<<i+1<<" "<<j+1<<" "<<k+1<<endl;
return;
}
else if(arr[i]+arr[j]<arr[k]){
break;
}
else{
k++;
}
}
j++;
}
i++;
}

cout<<"No sequence found"<<endl;

}
int main(){
int t ;
cin>>t;
while(t--){
int n;
cin>>n;
 vector<int>arr(n);
for(int i = 0;i<n;i++){
cin>>arr[i];
}
find_triplet(arr);
}
return 0;
}
2.2.2 Output Screenshot:

2.3 Given an array of nonnegative integers, design an algorithm and a program to count the
number of pairs of integers such that their difference is equal to a given key, K.
Sample I/O Problem III:
Input: Output:
2 2
5 4
1 51 84 21 31
20
10
24 71 16 92 12 28 48 14 20 22
4

2.3.1 Source Code:

#include <bits/stdc++.h>
using namespace std;
int difference(vector<int>& arr, int k) {
int n = [Link]();
int c = 0;
sort([Link](), [Link]());
int left = 0;
int right = 1;
while (right < n) {
if (left == right) {
right++;
 continue;
}
int diff = arr[right] - arr[left];
if (diff == k) {
c++;
left++;
right++;
// Skip duplicates
while (left < n && arr[left] == arr[left - 1])
left++;
while (right < n && arr[right] == arr[right - 1])
right++;
}
else if (diff < k) {
right++;
}
else {
left++;
}
}
return c;
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int k;
cin >> k;
int c = difference(arr, k);
cout << c << endl;
}
return 0;
}
2.3.2 Output Screenshot:
 CHAPTER 3: Week 3

3.1 Given an unsorted array of integers, design an algorithm and a program to sort the array
using insertion sort. Your program should be able to find number of comparisons and
shifts ( shifts total number of times the array elements are shifted from their place)
required for sorting the array.
Sample I/O Problem I:
Input: Output:
3 -31 -23 32 45 46 65 76 89
8 comparisons = 13
-23 65 -31 76 46 89 45 32 shifts = 20
10 21 32 34 46 51 54 65 76 78 97
54 65 34 76 78 97 46 32 51 21 comparisons = 28
15 shifts = 37
63 42 223 645 652 31 324 22 553 -12 54 65 86 46 325 -12 22 31 42 46 54 63 65 86 223 324 325 553 645
652
comparisons = 54
shifts = 68
3.1.1 Source Code:
#include<bits/stdc++.h>
using namespace std;
void InsertionSort(vector<int>&arr,int &comp,int &shift){
int n=[Link]();
for(int i=1;i<n;i++){
int j=i-1;
int key=arr[i];
while(j>=0 && key<arr[j]){
arr[j+1]=arr[j];
shift++;
comp++;
j--;
}
arr[j+1]=key;
shift++;
}
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
 }
int comp=0,shift=0;
InsertionSort(arr,comp,shift);
for(auto it:arr){
cout<<it<<" ";
}
cout<<endl<<"Comparisons: "<<comp<<endl<<"Shifts:
"<<shift<<endl;
}
}
3.1.2 Output Screenshot:

3.2 Given an unsorted array of integers, design an algorithm and implement a program to sort
this array using selection sort. Your program should also find number of comparisons and
number of swaps required.
Sample I/O Problem II:
Input: Output:
3 21 -13 12 45 46 65 76 89
8 comparisons = 28
-13 65 -21 76 46 89 45 12 swaps = 7
10 21 32 34 46 51 54 65 76 78 97
54 65 34 76 78 97 46 32 51 21 comparisons = 45
15 swaps = 9
63 42 223 645 652 31 324 22 553 12 54 65 86 46 325 12 22 31 42 46 54 63 65 86 223 324 325 553 645
652
comparisons = 105
swaps = 14
3.2.1 Source Code:
#include<bits/stdc++.h>
using namespace std;
 void SelectionSort(vector<int>&arr,int &comp,int &swaps){
int n=[Link]();
for(int i=0;i<n-1;i++){
int mini=i;
for(int j=i+1;j<n;j++){
if(arr[j]<arr[mini]){
mini=j;
}
comp++;
}
swap(arr[i],arr[mini]);
swaps++;
}
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
int comp=0,swaps=0;
SelectionSort(arr,comp,swaps);
for(auto it:arr){
cout<<it<<" ";
}
cout<<endl<<"Comparisons: "<<comp<<endl<<"Swaps:
"<<swaps<<endl;
}
}
3.2.2 Output Screenshot:
 3.3 Given an unsorted array of positive integers, design an algorithm and implement it using
a program to find whether there are any duplicate elements in the array or not. (use
sorting) (Time Complexity = O(n log n))
Sample I/O Problem III:
Input: Output:
3 NO
5 YES
28 52 83 14 75 NO
10
75 65 1 65 2 6 86 2 75 8
15
75 35 86 57 98 23 73 1 64 8 11 90 61 19 20

3.3.1 Source Code:

#include<bits/stdc++.h>
using namespace std;
void Merge(vector<int>&arr,int low,int mid,int high){
int n=[Link]();
int i=low;
int j=mid+1;
vector<int>temp;
while(i<=mid && j<=high){
if(arr[i]<=arr[j]){
temp.push_back(arr[i]);
i++;
}
else{
temp.push_back(arr[j]);
j++;
}
}

while(i<=mid){
temp.push_back(arr[i]);
i++;
}
while(j<=high){
temp.push_back(arr[j]);
j++;
}
int k=low;
for(int i=0;i<[Link]();i++){
arr[k]=temp[i];
k++;
}
}
 void MergeSort(vector<int>&arr,int low,int high){
if (low>=high){
return;
}
int mid=(low+high)/2;
MergeSort(arr,low,mid);
MergeSort(arr,mid+1,high);
Merge(arr,low,mid,high);
}
bool duplicates(vector<int>arr){
int n=[Link]();
for(int i=0;i<n-1;i++){
if(arr[i]==arr[i+1]){
return true;
}
}
return false;
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
int comp=0,shift=0;
MergeSort(arr,0,n-1);
if(duplicates(arr)){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}

}
}

3.3.2 Output Screenshot:

 CHAPTER 4: Week 4

4.1 Given an unsorted array of integers, design an algorithm and implement it using a program to
sort an array of elements by dividing the array into two subarrays and combining these
subarrays after sorting each one of them. Your program should also find number of
comparisons and inversions during sorting the array.
Sample I/O Problem I:
Input: Output:
3 21 23 32 45 46 65 76 89
8 comparisons = 16
23 65 21 76 46 89 45 32 inversions = 13
10 21 32 34 46 51 54 65 76 78 97
54 65 34 76 78 97 46 32 51 21 comparisons = 22
15 inversions = 28
63 42 223 645 652 31 324 22 553 12 54 65 86 46 325 12 22 31 42 46 54 63 65 86 223 324 325 553 645 652
comparisons = 43
inversions =54

4.1.1 Source Code:

#include<bits/stdc++.h>
using namespace std;
void Merge(vector<int>&arr,int low,int mid,int high,int &comp,int
&inv){
int i=low,j=mid+1;
vector<int>temp;
while(i<=mid && j<=high){
if(arr[i]<=arr[j]){
temp.push_back(arr[i]);
comp++;
i++;
}
else{
temp.push_back(arr[j]);
comp++;
j++;
inv+=(mid-i+1);
}
}
while(i<=mid){
temp.push_back(arr[i]);
i++;
}
while(j<=high){
temp.push_back(arr[j]);
j++;
 }
j=low;
for(int i=0;i<[Link]();i++){
arr[j]=temp[i];
j++;
}
}
void MergeSort(vector<int>&arr,int low,int high,int &comp,int
&inv){
if (low>=high){
return;
}
int mid=(low+high)/2;
MergeSort(arr,low,mid,comp,inv);
MergeSort(arr,mid+1,high,comp,inv);
Merge(arr,low,mid,high,comp,inv);
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
int comp=0,inv=0;
MergeSort(arr,0,n-1,comp,inv);
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
cout<<endl<<"Comparisons: "<<comp<<endl<<"Inversions:
"<<inv<<endl;
}
}
4.1.2 Output
Screenshot:
 4.2 Given an unsorted array of integers, design an algorithm and implement it using a program to
sort an array of elements by partitioning the array into two subarrays based on a pivot
element such that one of the sub array holds values smaller than the pivot element while
another sub array holds values greater than the pivot element. Pivot element should be
selected randomly from the array. Your program should also find number of comparisons and
swaps required for sorting the array.
Sample I/O Problem II:
Input: Output:
3 21 23 32 45 46 65 76 89
8 comparisons = 14
23 65 21 76 46 89 45 32 swaps = 10
10 21 32 34 46 51 54 65 76 78 97
54 65 34 76 78 97 46 32 51 21 comparisons = 29
15 swaps = 21
63 42 223 645 652 31 324 22 553 12 54 65 86 46 325 12 22 31 42 46 54 63 65 86 223 324 325 553 645
652
comparisons = 45
swaps = 39

4.2.1 Source Code:

#include<bits/stdc++.h>
using namespace std;
int partition(vector<int>&arr,int low,int high,int &comp,int
&swaps){
int pivot=arr[high];
int i=low-1;
for(int j=low;j<high;j++){
if(arr[j]<=pivot){
i++;
swap(arr[i],arr[j]);
swaps++;
}
comp++;
}
swap(arr[high],arr[i+1]);
swaps++;
return i+1;
}
void QuickSort(vector<int>&arr,int low,int high,int &comp,int
&swaps){
if (low>=high){
return;
}
int p_index=partition(arr,low,high,comp,swaps);
QuickSort(arr,low,p_index-1,comp,swaps);
QuickSort(arr,p_index+1,high,comp,swaps);
 }
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
int comp=0,swaps=0;
QuickSort(arr,0,n-1,comp,swaps);
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
cout<<endl<<"Comparisons: "<<comp<<endl<<"Swaps:
"<<swaps<<endl;
}
}
4.2.2 Output Screenshot:

4.3 Given an unsorted array of integers, design an algorithm and implement it using a program to
find Kth smallest or largest element in the array. (Worst case Time Complexity = O(n))
Sample I/O Problem III:
Input: Output:
3 123
10 78
123 656 54 765 344 514 765 34 765 234
3
15
43 64 13 78 864 346 786 456 21 19 8 434 76 270 601
8

4.3.1 Source Code:

#include<bits/stdc++.h>
using namespace std;
int partition(vector<int>&arr,int low,int high){
int pivot=arr[high];
int i=low-1;
for(int j=low;j<high;j++){
if(arr[j]<=pivot){
i++;
swap(arr[i],arr[j]);
}
}
swap(arr[high],arr[i+1]);
return i+1;
}
int findKth(vector<int>&arr,int low,int high,int k){
if (low>high){
return -1;
}
int p_index=partition(arr,low,high);
if (k-1 > p_index)
return findKth(arr,p_index+1,high,k);
else if (k-1 < p_index)
return findKth(arr,low,p_index-1,k);
else
return arr[p_index];
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int>arr(n);
 for(int i=0;i<n;i++){
cin>>arr[i];
}
int k;
cin>>k;
int ans=findKth(arr,0,n-1,k);
cout<<ans<<endl;
}
}
4.3.2 Output Screenshot:
 CHAPTER 5: Week 5

5.1 Given an unsorted array of alphabets containing duplicate elements. Design an algorithm and
implement it using a program to find which alphabet has maximum number of occurrences
and print it. (Time Complexity = O(n)) (Hint: Use counting sort)
Sample I/O Problem I:
Input: Output:
3 a–3
10 No Duplicates Present
aedwadqafp l-4
15
rkpgv yumqadjcze
20
gtlltcwawglcwdsaavcl

5.1.1 Source Code:

#include<bits/stdc++.h>
using namespace std;
void max_occurrence(vector<char>str){
int hash[256]={0};
for(int i=0;i<[Link]();i++){
hash[str[i]]++;
}
int max_occ=1;//1 occurrence is minimum as we need duplicates
char alpha;
for(int i=0;i<256;i++){
if(hash[i]>max_occ){
max_occ=hash[i];
alpha=char(i);
}
}
if(max_occ==1){
cout<<"No duplicates present"<<endl;
}
else{
cout<<alpha<<" - "<<max_occ<<endl;
}
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<char> str(n);
 for(int i=0;i<n;i++){
cin>>str[i];
}
max_occurrence(str);
}
}
5.1.2 Output Screenshot:

5.2 Given an unsorted array of integers, design an algorithm and implement it using a program to
find whether two elements exist such that their sum is equal to the given key element. (Time
Complexity = O(n log n)).
Sample I/O Problem II:
Input: Output:
2 10 40
10 No Such Element Exist
64 28 97 40 12 72 84 24 38 10
50
15
56 10 72 91 29 3 41 45 61 20 11 39 9 12 94
302
5.2.1 Source Code:
#include<bits/stdc++.h>
using namespace std;
void sum_of_two(vector<int>arr,int key){
sort([Link](),[Link]());
int n=[Link]();
int left=0,right=n-1;
while(left<right){
if(arr[left]+arr[right]>key){
right--;
}
else if(arr[left]+arr[right]<key){
left++;
}
else{
cout<<arr[left]<<" "<<arr[right]<<endl;
 return;
}
}
cout<<"No such element exist"<<endl;
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int> arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
int key;
cin>>key;
sum_of_two(arr,key);
}
}
5.2.2 Output Screenshot:

5.3 You have been given two sorted integer arrays of size m and n. Design an algorithm and
implement it using a program to find list of elements which are common to both. (Time
Complexity = O(m+n))
Sample I/O Problem III:
Input: Output:
7 10 10 34 55
34 76 10 39 85 10 55
12
30 55 34 72 10 34 10 89 11 30 69 51
5.3.1 Source Code:
#include<bits/stdc++.h>
using namespace std;
void intersection(vector<int>A,vector<int>B){
int i=0,j=0;
int m=[Link](),n=[Link]();
 vector<int>ans;
while(i<m && j<n){
if(A[i]==B[j]){
ans.push_back(A[i]);
i++;
j++;
}
else if(A[i]<B[j]){
i++;
}
else{
j++;
}
}
for(auto it:ans){
cout<<it<<" ";
}
}
int main(){
int m,n;
cin>>m;
vector<int> A(m);
for(int i=0;i<m;i++){
cin>>A[i];
}
cin>>n;
vector<int> B(n);
for(int i=0;i<n;i++){
cin>>B[i];
}
sort([Link](),[Link]());
sort([Link](),[Link]());
intersection(A,B);

}
5.3.2 Output Screenshot:
 CHAPTER 6: Week 6

6.1 Given a (directed/undirected) graph, design an algorithm and implement it using a program
to find if a path exists between two given vertices or not. (Hint: use DFS)
Sample I/O Problem I:
Input: Output:
5 Yes Path Exists
01100
10111
11010
01101
01010
15
6.1.1 Source Code:
#include<bits/stdc++.h>
using namespace std;
bool DFS(vector<vector<int> >&adj,int src,int dest,int vis[]){
int n=[Link]();
if(src==dest)
return true;
vis[src]=1;
for(int i=0;i<n;i++ ){
if(!vis[i] && adj[src][i]==1){
if(DFS(adj,i,dest,vis))
return true;
}
}
return false;
}
int main(){
int n;
cin>>n;
vector<vector<int> >adj(n,vector<int>(n,0));
int u,v,src,dest;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
cin>>adj[i][j];
}
cin>>src>>dest;
int vis[n]={0};
if(DFS(adj,src,dest,vis)){
cout<<"Yes Path Exists.";
}
else{
cout<<"No Such Path Exists";
 }
return 0;
}
6.1.2 Output Screenshot:

6.2 Given a graph, design an algorithm and implement it using a program to find if a graph is
bipartite or not. (Hint: use BFS)
Sample I/O Problem II:
Input: Output:
5 Not Bipartite
01100
10111
11010
01101
01010
6.2.1 Source Code:
#include <bits/stdc++.h>
using namespace std;
bool DFS(int node, int col, vector<int> &color, vector< vector<
int > > &adj) {
color[node] = col;
for (int neighbor : adj[node]) {
if (color[neighbor] == -1) {
if (!DFS(neighbor, !col, color, adj)) {
return false;
}
} else if (color[neighbor] == col) {
return false;
}
}
return true;
}
int main() {
int n;
cin >> n;
vector<vector<int>> adjMatrix(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
 cin >> adjMatrix[i][j];
}
}
// Convert adjacency matrix to adjacency list
vector<vector<int>> adj(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (adjMatrix[i][j] == 1) {
adj[i].push_back(j);
}
}
}
vector<int> color(n, -1);
for (int i = 0; i < n; ++i) {
if (color[i] == -1) {
if (!DFS(i, 0, color, adj)) {
cout << "Not Bipartite.\n";
return 0;
}
}
}
cout << "Yes Bipartite.\n";
return 0;
}
6.2.2 Output Screenshot:

6.3 Given a directed graph, design an algorithm and implement it using a program to find
whether cycle exists in the graph or not.
Sample I/O Problem III:
Input: Output:
5 No Cycle Exists
01100
00011
01010
00001
00000
6.3.1 Source Code:
#include<bits/stdc++.h>
using namespace std;
bool DFS(int node,vector<vector<int> > &adj, int vis[],int
pathVis[] ) {
vis[node]=1;
pathVis[node]=1;
for(int it: adj[node]){
if(!vis[it]){
//not visited check for cycle
if(DFS(it,adj,vis,pathVis)){
return true;
}
}
//visited and path visited also
else if(pathVis[it]){
return true;
}
}
pathVis[node]=0;
return false;
}
int main(){
int n;
cin >> n;
vector<vector<int>> adjMatrix(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> adjMatrix[i][j];
}
}
// Convert adjacency matrix to adjacency list
vector<vector<int>> adj(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (adjMatrix[i][j] == 1) {
adj[i].push_back(j);
}
}
}
int vis[n]={0};
int pathVis[n]={0};
for(int i=0;i<n;i++){
if(!vis[i]){
if(DFS(i,adj,vis,pathVis)){
cout<<"Yes Cycle exists.";
 return 0;
}
}
}
cout<<"No cycle exists.";
return 0;
}
6.3.2 Output Screenshot:
 CHAPTER 7: Week 7

7.1 After end term examination, Akshay wants to party with his friends. All his friends are
living as paying guest and it has been decided to first gather at Akshay’s house and then
move towards party location. The problem is that no one knows the exact address of his
house in the city. Akshay as a computer science wizard knows how to apply his theory
subjects in his real life and came up with an amazing idea to help his friends. He draws a
graph by looking in to location of his house and his friends’ location (as a node in the
graph) on a map. He wishes to find out shortest distance and path covering that distance
from each of his friend’s location to his house and then whatsapp them this path so that
they can reach his house in minimum time. Akshay has developed the program that
implements Dijkstra’s algorithm but not sure about correctness of results. Can you also
implement the same algorithm and verify the correctness of Akshay’s results? (Hint: Print
shortest path and distance from friends’ location to Akshay’s house).
Sample I/O Problem I & II:
Input: Output:
5 1:0
04100 1:32:3
00004 1:3:1
02040 1:34:5
00004 1:325:7
00000
1
7.1.1 Source Code:
#include <bits\stdc++.h>
using namespace std;
typedef pair<int, int> pii; // {distance, vertex}
void printPath(vector<int>& parent, int vertex, int source) {
if (vertex == source) {
cout << source + 1 << " : ";
return;
}
printPath(parent, parent[vertex], source);
cout << vertex + 1 << " ";
}
void dijkstra(vector<vector<pii>>& graph, int V, int source) {
vector<int> dist(V, INT_MAX);
vector<int> parent(V, -1);
priority_queue<pii, vector<pii>, greater<pii>> pq; // min-
heap
dist[source] = 0;
[Link]({0, source});
while (![Link]()) {
int u = [Link]().second;
int current_dist = [Link]().first;
 [Link]();
if (current_dist > dist[u]) continue; // Skip if a
shorter path is already found
for (auto& edge : graph[u]) {
int v = [Link];
int weight = [Link];

if (dist[u] + weight < dist[v]) {

dist[v] = dist[u] + weight;
parent[v] = u;
[Link]({dist[v], v});
}
}
}
// Print the shortest paths
for (int i = 0; i < V; ++i) {
if (i == source) {
cout << source + 1 << " : 0" << endl;
continue;
}
if (dist[i] == INT_MAX) {
cout << "No path from " << source + 1 << " to " << i
+ 1 << endl;
continue;
}
printPath(parent, i, source);
cout << ": " << dist[i] << endl;
}
}
int main() {
int V;
cin >> V;
vector<vector<pii>> graph(V);
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
int weight;
cin >> weight;
if (weight != 0) {
graph[i].push_back({j, weight});
}
}
}
int source;
cin >> source;
source--; // converting to 0-based index
dijkstra(graph, V, source);
 return 0;
}
7.1.2 Output Screenshot:

7.2 Design an algorithm and implement it using a program to solve previous question's
problem using Bellman- Ford's shortest path algorithm.
7.2.1 Source Code:
#include <bits\stdc++.h>
using namespace std;
struct Edge {
int src, dest, weight;
};
void printPath(vector<int>& parent, int vertex, int source) {
if (vertex == source) {
cout << source + 1 << " : ";
return;
}
printPath(parent, parent[vertex], source);
cout << vertex + 1 << " ";
}
void bellmanFord(vector<Edge>& edges, int V, int E, int source) {
vector<int> dist(V, INT_MAX);
vector<int> parent(V, -1);
dist[source] = 0;
for (int i = 1; i <= V - 1; ++i) {
for (int j = 0; j < E; ++j) {
int u = edges[j].src;
int v = edges[j].dest;
int weight = edges[j].weight;
 if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
{
dist[v] = dist[u] + weight;
parent[v] = u;
}
}
}
// Check for negative-weight cycles
for (int i = 0; i < E; ++i) {
int u = edges[i].src;
int v = edges[i].dest;
int weight = edges[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
cout << "Graph contains negative weight cycle" << endl;
return;
}
}
// Print the shortest paths
for (int i = 0; i < V; ++i) {
if (i == source) {
cout << source + 1 << " : 0" << endl;
continue;
}
if (dist[i] == INT_MAX) {
cout << "No path from " << source + 1 << " to " << i + 1 << endl;
continue;
}
printPath(parent, i, source);
cout << ": " << dist[i] << endl;
}
}
int main() {
int V;
cin >> V;
vector<Edge> edges;
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
int weight;
cin >> weight;
if (weight != 0) {
edges.push_back({i, j, weight});
}
}
}
int source;
cin >> source;
 source--; // converting to 0-based index
int E = [Link]();
bellmanFord(edges, V, E, source);
return 0;
}
7.2.2 Output Screenshot:

7.3 Given a directed graph with two vertices ( source and destination). Design an algorithm
and implement it using a program to find the weight of the shortest path from source to
destination with exactly k edges on the path.
Sample I/O Problem III:
Input: Output:
4 Weight of shortest path from (1,4) with 2 edges : 9
0 10 3 2
0007
0006
0000
14
2
7.3.1 Source Code:
#include <bits/stdc++.h>
using namespace std;
int findShortestPathWeightKEdges(int V, vector<vector<int>>&
graph, int src, int dest, int k) {
const int INF = INT_MAX;
vector<vector<int>> dp(k + 1, vector<int>(V, INF));
// Base case: 0 edges to reach src
dp[0][src - 1] = 0;

for (int e = 1; e <= k; ++e) {

 for (int u = 0; u < V; ++u) {
for (int v = 0; v < V; ++v) {
if (graph[u][v] != 0 && dp[e - 1][u] != INF) {
if (dp[e - 1][u] + graph[u][v] < dp[e][v]) {
dp[e][v] = dp[e - 1][u] + graph[u][v];
}
}
}
}
}
return dp[k][dest - 1] == INF ? -1 : dp[k][dest - 1];
}
int main() {
int V;
cin >> V;
vector<vector<int>> graph(V, vector<int>(V));
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
cin >> graph[i][j];
}
}
int src, dest;
cin >> src >> dest;
int k;
cin >> k;

int result = findShortestPathWeightKEdges(V, graph, src,

dest, k);
if (result != -1) {
cout << "Weight of shortest path from (" << src << "," <<
dest << ") with " << k << " edges : " << result << endl;
} else {
cout << "no path of length k is available" << endl;
}
return 0;
}
7.3.2 Output Screenshot:
 CHAPTER 8: Week 8

8.1 Assume that a project of road construction to connect some cities is given to your friend.
Map of these cities and roads which will connect them (after construction) is provided to
him in the form of a graph. Certain amount of rupees is associated with construction of
each road. Your friend has to calculate the minimum budget required for this project. The
budget should be designed in such a way that the cost of connecting the cities should be
minimum and number of roads required to connect all the cities should be minimum (if
there are N cities then only N-1 roads need to be constructed). He asks you for help.
Now, you have to help your friend by designing an algorithm which will find minimum
cost required to connect these cities. (use Prim's algorithm)
Sample I/O Problem I & II:
Input: Output:
7 Minimum Spanning Weight: 39
0075000
0085000
7809700
5 0 9 0 15 6 0
0 5 7 15 0 8 9
0 0 0 6 8 0 11
0 0 0 0 9 11 0
8.1.1 Source Code:
#include <bits/stdc++.h>
using namespace std;
int primMST(vector<vector<int>>& graph, int V) {
vector<int> key(V, INT_MAX);
vector<bool> inMST(V, false);
priority_queue<pair<int, int>, vector<pair<int, int>>,
greater<pair<int, int>>> pq;
int src = 0; // Start from the first city
[Link]({0, src});
key[src] = 0;
int mstWeight = 0;
while (![Link]()) {
int u = [Link]().second;
[Link]();
if (inMST[u]) continue;
inMST[u] = true;
mstWeight += key[u];
for (int v = 0; v < V; ++v) {
if (graph[u][v] != 0 && !inMST[v] && graph[u][v] <
key[v]) {
key[v] = graph[u][v];
[Link]({key[v], v});
}
 }
}
return mstWeight;
}
int main() {
int V;
cin >> V;
vector<vector<int>> graph(V, vector<int>(V));
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
cin >> graph[i][j];
}
}
int minCost = primMST(graph, V);
cout << "Minimum Spanning Weight: " << minCost << endl;
return 0;
}
8.1.2 Output Screenshot:

8.2 Implement the previous problem using Kruskal's algorithm.

8.2.1 Source Code:
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v, weight;
Edge(int u, int v, int weight) : u(u), v(v), weight(weight)
{}
};
bool compareEdges(const Edge &a, const Edge &b) {
return [Link] < [Link];
}
int findRoot(vector<int> &parent, int u) {
if (parent[u] != u) {
parent[u] = findRoot(parent, parent[u]);
}
return parent[u];
}
void unionSets(vector<int> &parent, vector<int> &rank, int u, int
v) {
int rootU = findRoot(parent, u);
int rootV = findRoot(parent, v);
if (rootU != rootV) {
if (rank[rootU] > rank[rootV]) {
parent[rootV] = rootU;
} else if (rank[rootU] < rank[rootV]) {
parent[rootU] = rootV;
} else {
parent[rootV] = rootU;
rank[rootU]++;
}
}
}
int kruskalMST(vector<vector<int>> &graph, int V) {
vector<Edge> edges;
for (int u = 0; u < V; ++u) {
for (int v = u + 1; v < V; ++v) {
if (graph[u][v] != 0) {
edges.emplace_back(u, v, graph[u][v]);
}
}
}
sort([Link](), [Link](), compareEdges);
vector<int> parent(V);
vector<int> rank(V, 0);
for (int i = 0; i < V; ++i) {
parent[i] = i;
}
int mstWeight = 0;
int edgesAdded = 0;
for (const Edge &edge : edges) {
if (edgesAdded == V - 1) break;
int u = edge.u;
int v = edge.v;
int rootU = findRoot(parent, u);
int rootV = findRoot(parent, v);
if (rootU != rootV) {
unionSets(parent, rank, u, v);
mstWeight += [Link];
edgesAdded++;
}
}
return mstWeight;
 }
int main() {
int V;
cin >> V;
vector<vector<int>> graph(V, vector<int>(V));
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
cin >> graph[i][j];
}
}
int minCost = kruskalMST(graph, V);
cout << "Minimum Spanning Weight: " << minCost << endl;
return 0;
}
8.2.2 Output Screenshot:

8.3 Assume that same road construction project is given to another person. The amount he
will earn from this project is directly proportional to the budget of the project. This
person is greedy, so he decided to maximize the budget by constructing those roads who
have highest construction cost. Design an algorithm and implement it using a program to
find the maximum budget required for the project.
Sample I/O Problem III:
Input: Output:
7 Maximum Spanning Weight: 59
0075000
0085000
7809700
5 0 9 0 15 6 0
0 5 7 15 0 8 9
0 0 0 6 8 0 11
0 0 0 0 9 11 0
8.3.1 Source Code:
#include <bits/stdc++.h>
using namespace std;
int primMaxST(vector<vector<int>>& graph, int V) {
vector<int> key(V, INT_MIN);
 vector<bool> inMST(V, false);
priority_queue<pair<int, int>> pq;
int src = 0; // Start from the first city
[Link]({0, src});
key[src] = 0;
int maxSTWeight = 0;
while (![Link]()) {
int u = [Link]().second;
[Link]();
if (inMST[u]) continue;
inMST[u] = true;
maxSTWeight += key[u];
for (int v = 0; v < V; ++v) {
if (graph[u][v] != 0 && !inMST[v] && graph[u][v] >
key[v]) {
key[v] = graph[u][v];
[Link]({key[v], v});
}
}

}
return maxSTWeight;
}
int main() {
int V;
cin >> V;
vector<vector<int>> graph(V, vector<int>(V));
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
cin >> graph[i][j];
}
}
int maxCost = primMaxST(graph, V);
cout << "Maximum Spanning Weight: " << maxCost << endl;
return 0;
}
8.3.2 Output Screenshot:
 CHAPTER 9: Week 9

9.1 Given a graph, Design an algorithm and implement it using a program to implement
Floyd Warshall all pair shortest path algorithm.
Sample I/O Problem I & II:
Input: Output:
5 Shortest Distance Matrix:
0 10 5 5 INF 0 10 15 5 15
INF 0 5 5 5 INF 0 5 5 5
INF INF 0 INF 10 INF INF 0 15 10
INF INF INF 0 20 INF INF INF 0 20
INF INF INF 5 0 INF INF INF 5 0
9.1.1 Source Code:
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
#define INF INT_MAX
void printSolution(vector<vector<int>>& dist, int V) {
cout << "Shortest Distance Matrix:" << endl;
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
if (dist[i][j] == INF)
cout << "INF ";
else
cout << dist[i][j] << " ";
}

cout << endl;

}
}
void floydWarshall(vector<vector<int>>& graph, int V) {
vector<vector<int>> dist(V, vector<int>(V));
// Initialize the distance matrix
for (int i = 0; i < V; ++i)
for (int j = 0; j < V; ++j)
dist[i][j] = graph[i][j];
// Update the distance matrix by considering each vertex as
intermediate
for (int k = 0; k < V; ++k) {
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
// Avoid overflow by checking if either distance
is INF
if (dist[i][k] != INF && dist[k][j] != INF &&
dist[i][k] + dist[k][j] < dist[i][j]) {
 dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
printSolution(dist, V);
}
int main() {
int V;
cin >> V;
vector<vector<int>> graph(V, vector<int>(V));
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
string s;
cin >> s;
if (s == "INF")
graph[i][j] = INF;
else
graph[i][j] = stoi(s);
}
}

floydWarshall(graph, V);
return 0;
}
9.1.2 Output Screenshot:

9.2 Given a knapsack of maximum capacity w. N items are provided, each having its own
value and weight. You have to Design an algorithm and implement it using a program to
find the list of the selected items such that the final selected content has weight w and has
maximum value. You can take fractions of items,i.e. the items can be broken into smaller
pieces so that you have to carry only a fraction xi of item i, where 0 ≤xi≤ 1.
Sample I/O Problem II:
Input: Output:
6 Maximum value : 22.33
6 10 3 5 1 3 item-weight
621835 5-3.00
16 6-10.00
4-6.00
1-1.00
3-1.67
9.2.1 Source Code:
#include <bits/stdc++.h>
using namespace std;
struct Item {
int weight;
int value;
int index;
double ratio;
};
bool compare(Item a, Item b) {
return [Link] > [Link];
}
void fractionalKnapsack(int n, vector<int>& weights, vector<int>&
values, int W) {
vector<Item> items(n);
for (int i = 0; i < n; ++i) {
items[i].weight = weights[i];
items[i].value = values[i];
items[i].index = i + 1;
items[i].ratio = (double)values[i] / weights[i];
}
sort([Link](), [Link](), compare);
double totalValue = 0.0;
vector<pair<int, double>> selectedItems;
int remainingWeight = W;
for (int i = 0; i < n; ++i) {
if (remainingWeight <= 0) break;
if (items[i].weight <= remainingWeight) {
totalValue += items[i].value;
remainingWeight -= items[i].weight;
selectedItems.push_back({items[i].index, 1.0});
} else {
double fraction = (double)remainingWeight /
items[i].weight;
totalValue += items[i].value * fraction;
selectedItems.push_back({items[i].index, fraction});
remainingWeight = 0;
 }
}
cout << fixed << setprecision(2);
cout << "Maximum value : " << totalValue << endl;
cout << "item-weight" << endl;
for (auto item : selectedItems) {
cout << [Link] << "-" << [Link] *
items[[Link] - 1].weight << endl;
}
}
int main() {
int n;
cin >> n;
vector<int> weights(n);
vector<int> values(n);
for (int i = 0; i < n; ++i) {
cin >> weights[i];
}
for (int i = 0; i < n; ++i) {
cin >> values[i];
}
int W;
cin >> W;
fractionalKnapsack(n, weights, values, W);
return 0;
}
9.2.2 Output Screenshot

9.3 Given an array of elements. Assume arr[i] represents the size of file i. Write an algorithm
and a program to merge all these files into single file with minimum computation. For
given two files A and B with sizes m and n, computation cost of merging them is
O(m+n). (Hint: use greedy approach)
 Sample I/O Problem III:
Input: Output:
10 895
10 5 100 50 20 15 5 20 100 10
9.3.1 Source Code:
#include <bits/stdc++.h>
using namespace std;
int minComputationCost(vector<int>& files) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int file : files) {
[Link](file);
}
int totalCost = 0;
while ([Link]() > 1) {
int first = [Link]();
[Link]();
int second = [Link]();
[Link]();
int cost = first + second;
totalCost += cost;
[Link](cost);
}
return totalCost;
}
int main() {
int n;
cin >> n;
vector<int> files(n);
for (int i = 0; i < n; ++i) {
cin >> files[i];
}
cout << minComputationCost(files) << endl;
return 0;
}
9.3.2 Output Screenshot:
 CHAPTER 10: Week 10

10.1 Given a list of activities with their starting time and finishing time. Your goal is to select
maximum number of activities that can be performed by a single person such that selected
activities must be non-conflicting. Any activity is said to be non-conflicting if starting time
of an activity is greater than or equal to the finishing time of the other activity. Assume that a
person can only work on a single activity at a time.
Sample I/O Problem I :
Input: Output:
10 No. of non-conflicting activities: 4
1 3 0 5 3 5 8 8 2 12 List of selected activities: 1, 4, 7, 10
4 5 6 7 9 9 11 12 14 16
10.1.1 Source Code:
#include <bits/stdc++.h>
using namespace std;
struct Activity {
int start;
int finish;
int index;
};
bool compareActivities(Activity a, Activity b) {
return [Link] < [Link];
}
void selectActivities(int N, vector<int>& start, vector<int>&
finish) {
vector<Activity> activities(N);
for (int i = 0; i < N; ++i) {
activities[i].start = start[i];
activities[i].finish = finish[i];
activities[i].index = i + 1; // Assuming activities are
1-indexed
}
sort([Link](), [Link](),
compareActivities);
vector<int> selected;
int lastFinish = -1;
for (const Activity& activity : activities) {
if ([Link] >= lastFinish) {
selected.push_back([Link]);
lastFinish = [Link];
}
}
cout << "No. of non-conflicting activities: " <<
[Link]() << endl;
cout << "List of selected activities: ";
 for (size_t i = 0; i < [Link](); ++i) {
if (i != 0) cout << ", ";
cout << selected[i];
}
cout << endl;
}
int main() {
int N;
cin >> N;
vector<int> start(N);
vector<int> finish(N);
for (int i = 0; i < N; ++i) {
cin >> start[i];
}
for (int i = 0; i < N; ++i) {
cin >> finish[i];
}
selectActivities(N, start, finish);
return 0;
}
10.1.2 Output Screenshot:

10.2 Given a long list of tasks. Each task takes specific time to accomplish it and each task has
a deadline associated with it. You have to design an algorithm and implement it using a
program to find maximum number of tasks that can be completed without crossing their
deadlines and also find list of selected tasks..
Sample I/O Problem II :
Input: Output:
7 Max number of tasks = 4
2132221 Selected task numbers : 1, 2, 3, 6
2386253
10.2.1 Source Code:
#include <bits\stdc++.h>
using namespace std;
struct Task {
int time;
int deadline;
int index;
 };
bool compareDeadline(const Task &a, const Task &b) {
return [Link] < [Link];
}
int main() {
int n;
cin >> n;
vector<Task> tasks(n);
for (int i = 0; i < n; ++i) {
cin >> tasks[i].time;
tasks[i].index = i + 1; // 1-based index
}
for (int i = 0; i < n; ++i) {
cin >> tasks[i].deadline;
}
// Sort tasks by deadline
sort([Link](), [Link](), compareDeadline);
int currentTime = 0;
vector<int> selectedTasks;
for (const auto &task : tasks) {
if (currentTime + [Link] <= [Link]) {
selectedTasks.push_back([Link]);
currentTime += [Link];
}
}
cout << "Max number of tasks = " << [Link]() <<
endl;
cout << "Selected task numbers : ";
for (size_t i = 0; i < [Link](); ++i) {
if (i != 0) {
cout << ", ";
}
cout << selectedTasks[i];
}
cout << endl;
return 0;
}
10.2.2 Output Screenshot:
 10.3 Given an unsorted array of elements, design an algorithm and implement it using a
program to find whether majority element exists or not. Also find median of the array. A
majority element is an element that appears more than n/2 times, where n is the size of array.
Sample I/O Problem III :
Input: Output:
9 yes
442322322 2
10.3.1 Source Code:
#include <bits\stdc++.h>
using namespace std;
void findMajorityAndMedian() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
// Step 1: Find majority candidate using Boyer-Moore
algorithm
int candidate = -1;
int count = 0;
for (int i=0;i<n;i++) {
if (count == 0) {
candidate = arr[i];
}
count += (arr[i] == candidate) ? 1 : -1;
}
// Verify if the candidate is indeed the majority element
int majorityThreshold = n / 2;
int actualCount = 0;
for (int i=0 ;i<n;i++) {
if (arr[i] == candidate) {
actualCount++;
}
}
bool hasMajority = actualCount > majorityThreshold;
// Step 2: Find the median
sort([Link](), [Link]());
double median;
if (n % 2 == 1) {
median = arr[n / 2];
} else {
median = (arr[n / 2 - 1] + arr[n / 2]) / 2.0;
}
 // Output results
cout << (hasMajority ? "yes" : "no") << endl;
// Check if median is integer or float to print appropriately
if (n % 2 == 0) {
if ((arr[n / 2 - 1] + arr[n / 2]) % 2 == 0) {
cout << static_cast<int>(median) << endl;
} else {
cout << median << endl;
}
} else {
cout << static_cast<int>(median) << endl;
}
}
int main() {
findMajorityAndMedian();
return 0;
}
10.3.2 Output Screenshot:
 CHAPTER 11: Week 11

11.1 Given a sequence of matrices, write an algorithm to find most efficient way to multiply these
matrices together. To find the optimal solution, you need to find the order in which these
matrices should be multiplied.
Sample I/O Problem I :
Input: Output:
3 4500
10 30
30 5
5 60
11.1.1 Source Code:
#include <bits\stdc++.h>
using namespace std;
int matrixChainMultiplication(const vector<int>& dims) {
int n = [Link]() - 1; // Number of matrices
vector< vector< int > > dp(n, vector< int >(n, 0));
for (int length = 2; length <= n; ++length) { // length is
the chain length
for (int i = 0; i < n - length + 1; ++i) {
int j = i + length - 1;
dp[i][j] = INT_MAX;
for (int k = i; k < j; ++k) {
int cost = dp[i][k] + dp[k+1][j] + dims[i] *
dims[k+1] * dims[j+1];
if (cost < dp[i][j]) {
dp[i][j] = cost;
}
}
}
}
return dp[0][n-1];
}
int main() {
int n;
cin >> n;
vector<int> dims(n + 1);
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
dims[i] = a;
if (i == n - 1) {
dims[i + 1] = b;
}
}
 cout << matrixChainMultiplication(dims) << endl;
return 0;
}
11.1.2 Output Screenshot:

11.2 Given a set of available types of coins. Let suppose you have infinite supply of each type of
coin. For a given value N, you have to Design an algorithm and implement it using a
program to find number of ways in which these coins can be added to make sum value equals
to N.
Sample I/O Problem II :
Input: Output:
4 5
2563
10
11.2.1 Source Code:
#include <iostream>
#include <vector>
using namespace std;
int countWays(vector<int>& coins, int N) {
vector<int> dp(N + 1, 0);
dp[0] = 1; // Base case: one way to make sum 0

for (int coin : coins) {

for (int i = coin; i <= N; ++i) {
dp[i] += dp[i - coin];
}
}
return dp[N];
}
int main() {
int numCoins;
cin >> numCoins;
vector<int> coins(numCoins);
for (int i = 0; i < numCoins; ++i) {
cin >> coins[i];
}
int N;
cin >> N;
 cout << countWays(coins, N) << endl;
return 0;
}
11.2.2 Output Screenshots:

11.3 Given a set of elements, you have to partition the set into two subsets such that the sum of
elements in both subsets is same. Design an algorithm and implement it using a program to
solve this problem.
Sample I/O Problem II :
Input: Output:
7 yes
1 5 4 11 5 14 10
11.3.1 Source Code:
#include <bits\stdc++.h>
using namespace std;
bool canPartition(vector<int>& nums) {
int totalSum = accumulate([Link](), [Link](), 0);
if (totalSum % 2 != 0) return false;
int target = totalSum / 2;
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int num : nums) {
for (int i = target; i >= num; --i) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[target];
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
if (canPartition(nums)) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
return 0;
 }
11.3.2 Output Screenshots:
 CHAPTER 12: Week 12

12.1 Given two sequences, Design an algorithm and implement it using a program to find the
length of longest subsequence present in both of them. A subsequence is a sequence that
appears in the same relative order, but not necessarily contiguous.
Sample I/O Problem I :
Input: Output:
Sequence1: AGGTAB Longest Common Subsequence: GTAB
Sequence2: GXTXAYB length = 4

12.1.1 Source Code:

#include <bits\stdc++.h>
using namespace std;
string findLCS(const string &s1, const string &s2) {
int m = [Link]();
int n = [Link]();
vector< vector< int > > dp(m + 1, vector< int >(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
int length = dp[m][n];
string lcs(length, ' ');
int i = m, j = n;
while (i > 0 && j > 0) {
if (s1[i - 1] == s2[j - 1]) {
lcs[--length] = s1[i - 1];
--i;
--j;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
--i;
} else {
--j;
}
}
return lcs;
}
int main() {
string s1, s2;
cout << "Sequence1: ";
 cin >> s1;
cout << "Sequence2: ";
cin >> s2;
string lcs = findLCS(s1, s2);
cout << "Longest Common Subsequence: " << lcs << endl;
cout << "length = " << [Link]() << endl;
return 0;
}
12.1.2 Output Screenshot:

12.2 Given a knapsack of maximum capacity w. N items are provided, each having its own value
and weight. Design an algorithm and implement it using a program to find the list of the
selected items such that the final selected content has weight <= w and has maximum value.
Here, you cannot break an item i.e. either pick the complete item or don't pick it. (0-1
property).
Sample I/O Problem II:
Input: Output:
5 Value = 16
23346 Weights selected : 3 3 4
12594 Values of selected weights : 2 5 9
10
12.2.1 Source Code:
#include <bits\stdc++.h>
using namespace std;
void knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
vector< vector< int > > dp(n + 1, vector< int >(W + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int w = 1; w <= W; ++w) {
if (wt[i - 1] <= w) {
dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
int max_value = dp[n][W];
cout << "Value = " << max_value << endl;
vector<int> selected_weights;
vector<int> selected_values;
int w = W;
for (int i = n; i > 0 && max_value > 0; --i) {
if (max_value != dp[i - 1][w]) {
 selected_weights.push_back(wt[i - 1]);
selected_values.push_back(val[i - 1]);
max_value -= val[i - 1];
w -= wt[i - 1];
}
}
cout << "Weights selected : ";
for (int i=0;i<selected_weights.size();i++) {
cout << selected_weights[i] << " ";
}
cout << endl;
cout << "Values of selected weights : ";
for (int i=0;i<selected_values.size();i++) {
cout << selected_values[i] << " ";
}
cout << endl;
}
int main() {
int n;
cin >> n;
vector<int> wt(n);
for (int i = 0; i < n; ++i) {
cin >> wt[i];
}
vector<int> val(n);
for (int i = 0; i < n; ++i) {
cin >> val[i];
}
int W;
cin >> W;
knapsack(W, wt, val, n);
return 0;
}
12.2.2 Output Screenshot:

12.3 Given a string of characters, design an algorithm and implement it using a program to print
all possible permutations of the string in lexicographic order.
Sample I/O Problem III:
Input: Output:
CAB ABC
ACB
BAC
BCA
CAB
CBA
12.3.1 Source Code:
#include <bits\stdc++.h>
using namespace std;
void generatePermutations(string &s, int l, int r, vector<string>
&result) {
if (l == r) {
result.push_back(s);
} else {
for (int i = l; i <= r; ++i) {
// Skip duplicates to avoid redundant permutations
if (i != l && s[i] == s[l]) continue;
// Swap characters to generate new permutation
swap(s[l], s[i]);
// Recursively generate permutations for the
remaining characters
generatePermutations(s, l + 1, r, result);
// Backtrack to restore the original string
swap(s[l], s[i]);
}
}
}
vector<string> getPermutations(string s) {
vector<string> result;
sort([Link](), [Link]()); // Ensure lexicographic order
generatePermutations(s, 0, [Link]() - 1, result);
return result;
}
int main() {
string s;
cin >> s;
vector<string> permutations = getPermutations(s);
for (int i=0;i<[Link]();i++) {
cout << permutations[i] << endl;
}
return 0;
}
12.3.2 Output Screenshot:
 CHAPTER 13: Week 13

13.1 Given two sequences, Design an algorithm and implement it using a program to find the
length of longest subsequence present in both of them. A subsequence is a sequence that
appears in the same relative order, but not necessarily contiguous.
Sample I/O Problem I :
Input: Output:
20 a4
aedefjttza zftaeekaeq d1
e5
f2
j1
k1
q1
t3
z2
13.1.1 Source Code:
#include <bits\stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
map<char, int> freqMap;
for (int i = 0; i < n; ++i) {
char c;
cin >> c;
freqMap[c]++;
}
for (const auto& pair : freqMap) {
cout << [Link] << " " << [Link] << endl;
}
return 0;
}
13.1.2 Output Screenshot:
 13.2 Given an array of integers of size n, design an algorithm and write a program to check
whether this array contains duplicate within a small window of size k < n.
Sample I/O Problem II :
Input: Output:
2 Duplicate not present in window 3.
10 Duplicate present in window 4.
1234123412
3
12
123123123123
4
13.2.1 Source Code:
#include <bits\stdc++/h>
using namespace std;
string checkDuplicatesInWindow(const vector<int>& arr, int k) {
unordered_set<int> window;
for (int i = 0; i < [Link](); ++i) {
if (i > k - 1) {
[Link](arr[i - k]);
}
if ([Link](arr[i]) != [Link]()) {
return "Duplicate present in window " + to_string(k)
+ ".";
}
[Link](arr[i]);
}
return "Duplicate not present in window " + to_string(k) +
".";
}
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
int k;
cin >> k;
cout << checkDuplicatesInWindow(arr, k) << endl;
}
return 0;
}
 13.2.2 Output Screenshot:

13.3 Given an array of nonnegative integers, Design an algorithm and implement it using a
program to find two pairs (a,b) and (c,d) such that a*b = c*d, where a, b, c and d are
distinct elements of array.
Sample I/O Problem III:
Input: Output:
10 4 10
31 23 4 1 39 2 20 27 8 10 2 20
13.3.1 Source Code:
#include <bits\stdc++.h>
using namespace std;
void findPairs(const vector<int>& arr) {
unordered_map<int, vector<pair<int, int>>> productMap;
int n = [Link]();
// Store all pairs and their products
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int product = arr[i] * arr[j];
productMap[product].push_back({arr[i], arr[j]});
}
}
// Check for two pairs with the same product and no
overlapping elements
for (const auto& entry : productMap) {
const vector<pair<int, int>>& pairs = [Link];
if ([Link]() >= 2) {
for (size_t i = 0; i < [Link](); ++i) {
for (size_t j = i + 1; j < [Link](); ++j) {
int a = pairs[i].first;
int b = pairs[i].second;
int c = pairs[j].first;
int d = pairs[j].second;
// Ensure all elements are distinct
if (a != c && a != d && b != c && b != d) {
 cout << a << " " << b << endl;
cout << c << " " << d << endl;
return;
}
}
}
}
}
// If no such pairs found
cout << "No such pairs found." << endl;
}
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
findPairs(arr);
return 0;
}
13.3.2 Output Screenshot:
 CHAPTER 14: Week 14

14.1 Given a number n, write an algorithm and a program to find nth ugly number. Ugly
numbers are those numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3,
4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, ..... is sequence of ugly numbers.
Sample I/O Problem I :
Input: Output:
3 15
11 9
8 24
15
14.1.1 Source Code:
#include <bits\stdc++.h>
using namespace std;
int nthUglyNumber(int n) {
vector<int> uglyNumbers(n);
uglyNumbers[0] = 1;
int i2 = 0, i3 = 0, i5 = 0;
int nextMultipleOf2 = 2;
int nextMultipleOf3 = 3;
int nextMultipleOf5 = 5;
for (int i = 1; i < n; ++i) {
int nextUgly = min(nextMultipleOf2, min(nextMultipleOf3,
nextMultipleOf5));
uglyNumbers[i] = nextUgly;
if (nextUgly == nextMultipleOf2) {
i2++;
nextMultipleOf2 = uglyNumbers[i2] * 2;
}
if (nextUgly == nextMultipleOf3) {
i3++;
nextMultipleOf3 = uglyNumbers[i3] * 3;
}
if (nextUgly == nextMultipleOf5) {
i5++;
nextMultipleOf5 = uglyNumbers[i5] * 5;
}
}
return uglyNumbers[n - 1];
}
int main() {
int T;
cin >> T;
while (T--) {
int n;
 cin >> n;
cout << nthUglyNumber(n) << endl;
}
return 0;
}
14.1.2 Output Screenshot:

14.2 Given a directed graph, write an algorithm and a program to find mother vertex in a
graph. A mother vertex is a vertex v such that there exists a path from v to all other
vertices of the graph..

14.2.1 Source Code:

#include <bits\stdc++.h>
using namespace std;
void DFS(int v, vector<vector<int>>& adj, vector<bool>& visited,
stack<int>& finishStack) {
visited[v] = true;
for (int u : adj[v]) {
if (!visited[u]) {
DFS(u, adj, visited, finishStack);
}
}
[Link](v);
}
int findMotherVertex(vector<vector<int>>& adj, int V) {
vector<bool> visited(V, false);
stack<int> finishStack;
 // Perform DFS and fill the stack with vertices in order of
finishing times
for (int i = 0; i < V; ++i) {
if (!visited[i]) {
DFS(i, adj, visited, finishStack);
}
}
// The last finished vertex is the candidate for mother
vertex
int candidate = [Link]();
fill([Link](), [Link](), false);
stack<int> dummyStack;
DFS(candidate, adj, visited, dummyStack);

// Check if the candidate can reach all vertices

for (bool v : visited) {
if (!v) {
return -1; // No mother vertex found
}
}
return candidate;
}
int main() {
int V, E;
cout << "Enter number of vertices and edges: ";
cin >> V >> E;
vector<vector<int>> adj(V);
cout << "Enter edges (source destination):" << endl;
for (int i = 0; i < E; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
int motherVertex = findMotherVertex(adj, V);
if (motherVertex != -1) {
cout << "Mother vertex is: " << motherVertex << endl;
} else {
cout << "No mother vertex found." << endl;
}
return 0;
}
14.2.2 Output Screenshot: