Starting from:
$29.99
Assignment 2: Minimum Spanning Trees
Minimum Spanning Trees
1 Programming Assignment
Theresa May, having just watched Shaun of the Dead, becomes worried that a zombie revoltisimminent. Shouldthishappen,anaturalfearisthatthezombieswillorganize clandestine meetings, pool their collective minimal brain power, and ultimately push for “Zexit” (Zombie Exit), thereby crippling the eponymous unity of the UK. Therefore, May creates the Ministry of Zombie Affairs, to be headed by Simon Pegg. Simon decides that the best way to prevent zombie meetings is by scrapping London’s current road network and replacing it with a network with the property that any two places are connected by precisely one path. This way, zombie drivers easily can be stopped using minimal blockades. Unfortunately, nearly all the funds required were spent on billboards warning of Zexit, and so Simon needs to construct a road network whose total length is minimal in order to minimize construction costs. More formally, the problem is described by the following Input and Output. Input: An edge-weighted graph G of n vertices. Each edge weight corresponds to the cost of constructing a road between two places in London. Output: The cost (sum of the edge weights) of the minimum-cost solution. A Java template has been provided containing an empty function mst. This function takes a two-dimensional integer array A that represents the weighted graph in the form of an adjacency matrix. This function returns the sum of the weights of the edges in a minimum spanning tree of G. Your task is to write the body of the mst function, which can include calls to helper functions that you write. Your code is not required to check for incorrect inputs or incorrectly-formed input data. You must use the provided Java template as the basis of your submission. You may not change the name, return type, or parameters of the mst function. The main function in the template contains code to help you test your implementation by entering test data or reading it from a file. A sample file is also provided (see the comments in MST.java for the file format). You may modify the main function or any other function, because your submission will be tested using a different main function. Only the contents of the mst function and associated helper functions (if any) will be marked.
2 Evaluation Criteria The programming assignment will be marked out of 40, based on a combination of automated testing (using large graphs) and human inspection. You are to implement Kruskal’s algorithm, equipped with the Weighted Quick-Union version of Union-Find (which you also are to implement). If implemented correctly, therunningtimeofyourcodeshouldbe O(|E|log|V|). Themarksforeachsubmission will be based on both the asymptotic worst case running time and the ability of the algorithm to handle inputs of different sizes. The table below shows the expectations associated with different scores.
1
CSC 226: Problem Set 2
Score Description 0 - 15 Submission does not compile or does not conform to the provided template. 16 - 30 TheimplementedalgorithmisnotO(|E|log|V|)orissubstantially inaccurate on the tested inputs. 31 - 40 The implemented algorithm is O(|E|log|V|) and gives the correct answer on all tested inputs.
1 Programming Assignment
Theresa May, having just watched Shaun of the Dead, becomes worried that a zombie revoltisimminent. Shouldthishappen,anaturalfearisthatthezombieswillorganize clandestine meetings, pool their collective minimal brain power, and ultimately push for “Zexit” (Zombie Exit), thereby crippling the eponymous unity of the UK. Therefore, May creates the Ministry of Zombie Affairs, to be headed by Simon Pegg. Simon decides that the best way to prevent zombie meetings is by scrapping London’s current road network and replacing it with a network with the property that any two places are connected by precisely one path. This way, zombie drivers easily can be stopped using minimal blockades. Unfortunately, nearly all the funds required were spent on billboards warning of Zexit, and so Simon needs to construct a road network whose total length is minimal in order to minimize construction costs. More formally, the problem is described by the following Input and Output. Input: An edge-weighted graph G of n vertices. Each edge weight corresponds to the cost of constructing a road between two places in London. Output: The cost (sum of the edge weights) of the minimum-cost solution. A Java template has been provided containing an empty function mst. This function takes a two-dimensional integer array A that represents the weighted graph in the form of an adjacency matrix. This function returns the sum of the weights of the edges in a minimum spanning tree of G. Your task is to write the body of the mst function, which can include calls to helper functions that you write. Your code is not required to check for incorrect inputs or incorrectly-formed input data. You must use the provided Java template as the basis of your submission. You may not change the name, return type, or parameters of the mst function. The main function in the template contains code to help you test your implementation by entering test data or reading it from a file. A sample file is also provided (see the comments in MST.java for the file format). You may modify the main function or any other function, because your submission will be tested using a different main function. Only the contents of the mst function and associated helper functions (if any) will be marked.
2 Evaluation Criteria The programming assignment will be marked out of 40, based on a combination of automated testing (using large graphs) and human inspection. You are to implement Kruskal’s algorithm, equipped with the Weighted Quick-Union version of Union-Find (which you also are to implement). If implemented correctly, therunningtimeofyourcodeshouldbe O(|E|log|V|). Themarksforeachsubmission will be based on both the asymptotic worst case running time and the ability of the algorithm to handle inputs of different sizes. The table below shows the expectations associated with different scores.
1
CSC 226: Problem Set 2
Score Description 0 - 15 Submission does not compile or does not conform to the provided template. 16 - 30 TheimplementedalgorithmisnotO(|E|log|V|)orissubstantially inaccurate on the tested inputs. 31 - 40 The implemented algorithm is O(|E|log|V|) and gives the correct answer on all tested inputs.
1 file (219.6KB)
