Computer Science 320 – (2021)
Programming Assignment 2
Due: Sunday, August 15 2021 (NZT 11:59pm)
计算机科学作业代写 This second assignment lets you get familiar with the minimum spanning tree (MST) problem. We would like you to implement any fast algorithm
Requirements 计算机科学作业代写
This second assignment lets you get familiar with the minimum spanning tree (MST) problem. We would like you to implement any fast algorithm (Prim, Kruskal, or whatever MST solvers) for finding the minimum spanning tree from a sparse graph. An O(m log n) solution for m edges and n nodes is preferred since we have set the running time limit on the automated marker.
There are 3 sparse graphs whose sizes are different. The first one (L100) has 100 nodes, while the last largest one (L5000) comprises of 5000 nodes. It is worth 5% of your total course marks. The first (L100)and second (L1000) test cases have 2 marks each and the last has 1 mark. 计算机科学作业代写
In order to boost your performance, we have created an additional small test case, named L50, which does not contribute to the mark. It would help you to be familiar with reading input and printing output on the automated marker.
There will be a penalty if you exceed the submission limit of 8. Therefore, please test your imple- mentation with your own generated inputs before submitting to the automated marker.
Test case description 计算机科学作业代写
We use # for the comment and we have e.g. n = 5 to indicate the value n of number of nodes. Thenode index starts from 1. There is a whitespace after #, n, = to make the parsing process easily. 计算机科学作业代写
If there is an edge between two nodes x and y, there will be two lines with the format of x y w and y x w, where w is the weight of the edge between x and y. All weights w are non negative integers smaller than 1000. There is one whitespace between each integer on each line.
Sample Input:
# This is the a graph of n = 5. #
| n
# |
= | 5 |
| 1 | 2 | 1 |
| 1 | 3 | 3 |
| 1 | 4 计算机科学作业代写 | 4 |
| 1 | 5 | 5 |
| 2 计算机科学作业代写 | 1 | 1 |
| 2 | 3 | 2 |
| 3 | 1 | 3 |
| 3 | 2 | 2 计算机科学作业代写 |
| 4 | 1 | 4 |
| 5 | 1 | 5 |
You should output the weight of the minimum spanning tree, i.e. the sum of weights given to each edge of the spanning tree as follows:
Sample Output:
12
Submission Procedure 计算机科学作业代写
Submit your program solutions to https://www.automarker.cs.auckland.ac.nz. There will be a penalty of 20% (per test case) if you exceed the submission limit of 8 for each test case (applied if you eventually solve them).
其他代写：代写CS C++代写 java代写 matlab代写 web代写 作业代写 物理代写 数学代写 考试助攻 paper代写 金融经济统计代写 python代写 app代写 r代写
