algorithms
Northeastern University CS5800 Algorithms, Spring 2024 Instructor: Hyonho Lee Assignment 8 (Total Marks: 50 pts) Due Date: April 8, 2024, 6pm (PST) Name: Student Number: Collaborators: I, , read and understood Northeastern University’s Academic Integrity Policy (https://osccr.sites.northeastern.edu/academic-integrity-policy/). 1. (20 pts) (Exercise 21.2-2 or 23.2-2 for the 3rd Ed) The below Python function, prim2(G, r), returns a minimum spanning tree using Prim’s algorithm without using a priority queue. G is an adjacent matrix representing a connected undirected graph. Note that, unlike the Prim’s algorithm in the class, this algorithm does not use Graph class nor Vertex class. The input format is a list of lists of integers, representing an adjacent matrix with edge weights. G’s vertex set is {0, …, n − 1}, where n is the total number of vertices. Input r is the starting vertex. In the function, variable, p, is used to record the predecessor and the proximity value of each vertex. For example, p[1] = (0, 4) indicates that vertex 1’s proximity value is 4 and its predecessor vertex is 0. Complete the below function, prim2(G, r), so that it correctly returns a minimum spanning tree in O(n2 ), where n is the number of vertices without using a priority queue. The output format is a list of pairs, representing a spanning tree of G. Note that the order of a pair or the order in a list does not matter, since it represents an undirected tree. (Do not use heapq. Do not implement a heap. Your algorithm should work without using a heap.) 1 import math def prim2(G, r): n = len(G) p = [(None, math.inf)]*n p[r] = (None, 0) # (pred, proximity) for each vertex ## Complete this part## # Construct a MST from p A = [] for i in range(n): if p[i][0] != None: A.append((i, p[i][0])) return A # Test cases g1 = [ [ 0, 4, 0, 0, 0, 0, 0, 8, 0], [ 4, 0, 8, 0, 0, 0, 0, 11, 0], [ 0, 8, 0, 7, 0, 4, 0, 0, 2], [ 0, 0, 7, 0, 9, 14, 0, 0, 0], [ 0, 0, 0, 9, 0, 10, 0, 0, 0], [ 0, 0, 4, 14, 10, 0, 2, 0, 0], [ 0, 0, 0, 0, 0, 2, 0, 1, 6], [ 8, 11, 0, 0, 0, 0, 1, 0, 7], [ 0, 0, 2, 0, 0, 0, 6, 7, 0] ] prim2(g1, 0) # The above should return # [(1, 0), (2, 1), (3, 2), (4, 3), (5, 2), (6, 5), (7, 6), (8, 2)] g2 = [ [ 0, [ 8, [ 5, [ 9, [ 6, [ 3, 8, 0, 2, 2, 5, 2, 5, 2, 0, 3, 1, 7, 9, 2, 3, 0, 1, 9, 6, 5, 1, 1, 0, 9, 3], 2], 7], 9], 9], 0] ] prim2(g2, 0) # The above should return [(1, 5), (2, 1), (3, 4), (4, 2), (5, 0)] 2 2. (30 pts) (Second-best minimum spanning tree, Problem 21-1 or 23-1 for the 3rd Ed.) The below function, secondMST(G), returns a second best minimum spanning tree of G. G is an adjacent matrix representing a connected undirected graph. The input format forG is a list of lists of integers, representing an adjacent matrix with edge weights. G’s vertex set is {0, …, n − 1}, where n is the total number of vertices. Note that this algorithm does not use Graph class nor Vertex class. Complete the function, secondMST(G), so that it correctly returns a second best minimum spanning tree in O(n2 ) time. The output format is a list of pairs, representing a spanning tree of G. Note that the order of a pair or the order in a list does not matter, since it represents an undirected tree. (Hint: Read the problem description in the textbook and follow the direction given by problem 21-1.b and 21-1.c.) def secondMST(G, r): ## Complete this function.## # Test cases g1 = [ [ 0, 4, 0, 0, 0, 0, 0, 8, 0], [ 4, 0, 8, 0, 0, 0, 0, 11, 0], [ 0, 8, 0, 7, 0, 4, 0, 0, 2], [ 0, 0, 7, 0, 9, 14, 0, 0, 0], [ 0, 0, 0, 9, 0, 10, 0, 0, 0], [ 0, 0, 4, 14, 10, 0, 2, 0, 0], [ 0, 0, 0, 0, 0, 2, 0, 1, 6], [ 8, 11, 0, 0, 0, 0, 1, 0, 7], [ 0, 0, 2, 0, 0, 0, 6, 7, 0] ] secondMST(g1) # The above should return # [(1, 0), (2, 1), (3, 2), (5, 4), (5, 2), (6, 5), (7, 6), (8, 2)] g2 = [ [ 0, [ 8, [ 5, [ 9, [ 6, [ 3, 8, 0, 2, 2, 5, 2, 5, 2, 0, 3, 1, 7, 9, 2, 3, 0, 1, 9, 6, 5, 1, 1, 0, 9, 3], 2], 7], 9], 9], 0] ] secondMST(g2) # The above should return[(1, 5), (2, 1), (3, 4), (1, 3), (5, 0)] # (or any spanning tree whose total weight is 10.) 3 Practice Exercises (The following questions will not be graded. Do not submit solutions. But similar questions may appear in the exams.) Exercise 21.1-3 (23.1-3 of the 3rd Ed.) Exercise 21.1-11 (23.1-11 of the 3rd Ed.) Exercise 21.2-4 (23.2-4 of the 3rd Ed.) Exercise 21.2-5 (23.2-5 of the 3rd Ed.) Problem 21-2 (Minimum spanning tree in sparse graphs) (23-2 of the 3rd Ed.) Exercise 22.1-1 (24.1-1 of the 3rd Ed.) Exercise 22.1-3 (24.1-3 of the 3rd Ed.) Exercise 22.2-1 (24.2-1 of the 3rd Ed.) Exercise 22.2-2 (24.2-2 of the 3rd Ed.) Exercise 22.3-1 (24.3-1 of the 3rd Ed.) Exercise 22.3-5 (24.3-4 of the 3rd Ed.) Problem 22-2 (Nesting boxes) (24-2 of the 3rd Ed.) 4
Collepals.com Plagiarism Free Papers
Are you looking for custom essay writing service or even dissertation writing services? Just request for our write my paper service, and we'll match you with the best essay writer in your subject! With an exceptional team of professional academic experts in a wide range of subjects, we can guarantee you an unrivaled quality of custom-written papers.
Get ZERO PLAGIARISM, HUMAN WRITTEN ESSAYS
Why Hire Collepals.com writers to do your paper?
Quality- We are experienced and have access to ample research materials.
We write plagiarism Free Content
Confidential- We never share or sell your personal information to third parties.
Support-Chat with us today! We are always waiting to answer all your questions.
