PYTHON PROGRAMMING: Improving the MST Implementation
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
PYTHON
- Read the problem below.
- Given the sample inputs and outputs.
- The code to be modified: https://pastebin.com/LxkCwpPj
![• Modify the given code implementation for the MinHeap such that:
Instead of having separate lists for keys and values (i.e., keys and values), you will instead have
a single list called heap. This heap variable should contain Node class objects. Each Node object
should contain a key and a value as its attribute.
Original
Expected modification
class MinHeap:
class MinHeap:
def _init_(self)
-> None:
_init__(self) -> None:
self.size = 0
self.size = 0
self.keys = [None]
self.heap = [None]
%3D
%3D
self.values = [None]
• Modify all the necessary methods and lines of code given that you will only have a list of Node
objects
• You can also choose to add/remove methods as you see fit
• Hint: make sure to define the __repr__ method for Node class to make it easier to debug
• Modify the implementation of Prim's and Kruskal's algorithms such that:
• Both classes (PrimMST and KruskalMST) would each have an mst attribute (i.e., a variable mst)
that stores a list of sets, where each set represents an edge of the Minimum Spanning Tree.
• Optional but highly recommended: Change the condition for Kruskal's algorithm to be when the
number of edges in the mst is equal to the (number of nodes - 1) instead of when the PQ is empty
Input Format
• The first line contains the number N which is the number of vertices. Graph will then have
nodes/vertices from 0 to N-1
The second line contains the number E which is the number of edges
Each of the next E lines contains 3 numbers separated by commas: v,w,weight.This means there
is an undirected edge connecting v and w with weight= weight
Constraints
v and w are not equal
• N, E > 0
• weight >0
v and w are guaranteed to be valid nodes/vertices
Output Format
• First line of the output should be the edges of the MST from Prim's algorithm
• Second line of the output should be the edges of the MST from Kruskal's algorithm
Both outputs should be a list of sets, where each set is an edge of the MST. For example, the MST
contains edges 1-2 and 2-3. The output should then be [{1,2}, {2,3}].
Note that the checker is order agnostic (i.e., it doesn't matter what order you output the edges; it will
check the presence/absence of edges)](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F519dec08-8ea6-43bd-acda-71c70d2d043d%2Fcb8aa465-dde1-452b-8e39-0077b6a49bf3%2F5xyyny1h_processed.jpeg&w=3840&q=75)
Transcribed Image Text:• Modify the given code implementation for the MinHeap such that:
Instead of having separate lists for keys and values (i.e., keys and values), you will instead have
a single list called heap. This heap variable should contain Node class objects. Each Node object
should contain a key and a value as its attribute.
Original
Expected modification
class MinHeap:
class MinHeap:
def _init_(self)
-> None:
_init__(self) -> None:
self.size = 0
self.size = 0
self.keys = [None]
self.heap = [None]
%3D
%3D
self.values = [None]
• Modify all the necessary methods and lines of code given that you will only have a list of Node
objects
• You can also choose to add/remove methods as you see fit
• Hint: make sure to define the __repr__ method for Node class to make it easier to debug
• Modify the implementation of Prim's and Kruskal's algorithms such that:
• Both classes (PrimMST and KruskalMST) would each have an mst attribute (i.e., a variable mst)
that stores a list of sets, where each set represents an edge of the Minimum Spanning Tree.
• Optional but highly recommended: Change the condition for Kruskal's algorithm to be when the
number of edges in the mst is equal to the (number of nodes - 1) instead of when the PQ is empty
Input Format
• The first line contains the number N which is the number of vertices. Graph will then have
nodes/vertices from 0 to N-1
The second line contains the number E which is the number of edges
Each of the next E lines contains 3 numbers separated by commas: v,w,weight.This means there
is an undirected edge connecting v and w with weight= weight
Constraints
v and w are not equal
• N, E > 0
• weight >0
v and w are guaranteed to be valid nodes/vertices
Output Format
• First line of the output should be the edges of the MST from Prim's algorithm
• Second line of the output should be the edges of the MST from Kruskal's algorithm
Both outputs should be a list of sets, where each set is an edge of the MST. For example, the MST
contains edges 1-2 and 2-3. The output should then be [{1,2}, {2,3}].
Note that the checker is order agnostic (i.e., it doesn't matter what order you output the edges; it will
check the presence/absence of edges)
![Sample Input 0
12
0,1,2
0,2,1
1,2,5
1,4,3
1,3,1
1
4,2,1
4,5,4
4,6,3
2,5,15
3,4,2
6,3,1
6,5,1
Sample Output 0
[{0, 2}, {2, 4}, {0, 1}, {3, 4}, {3, 6}, {5, 6}]
[{4, 2}, {2, 0}, {3, 6}, {5, 6}, {0, 1}, {3, 4}]
Sample Input 1
7
11
0,1,7
0,3,5
1,3,9
1,2,8
1,4,7
2,4,5
3,4,15
3,5,6
4,5,8
4,6,9
5,6,11
Sample Output 1
[{0, 3}, {3, 5}, {0, 1}, {1, 4}, {2, 4}, {4, 6}]
[{0, 3}, {2, 4}, {3, 5}, {0, 1}, {1, 4}, {4, 6}]](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F519dec08-8ea6-43bd-acda-71c70d2d043d%2Fcb8aa465-dde1-452b-8e39-0077b6a49bf3%2Ffn0ldvi_processed.jpeg&w=3840&q=75)
Transcribed Image Text:Sample Input 0
12
0,1,2
0,2,1
1,2,5
1,4,3
1,3,1
1
4,2,1
4,5,4
4,6,3
2,5,15
3,4,2
6,3,1
6,5,1
Sample Output 0
[{0, 2}, {2, 4}, {0, 1}, {3, 4}, {3, 6}, {5, 6}]
[{4, 2}, {2, 0}, {3, 6}, {5, 6}, {0, 1}, {3, 4}]
Sample Input 1
7
11
0,1,7
0,3,5
1,3,9
1,2,8
1,4,7
2,4,5
3,4,15
3,5,6
4,5,8
4,6,9
5,6,11
Sample Output 1
[{0, 3}, {3, 5}, {0, 1}, {1, 4}, {2, 4}, {4, 6}]
[{0, 3}, {2, 4}, {3, 5}, {0, 1}, {1, 4}, {4, 6}]
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY