DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

Experiment – 6.1

Student Name: Nikita Jha UID: 22BCS15758

Branch: BE-CSE Section/Group: 622-A
Semester: 5 Date of Performance: 08/10/24
Subject Name: Advanced Programming Subject Code: 22CSP-314

1. Aim:
In this challenge, you are required to implement inorder traversal of a tree.
Complete the inorder function in your editor below, which has 1
parameter: a pointer to the root of a binary tree. It must print the values in
the tree's inorder traversal as a single line of space-separated values.

2. Objective:
The objective of this code is to implement an in-order traversal of a binary
search tree, which recursively visits the left subtree, the root node, and
then the right subtree. The function takes the root node of the binary tree
as its parameter and prints the node values in ascending order (in-order
sequence) as a single line of space-separated values. This ensures that the
elements of the tree are output in sorted order, characteristic of in-order
traversal.

3. Implementation/Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
set<int> bst;
for (int i = 0; i < n; ++i) {
int val;
cin >> val;
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

bst.insert(val);
}
for (int val : bst) {
cout << val << " ";
}
cout << endl;
return 0;
}

4. Output

5. Learning Outcome:
1. Ability to implement recursive functions for tree traversal.
2. Understanding the structure and properties of binary search trees.
3. Experience in handling dynamic memory allocation using pointers in
C++.
4. Skill in printing elements in a specific traversal order from tree data
structures.
5. Familiarity with recursive function calls and base cases for tree
algorithms.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Experiment – 6.2

Student Name: Nikita Jha UID :22BCS15758

Branch: BE-CSE Section/Group: 622-A
Semester: 5 Date of Performance: 08/10/24
Subject Name: Advanced Programming Subject Code: 22CSP-314

1. Aim:
You are given a tree (a simple connected graph with no cycles). Find the
maximum number of edges you can remove from the tree to get a forest
such that each connected component of the forest contains an even
number of nodes.

2. Objective:
The objective of this code is to find the maximum number of edges that
can be removed from a tree to form a forest where each connected
component has an even number of nodes. It uses Depth-First Search
(DFS) to traverse the tree, counting the nodes in each subtree. If a subtree
has an even number of nodes, the edge connecting it to its parent can be
removed, and the algorithm keeps track of the number of such removable
edges.

3. Implementation Code:
#include <bits/stdc++.h>
using namespace std;
int dfs(int node, vector<vector<int>>& tree, vector<bool>& visited, int&
cuts) {
visited[node] = true;
int subtree_nodes = 1;
for (int neighbor : tree[node]) {
if (!visited[neighbor]) {
int child_nodes = dfs(neighbor, tree, visited, cuts);
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

if (child_nodes % 2 == 0) cuts++;
subtree_nodes += child_nodes;
}}
return subtree_nodes; }
int evenForest(int t_nodes, vector<pair<int, int>>& edges) {
vector<vector<int>> tree(t_nodes + 1);
for (auto& [u, v] : edges) {
tree[u].push_back(v);
tree[v].push_back(u); }
vector<bool> visited(t_nodes + 1, false);
int cuts = 0;
dfs(1, tree, visited, cuts); return cuts; }
int main() {
int t_nodes, t_edges;
cin >> t_nodes >> t_edges;
vector<pair<int, int>> edges(t_edges);
for (auto& [u, v] : edges) cin >> u >> v;
cout << evenForest(t_nodes, edges) << endl;
return 0; }

4. Output:
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

5. Learning Outcome:
1. Understanding tree traversal using Depth-First Search (DFS) to explore
nodes and their subtrees.
2. Learning how to use DFS to calculate the size of subtrees in a tree
structure.
3. Gaining insight into how to solve graph-related problems by
manipulating edges based on node counts.
4. Practicing the concept of conditionally removing edges based on
properties of subtrees (like even node counts).
5. Applying adjacency list representation to efficiently store and traverse
undirected graphs.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Experiment – 7.1

Student Name: Nikita Jha UID :22BCS15758

Branch: BE-CSE Section/Group: 622-A
Semester: 5 Date of Performance: 08/10/24
Subject Name: Advanced Programming Subject Code: 22CSP-314

1. Aim:
Consider an undirected graph where each edge weighs 6 units. Each of the
nodes is labelled consecutively from 1 to n. You will be given a number
of queries. For each query, you will be given a list of edges describing an
undirected graph. After you create a representation of the graph, you must
determine and report the shortest distance to each of the other nodes from
a given starting position using the breadth first search algorithm (BFS).
Return an array of distances from the start node in node number order. If a
node is unreachable, return -1 for that node.

2. Objective:
The objective of this code is to implement the Breadth-First Search (BFS)
algorithm to compute the shortest path distances in an unweighted,
undirected graph. For multiple test cases, the program reads the number of
nodes and edges, constructs an adjacency list to represent the graph, and
calculates the shortest distance from a specified source node to all other
nodes. The distances are calculated in terms of edge weights, where each
edge has a constant weight of 6. The result excludes the source node and
prints the shortest distances for the rest of the nodes in the graph.

3. Implementation/Code:
#include <bits/stdc++.h>
using namespace std;
int bfs(int n, int m, int edges[][2], int s, int *result) {
list<int> adj[1001];
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

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

adj[edges[i][0] - 1].push_back(edges[i][1] - 1);
adj[edges[i][1] - 1].push_back(edges[i][0] - 1);}
int dists[1001];
fill(dists, dists + n, -1); queue<int> q;
q.push(s - 1);
dists[s - 1] = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int child : adj[node]) {
if (dists[child] == -1) {
q.push(child);
dists[child] = dists[node] + 6;
}}}
int j = 0;
for (int i = 0; i < n; ++i) {
if (i != s - 1)
result[j++] = dists[i];}
return j;}
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
int edges[1001][2];
for (int i = 0; i < m; ++i) {
cin >> edges[i][0] >> edges[i][1]; }
int s;
cin >> s;
int result[1001];
int result_size = bfs(n, m, edges, s, result);
for (int i = 0; i < result_size; i++)
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

cout << result[i] << " ";

cout << endl;}
return 0;
}

4. Output:

5. Learning Outcome:
1. Understand how to implement the BFS algorithm to find the shortest path
in an unweighted, undirected graph.
2. Learn to represent a graph using an adjacency list with dynamic
structures.
3. Practice initializing and managing distance arrays to track visited nodes
and shortest paths.
4. Gain experience in handling multiple test cases and dynamic input for
graph traversal problems.
5. Learn to efficiently implement BFS using a queue to explore all nodes
level by level from a given source.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Experiment – 7.2

Student Name: Nikita Jha UID :22BCS15758

Branch: BE-CSE Section/Group: 622-A
Semester: 5 Date of Performance: 08/10/24
Subject Name: Advanced Programming Subject Code: 22CSP-314

1. Aim:
The member states of the UN are planning to send 2 people to the moon.
They want them to be from different countries. You will be given a list of
pairs of astronaut ID's. Each pair is made of astronauts from the same
country. Determine how many pairs of astronauts from different countries
they can choose from.

2. Objective:
The code implements a graph traversal using Depth-First Search to
determine the number of connected components in an undirected graph. It
calculates the number of distinct pairs of vertices that belong to different
components. The input consists of `n` vertices and `m` edges, and the graph
is represented as an adjacency list. The DFS function explores each
component, and the number of vertices in each component is stored. Finally,
the code calculates the total possible pairs of vertices, subtracts the number
of pairs within the same component, and outputs the result, which is the
number of valid pairs across different components.

3. Implementation Code:
#include <bits/stdc++.h>
#define MAX 643000
using namespace std;
vector<int> adj[MAX];
int visited[MAX], vertices;
void DFS(int u) {
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

visited[u] = 1;
vertices++;
for (int v : adj[u]) {
if (!visited[v]) {
DFS(v);
}}}
int main() {
int n, m, u, v, numComponents = 0;
long long totalWays, sameWays = 0;
vector<int> eachC;
cin >> n >> m;
if (n == 1) {
cout << "0\n";
return 0;
}
for (int i = 0; i < m; i++) {
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
vertices = 0;
DFS(i);
eachC.push_back(vertices);
numComponents++;
}}
totalWays = n * (n - 1LL) / 2;
for (int i = 0; i < numComponents; i++) {
sameWays += (eachC[i] * (eachC[i] - 1LL)) / 2;
}
cout << totalWays - sameWays << "\n";
return 0;
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

4. Output:

5. Learning Outcome:
1. Learn how to implement Depth-First Search (DFS) to explore connected
components in an undirected graph.
2. Understand the use of adjacency lists to represent graphs and store
relationships between vertices.
3. Practice counting connected components and determining the size of each
component using DFS.
4. Gain insights into calculating total possible pairs of vertices and filtering out
pairs within the same component.
5. Explore basic graph theory concepts like connected components and pair
counting in competitive programming.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Experiment – 8.1

Student Name: Nikita Jha UID :22BCS15758

Branch: BE-CSE Section/Group: 622-A
Semester: 5 Date of Performance: 15/10/24
Subject Name: Advanced Programming Subject Code: 22CSP-314

1. Aim:
Problem Marc loves cupcakes, but he also likes to stay fit. Each cupcake
has a calorie count, and Marc can walk a distance to expend those
calories. If Marc has eaten j cupcakes so far, after eating a cupcake with
ccc calories he must walk at least 2j×c miles to maintain his weight.

2. Objective:
The provided code defines a function, `marcsCakewalk`, that calculates
the minimum total number of miles Marc needs to walk to burn the
calories from a list of cakes, given their calorie values. It first sorts the
calorie values in descending order and then computes the total miles by
multiplying each calorie value by 2i. The final result is printed in the
`main` function after reading the number of cakes and their respective
calorie counts.

3. Implementation/Code:
#include <bits/stdc++.h>
using namespace std;
long long marcsCakewalk(int calorie[], int n) {
sort(calorie, calorie + n, greater<int>());

long long total_miles = 0;

for(int i = 0; i < n; i++) {
total_miles += (1LL << i) * (long long)calorie[i];
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

return total_miles;
}
int main(){
int n;
cin >> n;
int calorie[40];
for(int i = 0; i < n; i++){
cin >> calorie[i];
}
long long result = marcsCakewalk(calorie, n);
cout << result;
return 0;
}

4. Output:

5. Time Complexity: O( N logn)

6. Space Complexity: O(n)

DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

7. Learning Outcome:
1. Learn how sorting can impact problem-solving strategies by arranging
elements to maximize or minimize certain conditions.
2. Understand the usage of bitwise operations in practical scenarios like
exponential multiplication.
3. Develop an intuition for greedy algorithms where arranging input in a
certain order can lead to optimal solutions.
4. Manage basic I/O operations in C++.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Experiment – 8.2

Student Name: Nikita Jha UID :22BCS15758

Branch: BE-CSE Section/Group: 622-A
Semester: 5 Date of Performance: 15/10/24
Subject Name: Advanced Programming Subject Code: 22CSP-314

1. Aim:
Alice is a kindergarten teacher. She wants to give some candies to the
children in her class. All the children sit in a line and each of them has a
rating score according to his or her performance in the class. Alice wants to
give at least 1 candy to each child. If two children sit next to each other, then
the one with the higher rating must get more candies. Alice wants to
minimize the total number of candies she must buy.

2. Objective:
The objective of this code is to calculate the minimum number of candies
required to distribute to children based on their ratings while ensuring that
each child receives at least one candy and children with higher ratings than
their immediate neighbours receive more candies. It initializes an array to
track the candy count for each child, iterates through the ratings to assign
candies based on the given conditions, and finally sums up the total candies
distributed.

3. Algorithm:
• Read the number of elements n, allocate two arrays arr and candy, and
input n values into arr while initializing candy to 1 for each element.
• Iterate from the start to the end of the array, incrementing candy count for
each element if it's greater than the preceding element.
• Iterate from the end to the start of the array, adjusting the candy count to
ensure every element that's greater than the succeeding one has more
candy.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

• Sum all elements in the candy array using accumulate to determine the total
number of candies required.
• Print the total number of candies.

4. Implementation Code:
#include <bits/stdc++.h>
using namespace std;

long long marcsCakewalk(int calorie[], int n) {

sort(calorie, calorie + n, greater<int>());
long long total_miles = 0;
for(int i = 0; i < n; i++) {
total_miles += (1LL << i) * (long long)calorie[i];
}
return total_miles;
}

int main(){

int n;
cin >> n;

int calorie[40];

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

cin >> calorie[i];
}
long long result = marcsCakewalk(calorie, n);
cout << result;

return 0;
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

5. Output:

6. Time Complexity: O(n)

7. Space Complexity: O(n)

8. Learning Outcome:
1. Understand applying greedy strategies for optimization problems.
2. Use C++ standard library functions like max for computational efficiency.
3. Learn how to efficiently manage and manipulate data in arrays.
4. Implement conditional checks for solving sequential decision problems.