|
网址：http://www.daixiec.com/ QQ：2365427650 代写程序 C C++ Java KXT201 Algorithms Second (Indiyidual) Assignment 2009Standard LevelDue: 3pm 28th MayMaximum Minimum Spanning TreeIntroductionWhen Prim's algorithm is applied to a connected undirected graph, it computes (the weightof) a minimum weight spanning tree. For this assignment you need to adapt andimplement Prim's algorithm such that when applied to a connected undirected graph itcomputes (as usual) the weight of a minimum weight spanning tree for the graph, andwhen applied to an unconnected undirected graph it computes the maximum of the weightsof the minimum weight spanning trees for the graph's connected components. Forexample, for the graph below, the weights of the minimum weight spanning trees of theconnected components are (from left to right) 0 {a}, 5 {b, f, g}, 5 {c, d} and 3 {e, h, i},and the maximum of those values is 5, so this is the value to be computed.Hint about the adaptation: if you consider what happens when you apply the originalalgorithm to an unconnected graph, you will notice that when all the vertices in theconnected component of the starting vertex have become "known", the "nearest unknown"vertex, which is in a different connected component, is at distance "infinity". (Note: whenvertices tie to be "nearest unknown", you may break the tie as you wish.)Similarly to the first assignment, this assignment, which is worth 12% of the unit mark,and marked out of 24, can be attempted at two different levels – "standard" level, worth upto 21 marks, and "challenge" level, which includes the standard level and is worth up to 3more marks.The standard level assignment is described here and the additional work for the challengelevel is described in a supplement.The GraphThe graph will be a weighted undirected graph, with at least 1 vertex, and at most 10000vertices, and at most 99999 edges. Vertices will be numbered 0, 1, 2, ...V-1, for a graphwith V vertices. Edge weights will be integers, each at least 0, and at most 1000. (Note thatthe number of vertices and the edge weight limits affect the choice of an appropriate valuefor "infinity" in the implementation.) The graph must be represented as required below, theinput read as required below, and the output produced as required below. (The input willbe correct, and no extra marks will be given for handling incorrect input.)a b cf gd eh i2 453 23 1TestingPrograms will be tested automatically on alacritas / lawson similarly to the firstassignment and marks for each test will be awarded on a pass/fail basis.System AvailabilityExperience shows that, unfortunately, the computer system will probably be unavailable orpractically unusable for much of the 72 hours before the deadline. This is not anunforeseeable misfortune of the type that might justify a request for an assignmentextension.Data Structure RequirementsThe graph must be represented in an adjacency list form, with the implementation of thelists bbsed upon the dummy header linked list code of the weekly work, modified as littleas required. Each node in an adjacency list must be represented by a dynamically allocatedstruct of a type defined (with associated pointer type) as follows:typedef struct node *node_ptr;struct node{ int to_vertex; int weight; node_ptr next;};where (except for the dummy header node for which the first two items are irrelevant):to_vertex is the vertex to which the edge goes;weight is the weight of the edge;next is the pointer to the next node (/ NULL if this is the last node in the list).The adjacency list representation of the graph edges must be an array of size 10000 of(pointers to the header nodes of) such lists, e.g.:node_ptr g[10000];(In addition to the representation of the graph, an int array of distances will be needed forthe standard level assignment. It will be acceptable for this to be either of a fixed size of10000, or dynamically allocated to be of the right size for the number of vertices. Similarlyfor a “known” array if you choose to have one. )O() Running Time RequirementsThe running time of your program (not just the Prim's part) must be at most O(V2) for agraph with V vertices. Note:a) You can assume that no indiyidual pair of vertices has more than one undirected edgewith this pair of vertices as the endpoints.b) You can assume that each call to any of scanf, printf, malloc and free takes time that isO(1).c) Although the number of vertices is limited to 10000, and the number of edges to 99999,the existence of these limits must be ignored for the purposes of the O() running timerequirements.d) You do not need to make any special effort to have good constants in the running timeof your code, but equally, you must not make any effort to make it excessively inefficientin constant terms – the marker will limit the length of time for which they wait for a test tocomplete.Input and OutputInput must be read with scanf() and output written with printf(). The input will containonly what is described here, e.g. there will be no spaces other than those mentioned. Theoutput should contain only the maximum weight on a line by itself, e.g. given the answeranswer, print it as follows:printf("%dn", answer);The input will start with a line containing an integer specifying the number of vertices, aspace, then an integer specifying the number of edges. Then, there will be a series of lines,one per (undirected) edge. Each such line will contain three integers, with a space betweenthe first and second, and a space between the second and third. The first integer will be theweight of the edge. The second integer will be the lower numbered of the vertices at theends of the edge. The third integer will be the higher numbered of the vertices at the endsof the edge. The edges will be in descending order of higher numbered vertex, with edgesof equal higher numbered vertex in descending order of lower numbered vertex.The following input describes the graph of the Introduction, with vertex a becoming vertexnumber 0, vertex b becoming vertex number 1, ... vertex i becoming vertex number 8:9 72 7 83 4 81 4 73 5 64 1 62 1 55 2 3The corresponding output would be:5Submission of the AssignmentSimilarly to the first assignment, you must submit electronically the source files, anappropriate README (plain text, with your name, your student ID number, and anappropriate brief descripqion of your solution), and a completed electronic indiyidualassignment cover sheet. However, the relevant directory is now named Standard2, and thesubmit command is:kxt201-submit2(As mentioned in the first assignment it is possible to re-submit electronically if thisproves necessary.)AssessmentThe marker will assess your assignment as follows:1. The marker will extract the files from your submission. If the files are present whererequired, including a correctly named README file of the right form, with the rightinformation, this will be worth 2 marks.2. The marker will attempt to compile (and link) your submission (unaltered) using(exactly) the following command:gcc –Wall –ansi –pedantic –O *.cIf this produces the assignment executable, a.out, without any warnings (or errors), thiswill be worth 4 marks. If you do not get the 4 marks, but the marker is able to compile(and link) your submission (unaltered), as C, using gcc, to produce an a.out, this will beworth 1 mark.3. The marker will read your code. If it is easily readable and understandable, as isrequired, and your code appears to make a serious attempt to implement at least anunadapted Prim's algorithm, using the required data structures, they will assess the codestyle in general, such as readability or comprehensibility beyond minimum, out of 4marks. For example, your use of indentation and blank lines will affect readability. (Youshould assume that the readability is judged in terms of what the code looks like, whenread with the "more" command, with standard tab settings of width 8.) Similarly your useof comments, choice of variable and function names, diyision of code into functions, anddiyision of functions between files will affect comprehensibility.4. If you have used the required data structures, and the marker has been able to compile(and link) your code (unaltered) as C, using gcc, they will then assess code functionalityby running your code on those tests for which you appear to have made a serious attemptto implement the relevant computation bbsed upon Prim's algorithm. (An unaltered Prim'sis sufficient for Tests 1 and 2.) As shown in the table below, the marks obtained forpassing a test depend upon whether you have met the O() running time requirements. (Astests are time limited, failing to meet running time requirements could cause a test to befailed.)Test 1(The graph ofthe weeklywork Prim'sexample)Test 2(Anotherconnectedgraph)Test 3(The examplegraph ofearlier)Test 4(Anotherunconnectedgraph)Passing withboth requiredDataStructures andO()4 marks 2 marks 2 marks 2 marksPassing withrequired DataStructures, butnot O()2 marks 1 mark 1 mark 1 mark5. If it appears to the marker that your code might obtain more marks for functionality if atrivial mistake were corrected (e.g. the code fails all tests because there is an additionalspace being printed in the printf), then they will correct the mistake and retest, awardingyou half of any additional marks obtained as a result of their work. (You should not counton the marker getting right in a couple of minutes something that you have got wrong overa much longer period of time!)6. If your code as submitted uses the required data structures, is bbsed upon Prim'salgorithm, meets all the O() requirements, and passes all tests, the marker will checkwhether all dynamically allocated memory is correctly explicitly freed before the programterminates, if so, this will be worth 1 mark.Assignment Indiyiduality / Assignment Specification Clarifications /Advice On Doing A Programming AssignmentThe general remarks of the first assignment apply.
|
手机签到经验翻倍！
