# Quiz Week11

.docx
Question 1 1 out of 1 points Consider this instance of the knapsack problem. We have a total capacity W = 12 and six items, with weights and values as follows: item \weight \value 1 3 20 2 2 15 3 3 25 4 4 30 - 5 5 30 6 6 50 The dynamic programming algorithm will establish that the optimal value that can be achieved for this instance is: Selected Answer: 95 Response Feedback: Yes, that's right. Items 2, 4 and 6 will be selected. Question 2 1 out of 1 points A connected weighted undirected graph G has 57 nodes and 194 edges. How many edges does a minimum spanning tree for G have? Selected Answer: 56 Response Feedback: Yes, too easy. For a connected undirected graph <V,E>, any spanning tree has |V|-1 edges. Question 3 1 out of 1 points Consider the graph below. What is the cost of its minimum spanning tree, that is, the sum of its edges' weights? 6 N8 |2 Selected Answer: 12 Response Feedback: You got that right! Question 4 1 out of 1 points Consider the graph below. How many different minimum spanning trees does it have? O——0——0—@ 1225457 @—@—F—O@—® Selected Answer: 2 Response Feedback: Yes, correct. Friday, 9 June 2017 6:51:29 PM AEST
Uploaded by BailiffRhinocerosMaster952 on coursehero.com