[SOLVED] Csed233 – assignment #4

Evaluation Policy:
■ 100% penalty will be applied for the submission and marked as zero.
● We do not accept any submission via email; they will be ignored.
● We do not accept any keyboard-typed submissions for the written assignment.
● You can do your written assignment in two ways:
○ Use tablet (i.e. Galaxy Tab, iPad, etc) and stylus pen, and save your work as .pdf.
○ Write on any paper, scan it, and save as .pdf file
■ We recommend using Microsoft Lens to scan your works.
○ Please describe your process of solving the problems as detailed as possible.
○ If you write down your answer only, you will not earn a point.
● Please write neatly when showing your work.
○ Hardly unrecognizable work might be marked as zero points.
● Your code will be automatically tested using an evaluation program.
○ Each problem has the maximum score.
○ Full points will be given only if all test cases are passed; there are no partial points if only some portion of the test cases work, and the others don’t.
○ Points will be deducted for any typos or incorrect formatting
● Do not modify auxiliary files
○ utils.h, utils.cpp, evaluate.cpp, and so on.
● Compile your code using “Replit” and check your program before submission.
● You should not use C++ standard template library other than given ones. ○ DO NOT INCLUDE <queue>, <vector>, <stack>, or other container libraries ○ Any submission using such STL library will be disregarded.
○ Using only the given libraries will suffice.

Files You Need to Submit:
task_1.cpp
task_2.cpp
task_3.cpp
● .zip file named [your_student_id]_assignment4.zip (i.e. 20241234_assignment4.zip) containing:
○(do not change your filename!)
○(do not change your filename!)
○(do not change your filename!)
○ ds.h (optional)
○ wa4.pdf (your written assignment)
If You Find Bugs in the Program:
● Please notify us as soon as possible
Any other questions? Please use PLMS Q&A board in English.

Written Assignment #4
Q1. Graph Representation (Total 3pt)
Given a graph and its corresponding adjacency matrix or adjacency list representation, perform the following tasks. At each step, describe your reasoning and visually represent changes, if applicable.
Q1.1. Convert Adjacency Matrix to Adjacency List (1pt)
(1) Convert the adjacency matrix below into an adjacency list representation: (0.5pts)
Adjacency Matrix: (Directed Graph)
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
(2) Then identify whether the graph is connected or contains disconnected components. Explain your findings. (0.5pts)
Q1.2 Convert Adjacency List to Adjacency Matrix (2pt)
(1) Convert the adjacency list below into an adjacency matrix representation: (0.5pts)
Adjacency List: (Directed Graph)
1: [2, 3]
2: [4]
3: [5]
4: [6, 1]
5: [ ]
6: [3]
(2) Draw a directed graph. (0.5pts)
(3) Determine whether the graph is cyclic or acyclic. Justify your answer using the definition of cycles in directed graphs. (1pt)
Q2. MST (Total 3pts)
Q2.1 Convert Adjacency Matrix to Edge List (1pt)
(1) Given the following adjacency matrix for an undirected weighted graph, convert it into an edge list representation. (1pt)
1 2 3 4 5
————————–
1 | 0 2 0 6 0
2 | 2 0 3 8 5
3 | 0 3 0 0 7
4 | 6 8 0 0 9
5 | 0 5 7 9 0
(2) Apply Kruskal’s algorithm to find the Minimum Spanning Tree (MST) of the given graph. Clearly outline each step of the algorithm, explaining the selection of edges and the reasoning behind each decision. Present the MST in edge list representation and calculate the total weight of the MST. (2pts)
Programming Assignment #4
Basic Instruction
Please refer to C++ Environment Setup Guide, which is on PLMS.
Make sure your code can be compiled using command below:
$ g++ -std=c++11 -o task_1 task_1.cpp
Please ensure your program correctly handles inputs and outputs using cin and cout from <iostream>, adhering strictly to the format provided in the example.
Note: You are not required to submit the output of your program.
Example code: ex.cpp
#include <iostream> using namespace std;
int main() { int A, B, C; cin >> A >> B >> C;
// Do something with A, B, C
cout << A + B + C << endl;
return 0;
}
input_ex.txt
1 2 3
g++ ex.cpp -o ex && ./ex < input_ex.txt
6
[Task 1] MST (3pts)
You are given a connected, undirected graph with N nodes and M edges. Each edge has a weight associated with it. Your task is to compute the total weight of the Minimum Spanning Tree (MST) of the graph.
Constraints:
● 1≤ N ≤ 10^5
● N−1 ≤ M ≤ 2×10^5
● Edge weights are positive integers ≤ 10^6
● Nodes are numbered from 1 to N
Input
● The first line contains two integers: N and M
● The next M lines each contain three integers U, V, W, representing an undirected edge between node U and node V with weight W
Output
● Output a single integer representing the total weight of the Minimum Spanning Tree
Example Input & Output
Input Output
4 5
1 2 1
1 3
2 3
2 43 4 4
2
5
3 6
6 9
1 2 4
1 3 4
2 3 2
2 4 6
3 4
3 5
4 6
5 6
4 5 8
9
9
10
16 30
Example Usage
Using command line pipe (recommended)
Prepare an input file (e.g., input_1.txt) with the following content:
input_1.txt
4 5
1 2 1
1 3 4
2 3 2
2 4 5
3 4 3
Run the program using the input redirection operator < :
$ ./task_1 < input_1.txt
Alternatively, you can input the data manually:
$ ./task_1
4 5
1 2 1
1 3 4
2 3 2
2 4 5
3 4 3
Expected output:
6
[Task 2] Graph Traversal (3pts)
Description
You are given an undirected graph with n nodes and m edges. The graph is represented as a set of edges between nodes. Your task is to perform the following operations:
1. Shortest Path Calculation:
○ Calculate the shortest path from a given source node s to all other nodes using Breadth-First Search (BFS).
○ If a node is not reachable from the source, its shortest path distance should be -1.
2. Connected Components Identification:
○ Identify all connected components in the graph using Depth-First Search (DFS).
○ For each connected component, output the nodes in ascending order.
The graph structure can be implemented as either an adjacency matrix or an adjacency list.
Constraints:
● 1 ≤ n ≤ 10 (number of nodes)
● 0 ≤ m ≤ 100 (number of edges)
● 0 ≤ u, v
● s < n (node indices)
Input
● The first line contains two integers:
○ n — the number of nodes (labeled 0 to n-1).
○ m — the number of edges.
● The next m lines each contain two integers, u and v, representing an edge between nodes u and v.
● The last line contains a single integer, s — the source node for shortest path calculation.
Output
1. Shortest Path Distances:
○ The first line contains nn integers representing the shortest path distances from the source node ss to each node.
○ If a node is reachable from the source, print its shortest path distance. ○ If a node is not reachable, print −1.
2. Connected Components:
○ Each subsequent line corresponds to a connected component. ○ For each connected component:
■ List the nodes in ascending order, separated by spaces.
■ Connected components themselves should be sorted in ascending order, based on the smallest node in each component.
Sorting Requirements:
● Within each connected component: Nodes must appear in ascending order.
● Across connected components: Lines must be sorted by the smallest node in each component, ensuring the smallest values come first.
Example Input & Output

Input:
7 6 (7 nodes, 6 edges)
0 1 (edges)
0 2
1 3
4 5
5 6
4 6
0 (source node (s))
Correct Answer:
0 1 1 2 -1 -1 -1 (shortest paths for a given source node 0. -1 if not reachable)
0 1 2 3 (1st connected graph, ascending order)
4 5 6 (2nd connected graph, ascending order)
Wrong Answer: (Technically correct but violate output format)
0 1 1 2 -1 -1 -1
4 5 6 (violates component order, [4 5 6] comes before [0 1 2 3])
0 1 3 2 (violates node order within the component, 2 < 3)

Input Output
5 4
0 1
0 2
1 3
3 4
0 0 1
0 1 1
2 2
3 3
4
5 4
0 1
0 2
0 3
0 4
3 1 2
0 1 2
2 0
3 2
4
8 4
0 1
2 3
4 5
6 7
0 0 1
0 1
2 3
4 5
6 7 -1 -1 -1 -1 -1 -1
Example Usage
Using command line pipe (recommended)
Prepare an input file (e.g., input_1.txt) with the following content:
input_1.txt
5 4
0 1
0 2
1 3
3 4
0
Run the program using the input redirection operator < :
$ ./task_2 < input_1.txt
Alternatively, you can input the data manually:
$ ./task_2
5 4
0 1
0 2
1 3
3 4
0
Expected output:
0 1 1 2 3
0 1 2 3 4
[Task 3] Shortest Path with Edge Constraints (4pt)
Description
Given a weighted directed graph with N nodes and M edges, you need to find the shortest path from a source node S to a destination node D. However, the graph has an additional constraint:
● You can only traverse at most K edges.
Your task is to compute the shortest path from S to D that uses at most K edges. If there is no such path, report that it’s impossible.
Constraints:
● 1 ≤ N ≤ 100
● 1 ≤ M ≤ 1000
● 1 ≤ K ≤ 1000
● Edge weights are non-negative integers ≤10^5
● Nodes are numbered from 1 to N
Input
● The first line contains four integers: N, M, S, D
● The next M lines each contain three integers U, V, W, representing an edge from node U to node V with weight W
● The last line contains an integer K Output
● Output a single integer representing the minimum cost to reach from S to D using at most K edges. If it’s impossible, output -1
Example Input & Output
Input Output
5 6 1 5
1 2 10
1 3 3
2 3
3 2
2 4
4 5
3 1
4
2
2 14
4 4 1 4
1 2 5
2 3
3 4
1 3
2 5
5
15 20
3 2 1 3
1 2 4
2 3
1 6 -1
10 15 1 10
1 2 5
2 3 5
3 4 5
4 5 5
5 6 5
6 7 5
7 8 5
8 9 5
9 10 5
1 3 15
1 5 20
1 7 25
1 10 100
2 10 50
5 10 10
3 30
Example Usage
Using command line (recommended)
Prepare an input file (e.g., input_1.txt) with the following content:
input_1.txt
5 6 1 5
1 2 10
1 3 3
2 3 1
3 2 4
2 4 2
4 5 2
3
Run the program using the input redirection operator < :
$ ./task_3 < input_1.txt
Alternatively, you can input the data manually:
$ ./task_3
5 6 1 5
1 2 10
1 3 3
2 3 1
3 2 4
2 4 2
4 5 2
3
Expected output:
12
Before you submit
Files You Need to Submit:
● .zip file named [your_student_id]_assignment4.zip (i.e. 20241234_assignment4.zip) containing:
task_1.cpp
task_2.cpp
task_3.cpp
○(do not change your filename!)
○(do not change your filename!)
○(do not change your filename!)
○ ds.h (optional)
○ wa4.pdf (your written assignment)
Your submission should follow this format: (STUDENTID_assignment4.zip)

Please submit it as a .zip file.