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

algorithms

We offer the best custom writing paper services. We have answered this question before and we can also do it for you.

GET STARTED TODAY AND GET A 20% DISCOUNT coupon code DISC20

We offer the bestcustom writing paper services. We have done this question before, we can also do it for you.

Why Choose Us

  • 100% non-plagiarized Papers
  • 24/7 /365 Service Available
  • Affordable Prices
  • Any Paper, Urgency, and Subject
  • Will complete your papers in 6 hours
  • On-time Delivery
  • Money-back and Privacy guarantees
  • Unlimited Amendments upon request
  • Satisfaction guarantee

How it Works

  • Click on the “Place Order” tab at the top menu or “Order Now” icon at the bottom and a new page will appear with an order form to be filled.
  • Fill in your paper’s requirements in the "PAPER DETAILS" section.
  • Fill in your paper’s academic level, deadline, and the required number of pages from the drop-down menus.
  • Click “CREATE ACCOUNT & SIGN IN” to enter your registration details and get an account with us for record-keeping and then, click on “PROCEED TO CHECKOUT” at the bottom of the page.
  • From there, the payment sections will show, follow the guided payment process and your order will be available for our writing team to work on it.