// Numbas version: exam_results_page_options
{"name": "Prim's algorithm", "extensions": ["graph-theory"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Prim's algorithm", "tags": [], "metadata": {"description": "<p>The student is given a connected graph and must find a minimum spanning tree.</p>", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "<p>$G$ is a graph with {len(vertices(g))} vertices.</p>\n<p>{max_height(30,max_width(30,draw(g)))}</p>\n<p>The table below gives the weights of the edges in $G$:</p>\n<p>{weight_table(g)}</p>", "advice": "<p>{prims_algorithm_working(g)}</p>", "rulesets": {}, "extensions": ["graph-theory"], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"g": {"name": "g", "group": "Ungrouped variables", "definition": "let(\n  vertices, vertices(unweighted_g),\n  weights,map(round(len(vertices[from(e)]-vertices[to(e)])),e,edges(unweighted_g)),\n  \n  set_edge_weights(unweighted_g,weights)\n)\n", "description": "", "templateType": "anything", "can_override": false}, "vertex_labels": {"name": "vertex_labels", "group": "Ungrouped variables", "definition": "map(upper(letterordinal(i)),i,0..n-1)", "description": "", "templateType": "anything", "can_override": false}, "n": {"name": "n", "group": "Ungrouped variables", "definition": "7", "description": "", "templateType": "anything", "can_override": false}, "min_spanning_tree": {"name": "min_spanning_tree", "group": "Ungrouped variables", "definition": "map(ends(e),e,prims_algorithm(g))", "description": "", "templateType": "anything", "can_override": false}, "min_spanning_tree_marking_matrix": {"name": "min_spanning_tree_marking_matrix", "group": "Ungrouped variables", "definition": "map(\n  map(\n    award(1,[x,y] in min_spanning_tree or [y,x] in min_spanning_tree),\n    x,\n    0..n-1\n  ),\n  y,\n  0..n-1\n)", "description": "", "templateType": "anything", "can_override": false}, "minimal_weight": {"name": "minimal_weight", "group": "Ungrouped variables", "definition": "sum(map(award(weight_matrix[x][y],[x,y] in min_spanning_tree), [x,y], product(0..n,2)))", "description": "", "templateType": "anything", "can_override": false}, "weight_matrix": {"name": "weight_matrix", "group": "Ungrouped variables", "definition": "weight_matrix(g)", "description": "", "templateType": "anything", "can_override": false}, "unweighted_g": {"name": "unweighted_g", "group": "Ungrouped variables", "definition": "let(g,random_planar_graph(n),\n  auto_layout(\n    set_vertex_labels(g,\n      vertex_labels\n    )\n  )\n)", "description": "", "templateType": "anything", "can_override": false}, "entry_layout": {"name": "entry_layout", "group": "Ungrouped variables", "definition": "let(\n  a,adjacency_matrix(g),\n  map(\n    map(i>j and a[i][j]>0, j, 0..n),\n    i,\n    0..n\n  )\n)", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["n", "vertex_labels", "g", "min_spanning_tree", "min_spanning_tree_marking_matrix", "weight_matrix", "minimal_weight", "unweighted_g", "entry_layout"], "variable_groups": [], "functions": {}, "preamble": {"js": "", "css": ".graph { min-height: 10em; }"}, "parts": [{"type": "m_n_x", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "student_weight: sum(map(award(weight_matrix[x][y],studentAnswer[x][y]), [x,y], tick_indexes))\n\nstudent_graph: graph(matrix(map(map(award(1,x),x,row),row,studentAnswer)), vertices(g))\n\nstudent_graph_is_connected:\n  assert(is_connected(student_graph), \n    incorrect(\"Your graph is not a spanning tree.\");\n    end()\n  )\n\nmark:\n  feedback(\"Here's your graph:\");\n  feedback(draw(student_graph));\n  apply(student_graph_is_connected);\n  if(student_weight <= minimal_weight,\n    correct()\n  ,\n    add_credit(1/6, \"The weight of your tree is {student_weight}. You could do better.\")\n  )", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Find a minimum spanning tree for $G$.</p>\n<p>For each edge in your minimum spanning tree, tick the box corresponding to the vertices that the edge joins.</p>", "minMarks": 0, "maxMarks": "6", "minAnswers": 0, "maxAnswers": 0, "shuffleChoices": false, "shuffleAnswers": false, "displayType": "checkbox", "warningType": "none", "showCellAnswerState": false, "markingMethod": "all-or-nothing", "choices": "vertex_labels", "matrix": "min_spanning_tree_marking_matrix", "layout": {"type": "expression", "expression": "entry_layout"}, "answers": "vertex_labels"}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}