// Numbas version: exam_results_page_options
{"name": "Graph theory questions", "metadata": {"description": "<p>These are some questions on graph theory, pulled from a module on groups and graphs.</p>", "licence": "Creative Commons Attribution 4.0 International"}, "duration": 0, "percentPass": 0, "showQuestionGroupNames": false, "shuffleQuestionGroups": false, "showstudentname": true, "question_groups": [{"name": "Group", "pickingStrategy": "all-ordered", "pickQuestions": 1, "questionNames": ["", "Match adjacency matrix to a graph", "Write the adjacency matrix of this graph", ""], "variable_overrides": [[], [], [], []], "questions": [{"name": "Are these graphs isomorphic?", "extensions": ["graph-theory", "permutations"], "custom_part_types": [{"source": {"pk": 2, "author": {"name": "Christian Lawson-Perfect", "pk": 7}, "edit_page": "/part_type/2/edit"}, "name": "List of numbers", "short_name": "list-of-numbers", "description": "<p>The answer is a comma-separated list of numbers.</p>\n<p>The list is marked correct if each number occurs the same number of times as in the expected answer, and no extra numbers are present.</p>\n<p>You can optionally treat the answer as a set, so the number of occurrences doesn't matter, only whether each number is included or not.</p>", "help_url": "", "input_widget": "string", "input_options": {"correctAnswer": "join(\n  if(settings[\"correctAnswerFractions\"],\n    map(let([a,b],rational_approximation(x), string(a/b)),x,settings[\"correctAnswer\"])\n  ,\n    settings[\"correctAnswer\"]\n  ),\n  settings[\"separator\"] + \" \"\n)", "hint": {"static": false, "value": "if(settings[\"show_input_hint\"],\n  \"Enter a list of numbers separated by <code>{settings['separator']}</code>.\",\n  \"\"\n)"}, "allowEmpty": {"static": true, "value": true}}, "can_be_gap": true, "can_be_step": true, "marking_script": "bits:\nlet(b,filter(x<>\"\",x,split(studentAnswer,settings[\"separator\"])),\n    if(isSet,list(set(b)),b)\n)\n\nexpected_numbers:\nlet(l,settings[\"correctAnswer\"] as \"list\",\n    if(isSet,list(set(l)),l)\n)\n\nvalid_numbers:\nif(all(map(not isnan(x),x,interpreted_answer)),\n    true,\n    let(index,filter(isnan(interpreted_answer[x]),x,0..len(interpreted_answer)-1)[0], wrong, bits[index],\n      warn(wrong+\" is not a valid number\");\n      fail(wrong+\" is not a valid number.\")\n    )\n  )\n\nis_sorted:\nassert(sort(interpreted_answer)=interpreted_answer,\n    multiply_credit(0.5,\"Not in order\")\n  )\n\nincluded:\nmap(\n      let(\n        num_student,len(filter(x=y,y,interpreted_answer)),\n        num_expected,len(filter(x=y,y,expected_numbers)),\n        switch(\n          num_student=num_expected,\n            true,\n          num_student<num_expected,\n            incorrect(\n              if(isSet,\"Your answer does not contain \"+x+\" but should.\",\n                \"Your answer does not contain \"+x+\" enough times.\"\n              )\n            );false\n          ,\n            incorrect(\n              if(isSet,\"Your answer contains \"+x+\" but should not.\",\n                \"Your answer contains \"+x+\" too many times.\"\n              )\n            );false\n        )\n      )\n      ,\n      x,\n      sort(list(set(expected_numbers)))\n  )\n\nall_included:\nall(included)\n\nno_extras:\nif(all(map(x in expected_numbers, x, interpreted_answer)),\n    true\n  ,\n    incorrect(\"Your answer contains \"+extra_numbers[0]+\" but should not.\");\n    false\n  )\n\ninterpreted_answer:\nif(lower(studentAnswer) in [\"empty\",\"\u2205\"],[],\n  map(\n    if(settings[\"allowFractions\"],parsenumber_or_fraction(x,notationStyles), parsenumber(x,notationStyles))\n    ,x\n    ,bits\n  )\n)\n\nmark:\nif(studentanswer=\"\",fail(\"You have not entered an answer\"),false);\napply(valid_numbers);\napply(included);\napply(no_extras);\ncorrectif(all_included and no_extras)\n\nnotationStyles:\n[\"en\"]\n\nisSet:\nsettings[\"isSet\"]\n\nextra_numbers:\nfilter(not (x in expected_numbers),x,interpreted_answer)", "marking_notes": [{"name": "bits", "description": "<p>The separate items in the student's answer</p>", "definition": "let(b,filter(x<>\"\",x,split(studentAnswer,settings[\"separator\"])),\n    if(isSet,list(set(b)),b)\n)"}, {"name": "expected_numbers", "description": "", "definition": "let(l,settings[\"correctAnswer\"] as \"list\",\n    if(isSet,list(set(l)),l)\n)"}, {"name": "valid_numbers", "description": "<p>Is every number in the student's list valid?</p>", "definition": "if(all(map(not isnan(x),x,interpreted_answer)),\n    true,\n    let(index,filter(isnan(interpreted_answer[x]),x,0..len(interpreted_answer)-1)[0], wrong, bits[index],\n      warn(wrong+\" is not a valid number\");\n      fail(wrong+\" is not a valid number.\")\n    )\n  )"}, {"name": "is_sorted", "description": "<p>Are the student's answers in ascending order?</p>", "definition": "assert(sort(interpreted_answer)=interpreted_answer,\n    multiply_credit(0.5,\"Not in order\")\n  )"}, {"name": "included", "description": "<p>Is each number in the expected answer present in the student's list the correct number of times?</p>", "definition": "map(\n      let(\n        num_student,len(filter(x=y,y,interpreted_answer)),\n        num_expected,len(filter(x=y,y,expected_numbers)),\n        switch(\n          num_student=num_expected,\n            true,\n          num_student<num_expected,\n            incorrect(\n              if(isSet,\"Your answer does not contain \"+x+\" but should.\",\n                \"Your answer does not contain \"+x+\" enough times.\"\n              )\n            );false\n          ,\n            incorrect(\n              if(isSet,\"Your answer contains \"+x+\" but should not.\",\n                \"Your answer contains \"+x+\" too many times.\"\n              )\n            );false\n        )\n      )\n      ,\n      x,\n      sort(list(set(expected_numbers)))\n  )"}, {"name": "all_included", "description": "<p>Has every number been included the right number of times?</p>", "definition": "all(included)"}, {"name": "no_extras", "description": "<p>True if the student's list doesn't contain any numbers that aren't in the expected answer.</p>", "definition": "if(all(map(x in expected_numbers, x, interpreted_answer)),\n    true\n  ,\n    incorrect(\"Your answer contains \"+extra_numbers[0]+\" but should not.\");\n    false\n  )"}, {"name": "interpreted_answer", "description": "A value representing the student's answer to this part.", "definition": "if(lower(studentAnswer) in [\"empty\",\"\u2205\"],[],\n  map(\n    if(settings[\"allowFractions\"],parsenumber_or_fraction(x,notationStyles), parsenumber(x,notationStyles))\n    ,x\n    ,bits\n  )\n)"}, {"name": "mark", "description": "This is the main marking note. It should award credit and provide feedback based on the student's answer.", "definition": "if(studentanswer=\"\",fail(\"You have not entered an answer\"),false);\napply(valid_numbers);\napply(included);\napply(no_extras);\ncorrectif(all_included and no_extras)"}, {"name": "notationStyles", "description": "", "definition": "[\"en\"]"}, {"name": "isSet", "description": "<p>Should the answer be considered as a set, so the number of times an element occurs doesn't matter?</p>", "definition": "settings[\"isSet\"]"}, {"name": "extra_numbers", "description": "<p>Numbers included in the student's answer that are not in the expected list.</p>", "definition": "filter(not (x in expected_numbers),x,interpreted_answer)"}], "settings": [{"name": "correctAnswer", "label": "Correct answer", "help_url": "", "hint": "The list of numbers that the student should enter. The order does not matter.", "input_type": "code", "default_value": "", "evaluate": true}, {"name": "allowFractions", "label": "Allow the student to enter fractions?", "help_url": "", "hint": "", "input_type": "checkbox", "default_value": false}, {"name": "correctAnswerFractions", "label": "Display the correct answers as fractions?", "help_url": "", "hint": "", "input_type": "checkbox", "default_value": false}, {"name": "isSet", "label": "Is the answer a set?", "help_url": "", "hint": "If ticked, the number of times an element occurs doesn't matter, only whether it's included at all.", "input_type": "checkbox", "default_value": false}, {"name": "show_input_hint", "label": "Show the input hint?", "help_url": "", "hint": "", "input_type": "checkbox", "default_value": true}, {"name": "separator", "label": "Separator", "help_url": "", "hint": "The substring that should separate items in the student's list", "input_type": "string", "default_value": ",", "subvars": false}], "public_availability": "always", "published": true, "extensions": []}, {"source": {"pk": 197, "author": {"name": "Christian Lawson-Perfect", "pk": 7}, "edit_page": "/part_type/197/edit"}, "name": "Write a permutation in two-line form", "short_name": "write-a-permutation-in-two-line-form", "description": "<p>The student must write out a permutation (an element of $S_n$) in two-line form: the top line always contains the numbers 1 to $n$, and on the bottom line they must write the numbers that they are mapped to.</p>", "help_url": "", "input_widget": "matrix", "input_options": {"correctAnswer": "matrix(map(settings[\"correctAnswer\"][i],i,1..settings[\"size\"]))", "hint": {"static": true, "value": ""}, "allowResize": {"static": true, "value": false}, "numRows": {"static": true, "value": 1}, "numColumns": {"static": false, "value": "settings[\"size\"]"}, "parseCells": {"static": true, "value": true}, "allowedNotationStyles": {"static": true, "value": ["plain"]}, "allowFractions": {"static": true, "value": false}, "showBrackets": {"static": true, "value": true}, "rowHeaders": {"static": false, "value": "[]"}, "columnHeaders": {"static": false, "value": "map(string(n),n,1..settings[\"size\"])"}}, "can_be_gap": true, "can_be_step": true, "marking_script": "mark:\napply(valid_permutation);\ncorrectif(student_permutation=settings[\"correctAnswer\"])\n\nstudent_numbers:\nlist(studentAnswer[0])\n\nstudent_permutation:\npermutation(map(x-1,x,student_numbers))\n\nvalid_permutation:\n  assert(all(map(isint(x) and x>=1 and x<=settings[\"size\"], x, student_numbers)),\n    fail(\"Your answer is not a valid permutation: each entry must be one of the numbers 1 \u2026 {settings['size']}.\")\n  );\n  assert(len(set(student_numbers))=settings[\"size\"],\n    fail(\"Your answer is not a valid permutation: some entries occur more than once.\")\n  )\n\ninterpreted_answer:\nstudent_permutation", "marking_notes": [{"name": "mark", "description": "This is the main marking note. It should award credit and provide feedback based on the student's answer.", "definition": "apply(valid_permutation);\ncorrectif(student_permutation=settings[\"correctAnswer\"])"}, {"name": "student_numbers", "description": "<p>The numbers that the student typed.</p>", "definition": "list(studentAnswer[0])"}, {"name": "student_permutation", "description": "", "definition": "permutation(map(x-1,x,student_numbers))"}, {"name": "valid_permutation", "description": "", "definition": "  assert(all(map(isint(x) and x>=1 and x<=settings[\"size\"], x, student_numbers)),\n    fail(\"Your answer is not a valid permutation: each entry must be one of the numbers 1 \u2026 {settings['size']}.\")\n  );\n  assert(len(set(student_numbers))=settings[\"size\"],\n    fail(\"Your answer is not a valid permutation: some entries occur more than once.\")\n  )"}, {"name": "interpreted_answer", "description": "A value representing the student's answer to this part.", "definition": "student_permutation"}], "settings": [{"name": "correctAnswer", "label": "Correct answer", "help_url": "", "hint": "", "input_type": "code", "default_value": "", "evaluate": true}, {"name": "size", "label": "Size", "help_url": "", "hint": "", "input_type": "code", "default_value": "", "evaluate": true}], "public_availability": "always", "published": true, "extensions": []}, {"source": {"pk": 1, "author": {"name": "Christian Lawson-Perfect", "pk": 7}, "edit_page": "/part_type/1/edit"}, "name": "Yes/no", "short_name": "yes-no", "description": "<p>The student is shown two radio choices: \"Yes\" and \"No\". One of them is correct.</p>", "help_url": "", "input_widget": "radios", "input_options": {"correctAnswer": "if(eval(settings[\"correct_answer_expr\"]), 0, 1)", "hint": {"static": true, "value": ""}, "choices": {"static": true, "value": ["Yes", "No"]}}, "can_be_gap": true, "can_be_step": true, "marking_script": "mark:\nif(studentanswer=correct_answer,\n  correct(),\n  incorrect()\n)\n\ninterpreted_answer:\nstudentAnswer=0\n\ncorrect_answer:\nif(eval(settings[\"correct_answer_expr\"]),0,1)", "marking_notes": [{"name": "mark", "description": "This is the main marking note. It should award credit and provide feedback based on the student's answer.", "definition": "if(studentanswer=correct_answer,\n  correct(),\n  incorrect()\n)"}, {"name": "interpreted_answer", "description": "A value representing the student's answer to this part.", "definition": "studentAnswer=0"}, {"name": "correct_answer", "description": "", "definition": "if(eval(settings[\"correct_answer_expr\"]),0,1)"}], "settings": [{"name": "correct_answer_expr", "label": "Is the answer \"Yes\"?", "help_url": "", "hint": "An expression which evaluates to <code>true</code> or <code>false</code>.", "input_type": "mathematical_expression", "default_value": "true", "subvars": false}], "public_availability": "always", "published": true, "extensions": []}], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Sam Mutter", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/9360/"}], "tags": [], "metadata": {"description": "<p>The student is shown two labelled graphs. They are asked:</p>\n<ul>\n<li>Number of vertices in each</li>\n<li>Number of edges in each</li>\n<li>Degree sequences for each</li>\n<li>Is there an isomorphism between them? If so, write one.</li>\n</ul>\n<p>The number of vertices is always equal, so this is a gimme.</p>\n<p>If the edges or degree sequences are different, the student is expected to realise that there cannot be an isomorphism.</p>\n<p>If these values are the same, then there will be an isomorphism (else the question is a bit too tricky).</p>\n<p>Numbas expects a particular isomorphism, but there may be more than one, all of which would be accepted.</p>", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "<p>Consider the following labelled graphs, and their adjacency matrices:</p>\n<table style=\"width: 600px; height: 36px;\">\n<tbody>\n<tr style=\"height: 18px;\">\n<td style=\"text-align: center; width: 285.85px; height: 18px;\">$\\Gamma_1$</td>\n<td style=\"text-align: center; width: 281.15px; height: 18px;\">$\\Gamma_2$</td>\n</tr>\n<tr style=\"height: 18px;\">\n<td style=\"text-align: center; width: 285.85px; height: 18px;\">{draw(g1)}</td>\n<td style=\"text-align: center; width: 281.15px; height: 18px;\">{draw(g2)}</td>\n</tr>\n<tr>\n<td style=\"text-align: center; width: 285.85px;\">$\\var{adjacency_matrix(g1)}$</td>\n<td style=\"text-align: center; width: 281.15px;\">$\\var{adjacency_matrix(g2)}$</td>\n</tr>\n<tr>\n<td style=\"text-align: center; width: 285.85px;\"></td>\n<td style=\"text-align: center; width: 281.15px;\"></td>\n</tr>\n</tbody>\n</table>\n<p></p>", "advice": "<p>The <strong>vertices</strong> are the labelled \"dots\". In each graph there are {n+1} vertices.</p>\n<p>The <strong>edges</strong> are the lines connecting vertices. In $\\Gamma_1$ there are {len(edges(g1))} edges, and in $\\Gamma_2$ there are {len(edges(g2))}.</p>\n<p>The <strong>degree </strong>of a vertex is the number of edges incident to it.</p>\n<p>The <strong>degree sequence </strong>is a list of the degrees of all of the vertices of a graph, usually ordered from smallest to largest. The degree sequence of $\\Gamma_1$ is {join(sort(vertex_degrees(g1)),\", \")}.</p>\n<p>Similarly, the degree sequence of $\\Gamma_2$ is {join(sort(vertex_degrees(g2)),\", \")}. This is because, for example, {len(filter(i=2, i, vertex_degrees(g2)))} of the vertices in $\\Gamma_2$ have degree 2, {len(filter(i=3, i, vertex_degrees(g2)))} of the vertices in $\\Gamma_2$ have degree 3, and so on.</p>\n<p>Two graphs $\\Gamma_1, \\Gamma_2$ are isomorphic if there is a bijection from the vertex set of $\\Gamma_1$ to the vertex set of $\\Gamma_2$ that maps a pair of vertices joined by an edge to a pair of vertices joined by an edge, and that maps a pair of vertices not joined by an edge to a pair of vertices not joined by an edge. If there is no such bijection then the graphs are not isomorphic.</p>\n<p><strong>There cannot be a graph isomorphism </strong>between two graphs if they have different numbers of vertices, different numbers of edges, or different degree sequences.</p>\n<p>{advice}</p>", "rulesets": {}, "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"g1": {"name": "g1", "group": "Ungrouped variables", "definition": "set_vertex_labels( graph(map(edge(from,to),[from,to],\n  [[0,1],[0,2]+[0,n-2],[0,n-1]]+\n  flatten(map(map([j,k],k,shuffle(j+1..n-1)[0..random(1,2)]),j,1..n-1))\n)), map(string(x),x,1..n))", "description": "<p>The graph $\\Gamma_1$.</p>\n<p>Vertex 1 will be adjacent to four others.</p>\n<p>The remaining vertices will each be adjacent to either one or two later vertices.</p>\n<p>In this way, no vertex will be adjacent to more than four others.</p>", "templateType": "anything", "can_override": false}, "n": {"name": "n", "group": "Ungrouped variables", "definition": "random(6..8)", "description": "<p>Each graph will contain n vertices.</p>", "templateType": "anything", "can_override": false}, "vertex_perm": {"name": "vertex_perm", "group": "Ungrouped variables", "definition": "perm(shuffle(0..n-1))", "description": "<p>The vertices of graph 2 will be mapped by this permutation to those of graph 1.</p>", "templateType": "anything", "can_override": false}, "diff_degree": {"name": "diff_degree", "group": "Ungrouped variables", "definition": "let(\n  degrees, vertex_degrees(g1),\n  d, max(degrees),\n  v, indices(degrees,d)[0],\n  edges, edges(g1),\n  e, random(filter(not (v in ends(e)),e,edges)),\n  nedges,map(if(e2=e,edge(v,to(e)),e2),e2,edges),\n  graph(nedges)\n)", "description": "<p>Take g1 and find the vertex $v$ with highest degree. Move an edge connecting two other vertices so that one end is on $v$ instead. This changes the degree sequence, so produces a graph not isomorphic to g1.</p>", "templateType": "anything", "can_override": false}, "fewer_edges": {"name": "fewer_edges", "group": "Ungrouped variables", "definition": "let(\n  edges, edges(g1),\n  degrees,vertex_degrees(g1),\n  ok_edges,filter(degrees[from(e)]>1 and degrees[to(e)]>1,e,edges),\n  e,random(ok_edges),\n  graph(filter(e2<>e,e2,edges))\n)", "description": "<p>Remove an edge from g1 to produce a non-isomorphic graph. Only edges connecting vertices with degree at least 2 are considered, so the graph remains connected.</p>", "templateType": "anything", "can_override": false}, "g2": {"name": "g2", "group": "Ungrouped variables", "definition": "set_vertex_labels(\n  auto_layout(permute_vertices(\n    vertex_perm, \n    if(is_isomorphic,\n      graph(edges(g1)),\n      random(diff_degree, fewer_edges)\n    )\n  ))\n  ,\n  map(string(x),x,1..n)\n)", "description": "<p>The graph $\\Gamma_2$. If it should be isomorphic, just take g1, otherwise pick from the non-isomorphic options.</p>\n<p>Permute the vertices according to the permutation vertex_perm, and lay the vertices out again.</p>", "templateType": "anything", "can_override": false}, "advice_none": {"name": "advice_none", "group": "Ungrouped variables", "definition": "\"<p>Therefore there is no isomorphism between $\\\\Gamma_1$ and $\\\\Gamma_2$.</p>\"", "description": "<p>The advice shown if the graphs are not isomorphic.</p>", "templateType": "long string", "can_override": false}, "advice_isomorphism": {"name": "advice_isomorphism", "group": "Ungrouped variables", "definition": "\"<p>Since these are all the same for $\\\\Gamma_1$ and $\\\\Gamma_2$, we might be able to find an isomorphism. Indeed, we can map vertex 1 of $\\\\Gamma_1$ to vertex {vertex_perm[1]} of $\\\\Gamma_2$, we can map vertex 2 to vertex {vertex_perm[2]}, vertex 3 to vertex {vertex_perm[3]}, and so on. Therefore a valid isomorphism is</p>\\n<p>\\\\[ \\\\var{twoline(vertex_perm)} \\\\]</p>\\n<p>(Note: there may be more than one isomorphism.)</p>\"", "description": "<p>The advice shown if the graphs are isomorphic.</p>", "templateType": "long string", "can_override": false}, "advice": {"name": "advice", "group": "Ungrouped variables", "definition": "if(is_isomorphic, advice_isomorphism, advice_none)", "description": "<p>The final line of the advice, describing the isomorphism if there is one, or stating that there is none.</p>", "templateType": "anything", "can_override": false}, "is_isomorphic": {"name": "is_isomorphic", "group": "Ungrouped variables", "definition": "random(true,false)", "description": "<p>Should $\\Gamma_1$ and $\\Gamma_2$ be isomorphic?</p>", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["is_isomorphic", "n", "g1", "diff_degree", "fewer_edges", "g2", "vertex_perm", "advice_none", "advice_isomorphism", "advice"], "variable_groups": [], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Compare the properties of $\\Gamma_1$ and $\\Gamma_2$.</p>\n<table style=\"height: 59px;\">\n<tbody>\n<tr style=\"height: 18px;\">\n<td style=\"height: 18px; width: 96.8333px;\"></td>\n<td style=\"height: 18px; width: 185.283px;\">Number of vertices</td>\n<td style=\"height: 18px; width: 171.7px;\">Number of edges</td>\n<td style=\"height: 18px; width: 251.917px;\">Degree sequence</td>\n</tr>\n<tr style=\"height: 23px;\">\n<td style=\"height: 23px; width: 96.8333px;\">$\\Gamma_1$</td>\n<td style=\"height: 23px; width: 185.283px;\">[[0]]</td>\n<td style=\"height: 23px; width: 171.7px;\">[[2]]</td>\n<td style=\"height: 23px; width: 251.917px;\">[[4]]</td>\n</tr>\n<tr style=\"height: 18px;\">\n<td style=\"height: 18px; width: 96.8333px;\">$\\Gamma_2$</td>\n<td style=\"height: 18px; width: 185.283px;\">[[1]]</td>\n<td style=\"height: 18px; width: 171.7px;\">[[3]]</td>\n<td style=\"height: 18px; width: 251.917px;\">[[5]]</td>\n</tr>\n</tbody>\n</table>", "gaps": [{"type": "numberentry", "useCustomName": true, "customName": "Vertices in $\\Gamma_1$", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "len(vertices(g1))", "maxValue": "len(vertices(g1))", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": true, "customName": "Vertices in $\\Gamma_2$", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "len(vertices(g2))", "maxValue": "len(vertices(g2))", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": true, "customName": "Edges in $\\Gamma_1$", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "len(edges(g1))", "maxValue": "len(edges(g1))", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": true, "customName": "Edges in $\\Gamma_2$", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "len(edges(g2))", "maxValue": "len(edges(g2))", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "list-of-numbers", "useCustomName": true, "customName": "Degree sequence of $\\Gamma_1$", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "settings": {"correctAnswer": "sort(vertex_degrees(g1))", "allowFractions": false, "correctAnswerFractions": false, "isSet": false, "show_input_hint": false}}, {"type": "list-of-numbers", "useCustomName": true, "customName": "Degree sequence of $\\Gamma_2$", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "settings": {"correctAnswer": "sort(vertex_degrees(g2))", "allowFractions": false, "correctAnswerFractions": false, "isSet": false, "show_input_hint": false}}], "sortAnswers": false}, {"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Are the graphs $\\Gamma_1$ and $\\Gamma_2$ isomorphic?</p>\n<p>[[0]]</p>\n<p><strong>If so</strong>, write down an isomorphism $\\varphi : \\Gamma_1 \\to \\Gamma_2$.</p>\n<p><strong>If no such isomorphism exists</strong>, write <code>0</code> in every box below.</p>\n<p>[[1]]</p>", "gaps": [{"type": "yes-no", "useCustomName": true, "customName": "Is there an isomorphism?", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "settings": {"correct_answer_expr": "is_isomorphic"}}, {"type": "write-a-permutation-in-two-line-form", "useCustomName": true, "customName": "Write an isomorphism", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "all_zero:\n  all(map(x=0,x,student_numbers))\n\nstudent_permutation_is_isomorphism:\n  let(\n    a1, adjacency_matrix(g1),\n    a2, adjacency_matrix(g2),\n    p, student_permutation,\n    all(map(\n      all(map(a1[y-1][x-1]=a2[p[y]-1][p[x]-1],x,1..n)),\n      y,\n      1..n\n    ))\n  )\n\nmark:\n  if(is_isomorphic,\n    correctif(student_permutation_is_isomorphism)\n  ,\n    correctif(all_zero)\n  )", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "settings": {"correctAnswer": "if(is_isomorphic,\n  vertex_perm\n,\n  repeat(0,n+1)\n)", "size": "n"}}], "sortAnswers": false}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always"}, {"name": "Graphs: Match adjacency matrix to a graph", "extensions": ["graph-theory-v1"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Chris Graham", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/369/"}, {"name": "Sam Mutter", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/9360/"}], "tags": [], "metadata": {"description": "<p>Alternative version of Graphs: Match graph to its adjacency matrix, where the student must match an adjacency matrix to a graph.</p>", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "<p>Consider the {number_of_graphs} graphs drawn below, each with vertices labelled from $1$ to $\\var{n+1}$.</p>\n<table style=\"height: 32px; width: 900px;\">\n<tbody>\n<tr style=\"height: 18px;\">\n<td style=\"text-align: center; height: 14px; width: 289.433px;\">Graph $G_1$:</td>\n<td style=\"text-align: center; width: 281.05px; height: 14px;\">Graph $G_2$:</td>\n<td style=\"text-align: center; width: 281.05px; height: 14px;\">Graph $G_3$:</td>\n</tr>\n<tr style=\"height: 18px;\">\n<td style=\"text-align: center; height: 18px; width: 289.433px;\">{graphs[0]}</td>\n<td style=\"text-align: center; width: 281.05px; height: 18px;\">{graphs[1]}</td>\n<td style=\"text-align: center; width: 281.05px; height: 18px;\">{graphs[2]}</td>\n</tr>\n</tbody>\n</table>\n<p>You will be shown an adjacency matrix below. The $i$th row or column of the matrix corresponds to vertex labelled $i$.</p>\n<p>Match the matrix to the graph it describes the adjacency of.</p>", "advice": "<p>The adjacency matrix $M$ of a graph $G$ has $(i,j)$th entry $1$ whenever there is an edge from vertex $i$ to vertex $j$.</p>\n<p>The $(i,j)$th entry is $0$ otherwise.</p>", "rulesets": {}, "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"graphs": {"name": "graphs", "group": "Ungrouped variables", "definition": "map(\n  draw_graph_from_adjacency(matrices[q], map(string(i), i, 1..n+1)), \n  q, 0..number_of_graphs - 1\n)", "description": "<p>Graphs built fron the adjacency matrices</p>", "templateType": "anything", "can_override": false}, "matrices": {"name": "matrices", "group": "Ungrouped variables", "definition": "map(\n  matrix(reorder(  \n    [reorder(a[q][0], vertex_perm)] +\n    map(\n      reorder(map(a[q][i][j-i], i, 0..j-1) + a[q][j], vertex_perm), j, 1..n\n      ), vertex_perm\n    )), q, 0..number_of_graphs - 1\n)", "description": "<p>The qth matrix takes entries from a[q] as its upper triangle, then duplicates this for the bottom triangle to make a symmetric matrix.</p>", "templateType": "anything", "can_override": false}, "n": {"name": "n", "group": "Ungrouped variables", "definition": "7", "description": "<p>Each graph will contain n+1 vertices</p>", "templateType": "anything", "can_override": false}, "a": {"name": "a", "group": "Ungrouped variables", "definition": "map(\n  [first_row[q]] +\n  map([0] + repeat(random(0,0,0,1,1), n-j), j, 1..n-1)\n  + [[0]],\n  q, 0..number_of_graphs - 1\n)", "description": "<p>The top-right triangle of the adjacency matrices. The bottom-left triangle will be the transpose of this, so that the matrices are symmetrical.</p>\n<p>The first rows are all distinct, so no two adjacency matrices are the same.</p>\n<p>Change the number of 0s and 1s to get a more/less dense matrix.</p>", "templateType": "anything", "can_override": false}, "number_of_graphs": {"name": "number_of_graphs", "group": "Ungrouped variables", "definition": "3", "description": "<p>The number of graphs displayed in the question. Each adjacency matrix correctly matched to its graph will score a point.</p>\n<p>This must be less than or equal to the number of vertices n+1.</p>", "templateType": "anything", "can_override": false}, "graph_mat_pairs": {"name": "graph_mat_pairs", "group": "Ungrouped variables", "definition": "shuffle(\n  map(\n    [\n      'graph': graphs[i],\n      'matrix': matrices[i],\n      'marks': 4*id(number_of_graphs)[i]\n    ], i, 0..number_of_graphs - 1\n  )\n)", "description": "<p>The graphs, matched with their adjacency matrices. The 'marks' column will form the marking matrix</p>", "templateType": "anything", "can_override": false}, "first_row": {"name": "first_row", "group": "Ungrouped variables", "definition": "shuffle(\n  flatten(map(\n    map(vector(id(n+1)[i]) + vector(id(n+1)[j]), j, i+1..n), i, 1..n)\n  )\n)", "description": "<p>To ensure no two adjacency matrices are the same, the first row will be taken from this list.</p>", "templateType": "anything", "can_override": false}, "vertex_perm": {"name": "vertex_perm", "group": "Ungrouped variables", "definition": "shuffle(0..n)", "description": "<p>The labels of vertices will be permuted. This is so it isn't obvious that the first row of the adjacency matrices are different.</p>", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["graphs", "matrices", "n", "a", "number_of_graphs", "graph_mat_pairs", "first_row", "vertex_perm"], "variable_groups": [], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "1_n_2", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>$A = \\var{graph_mat_pairs[0]['matrix']}$.</p>\n<p>Select which graph $A$ is the adjacency matrix for.</p>", "minMarks": 0, "maxMarks": 0, "shuffleChoices": false, "displayType": "radiogroup", "displayColumns": 0, "showCellAnswerState": true, "choices": ["$G_1$", "$G_2$", "$G_3$"], "matrix": "graph_mat_pairs[0]['marks']"}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always"}, {"name": "Graphs: Write the adjacency matrix of this graph", "extensions": ["graph-theory-v1"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Sam Mutter", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/9360/"}], "tags": [], "metadata": {"description": "<p>The student is shown one graph, and asked to type the adjacency matrix</p>", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "<p>You will be shown three graphs below, each with vertices labelled from $1$ to $\\var{n+1}$.</p>\n<p>Consider the following graph:</p>\n<p>{max_width(30,graph)}</p>\n<p>Write down the adjacency matrix of this graph.</p>\n<p>The $i$th row or column of your matrix should correspond to the vertex labelled $i$.</p>", "advice": "<p>The adjacency matrix $M$ of a graph $G$ has $ij$th entry $1$ whenever there is an edge from vertex $i$ to vertex $j$.</p>\n<p>The $ij$th entry is $0$ otherwise.</p>", "rulesets": {}, "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"graph": {"name": "graph", "group": "Ungrouped variables", "definition": "draw_graph_from_adjacency(mat, map(string(i), i, 1..n+1))", "description": "<p>Graphs built fron the adjacency matrices</p>", "templateType": "anything", "can_override": false}, "mat": {"name": "mat", "group": "Ungrouped variables", "definition": "matrix(reorder(  \n    [reorder(a[0], vertex_perm)] +\n    map(\n      reorder(map(a[i][j-i], i, 0..j-1) + a[j], vertex_perm), j, 1..n\n      ), vertex_perm\n  ))", "description": "<p>The qth matrix takes entries from a[q] as its upper triangle, then duplicates this for the bottom triangle to make a symmetric matrix.</p>", "templateType": "anything", "can_override": false}, "n": {"name": "n", "group": "Ungrouped variables", "definition": "7", "description": "<p>Each graph will contain n+1 vertices.</p>\n<p>n should be at least 4. My view is that it looks good when n is around 7 to 8.</p>", "templateType": "anything", "can_override": false}, "a": {"name": "a", "group": "Ungrouped variables", "definition": "map([0] + repeat(random(0,0,0,1,1), n-j), j, 0..n-1)\n+ [[0]]\n", "description": "<p>The top-right triangle of the adjacency matrices. The bottom-left triangle will be the transpose of this, so that the matrices are symmetrical.</p>\n<p>The first rows are all distinct, so no two adjacency matrices are the same.</p>\n<p>Change the number of 0s and 1s to get a more/less dense matrix.</p>", "templateType": "anything", "can_override": false}, "vertex_perm": {"name": "vertex_perm", "group": "Ungrouped variables", "definition": "shuffle(0..n)", "description": "<p>The labels of vertices will be permuted. This is so it isn't obvious that the first row of the adjacency matrices are different.</p>", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["n", "a", "vertex_perm", "graph", "mat"], "variable_groups": [], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "matrix", "useCustomName": false, "customName": "", "marks": "4", "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "correctAnswer": "{mat}", "correctAnswerFractions": false, "numRows": "{n+1}", "numColumns": "{n+1}", "allowResize": false, "tolerance": 0, "markPerCell": true, "allowFractions": false, "minColumns": 1, "maxColumns": 0, "minRows": 1, "maxRows": 0}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always"}, {"name": "Prim's algorithm", "extensions": ["graph-theory"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}], "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": {}, "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"}]}], "allowPrinting": true, "navigation": {"allowregen": true, "reverse": true, "browse": true, "allowsteps": true, "showfrontpage": false, "showresultspage": "oncompletion", "navigatemode": "menu", "onleave": {"action": "none", "message": ""}, "preventleave": false, "startpassword": "", "allowAttemptDownload": false, "downloadEncryptionKey": ""}, "timing": {"allowPause": true, "timeout": {"action": "none", "message": ""}, "timedwarning": {"action": "none", "message": ""}}, "feedback": {"showactualmark": true, "showtotalmark": true, "showanswerstate": true, "allowrevealanswer": true, "advicethreshold": 0, "intro": "", "end_message": "", "reviewshowscore": true, "reviewshowfeedback": true, "reviewshowexpectedanswer": true, "reviewshowadvice": true, "feedbackmessages": []}, "diagnostic": {"knowledge_graph": {"topics": [], "learning_objectives": []}, "script": "diagnosys", "customScript": ""}, "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}], "extensions": ["graph-theory", "graph-theory-v1", "permutations"], "custom_part_types": [{"source": {"pk": 2, "author": {"name": "Christian Lawson-Perfect", "pk": 7}, "edit_page": "/part_type/2/edit"}, "name": "List of numbers", "short_name": "list-of-numbers", "description": "<p>The answer is a comma-separated list of numbers.</p>\n<p>The list is marked correct if each number occurs the same number of times as in the expected answer, and no extra numbers are present.</p>\n<p>You can optionally treat the answer as a set, so the number of occurrences doesn't matter, only whether each number is included or not.</p>", "help_url": "", "input_widget": "string", "input_options": {"correctAnswer": "join(\n  if(settings[\"correctAnswerFractions\"],\n    map(let([a,b],rational_approximation(x), string(a/b)),x,settings[\"correctAnswer\"])\n  ,\n    settings[\"correctAnswer\"]\n  ),\n  settings[\"separator\"] + \" \"\n)", "hint": {"static": false, "value": "if(settings[\"show_input_hint\"],\n  \"Enter a list of numbers separated by <code>{settings['separator']}</code>.\",\n  \"\"\n)"}, "allowEmpty": {"static": true, "value": true}}, "can_be_gap": true, "can_be_step": true, "marking_script": "bits:\nlet(b,filter(x<>\"\",x,split(studentAnswer,settings[\"separator\"])),\n    if(isSet,list(set(b)),b)\n)\n\nexpected_numbers:\nlet(l,settings[\"correctAnswer\"] as \"list\",\n    if(isSet,list(set(l)),l)\n)\n\nvalid_numbers:\nif(all(map(not isnan(x),x,interpreted_answer)),\n    true,\n    let(index,filter(isnan(interpreted_answer[x]),x,0..len(interpreted_answer)-1)[0], wrong, bits[index],\n      warn(wrong+\" is not a valid number\");\n      fail(wrong+\" is not a valid number.\")\n    )\n  )\n\nis_sorted:\nassert(sort(interpreted_answer)=interpreted_answer,\n    multiply_credit(0.5,\"Not in order\")\n  )\n\nincluded:\nmap(\n      let(\n        num_student,len(filter(x=y,y,interpreted_answer)),\n        num_expected,len(filter(x=y,y,expected_numbers)),\n        switch(\n          num_student=num_expected,\n            true,\n          num_student<num_expected,\n            incorrect(\n              if(isSet,\"Your answer does not contain \"+x+\" but should.\",\n                \"Your answer does not contain \"+x+\" enough times.\"\n              )\n            );false\n          ,\n            incorrect(\n              if(isSet,\"Your answer contains \"+x+\" but should not.\",\n                \"Your answer contains \"+x+\" too many times.\"\n              )\n            );false\n        )\n      )\n      ,\n      x,\n      sort(list(set(expected_numbers)))\n  )\n\nall_included:\nall(included)\n\nno_extras:\nif(all(map(x in expected_numbers, x, interpreted_answer)),\n    true\n  ,\n    incorrect(\"Your answer contains \"+extra_numbers[0]+\" but should not.\");\n    false\n  )\n\ninterpreted_answer:\nif(lower(studentAnswer) in [\"empty\",\"\u2205\"],[],\n  map(\n    if(settings[\"allowFractions\"],parsenumber_or_fraction(x,notationStyles), parsenumber(x,notationStyles))\n    ,x\n    ,bits\n  )\n)\n\nmark:\nif(studentanswer=\"\",fail(\"You have not entered an answer\"),false);\napply(valid_numbers);\napply(included);\napply(no_extras);\ncorrectif(all_included and no_extras)\n\nnotationStyles:\n[\"en\"]\n\nisSet:\nsettings[\"isSet\"]\n\nextra_numbers:\nfilter(not (x in expected_numbers),x,interpreted_answer)", "marking_notes": [{"name": "bits", "description": "<p>The separate items in the student's answer</p>", "definition": "let(b,filter(x<>\"\",x,split(studentAnswer,settings[\"separator\"])),\n    if(isSet,list(set(b)),b)\n)"}, {"name": "expected_numbers", "description": "", "definition": "let(l,settings[\"correctAnswer\"] as \"list\",\n    if(isSet,list(set(l)),l)\n)"}, {"name": "valid_numbers", "description": "<p>Is every number in the student's list valid?</p>", "definition": "if(all(map(not isnan(x),x,interpreted_answer)),\n    true,\n    let(index,filter(isnan(interpreted_answer[x]),x,0..len(interpreted_answer)-1)[0], wrong, bits[index],\n      warn(wrong+\" is not a valid number\");\n      fail(wrong+\" is not a valid number.\")\n    )\n  )"}, {"name": "is_sorted", "description": "<p>Are the student's answers in ascending order?</p>", "definition": "assert(sort(interpreted_answer)=interpreted_answer,\n    multiply_credit(0.5,\"Not in order\")\n  )"}, {"name": "included", "description": "<p>Is each number in the expected answer present in the student's list the correct number of times?</p>", "definition": "map(\n      let(\n        num_student,len(filter(x=y,y,interpreted_answer)),\n        num_expected,len(filter(x=y,y,expected_numbers)),\n        switch(\n          num_student=num_expected,\n            true,\n          num_student<num_expected,\n            incorrect(\n              if(isSet,\"Your answer does not contain \"+x+\" but should.\",\n                \"Your answer does not contain \"+x+\" enough times.\"\n              )\n            );false\n          ,\n            incorrect(\n              if(isSet,\"Your answer contains \"+x+\" but should not.\",\n                \"Your answer contains \"+x+\" too many times.\"\n              )\n            );false\n        )\n      )\n      ,\n      x,\n      sort(list(set(expected_numbers)))\n  )"}, {"name": "all_included", "description": "<p>Has every number been included the right number of times?</p>", "definition": "all(included)"}, {"name": "no_extras", "description": "<p>True if the student's list doesn't contain any numbers that aren't in the expected answer.</p>", "definition": "if(all(map(x in expected_numbers, x, interpreted_answer)),\n    true\n  ,\n    incorrect(\"Your answer contains \"+extra_numbers[0]+\" but should not.\");\n    false\n  )"}, {"name": "interpreted_answer", "description": "A value representing the student's answer to this part.", "definition": "if(lower(studentAnswer) in [\"empty\",\"\u2205\"],[],\n  map(\n    if(settings[\"allowFractions\"],parsenumber_or_fraction(x,notationStyles), parsenumber(x,notationStyles))\n    ,x\n    ,bits\n  )\n)"}, {"name": "mark", "description": "This is the main marking note. It should award credit and provide feedback based on the student's answer.", "definition": "if(studentanswer=\"\",fail(\"You have not entered an answer\"),false);\napply(valid_numbers);\napply(included);\napply(no_extras);\ncorrectif(all_included and no_extras)"}, {"name": "notationStyles", "description": "", "definition": "[\"en\"]"}, {"name": "isSet", "description": "<p>Should the answer be considered as a set, so the number of times an element occurs doesn't matter?</p>", "definition": "settings[\"isSet\"]"}, {"name": "extra_numbers", "description": "<p>Numbers included in the student's answer that are not in the expected list.</p>", "definition": "filter(not (x in expected_numbers),x,interpreted_answer)"}], "settings": [{"name": "correctAnswer", "label": "Correct answer", "help_url": "", "hint": "The list of numbers that the student should enter. The order does not matter.", "input_type": "code", "default_value": "", "evaluate": true}, {"name": "allowFractions", "label": "Allow the student to enter fractions?", "help_url": "", "hint": "", "input_type": "checkbox", "default_value": false}, {"name": "correctAnswerFractions", "label": "Display the correct answers as fractions?", "help_url": "", "hint": "", "input_type": "checkbox", "default_value": false}, {"name": "isSet", "label": "Is the answer a set?", "help_url": "", "hint": "If ticked, the number of times an element occurs doesn't matter, only whether it's included at all.", "input_type": "checkbox", "default_value": false}, {"name": "show_input_hint", "label": "Show the input hint?", "help_url": "", "hint": "", "input_type": "checkbox", "default_value": true}, {"name": "separator", "label": "Separator", "help_url": "", "hint": "The substring that should separate items in the student's list", "input_type": "string", "default_value": ",", "subvars": false}], "public_availability": "always", "published": true, "extensions": []}, {"source": {"pk": 197, "author": {"name": "Christian Lawson-Perfect", "pk": 7}, "edit_page": "/part_type/197/edit"}, "name": "Write a permutation in two-line form", "short_name": "write-a-permutation-in-two-line-form", "description": "<p>The student must write out a permutation (an element of $S_n$) in two-line form: the top line always contains the numbers 1 to $n$, and on the bottom line they must write the numbers that they are mapped to.</p>", "help_url": "", "input_widget": "matrix", "input_options": {"correctAnswer": "matrix(map(settings[\"correctAnswer\"][i],i,1..settings[\"size\"]))", "hint": {"static": true, "value": ""}, "allowResize": {"static": true, "value": false}, "numRows": {"static": true, "value": 1}, "numColumns": {"static": false, "value": "settings[\"size\"]"}, "parseCells": {"static": true, "value": true}, "allowedNotationStyles": {"static": true, "value": ["plain"]}, "allowFractions": {"static": true, "value": false}, "showBrackets": {"static": true, "value": true}, "rowHeaders": {"static": false, "value": "[]"}, "columnHeaders": {"static": false, "value": "map(string(n),n,1..settings[\"size\"])"}}, "can_be_gap": true, "can_be_step": true, "marking_script": "mark:\napply(valid_permutation);\ncorrectif(student_permutation=settings[\"correctAnswer\"])\n\nstudent_numbers:\nlist(studentAnswer[0])\n\nstudent_permutation:\npermutation(map(x-1,x,student_numbers))\n\nvalid_permutation:\n  assert(all(map(isint(x) and x>=1 and x<=settings[\"size\"], x, student_numbers)),\n    fail(\"Your answer is not a valid permutation: each entry must be one of the numbers 1 \u2026 {settings['size']}.\")\n  );\n  assert(len(set(student_numbers))=settings[\"size\"],\n    fail(\"Your answer is not a valid permutation: some entries occur more than once.\")\n  )\n\ninterpreted_answer:\nstudent_permutation", "marking_notes": [{"name": "mark", "description": "This is the main marking note. It should award credit and provide feedback based on the student's answer.", "definition": "apply(valid_permutation);\ncorrectif(student_permutation=settings[\"correctAnswer\"])"}, {"name": "student_numbers", "description": "<p>The numbers that the student typed.</p>", "definition": "list(studentAnswer[0])"}, {"name": "student_permutation", "description": "", "definition": "permutation(map(x-1,x,student_numbers))"}, {"name": "valid_permutation", "description": "", "definition": "  assert(all(map(isint(x) and x>=1 and x<=settings[\"size\"], x, student_numbers)),\n    fail(\"Your answer is not a valid permutation: each entry must be one of the numbers 1 \u2026 {settings['size']}.\")\n  );\n  assert(len(set(student_numbers))=settings[\"size\"],\n    fail(\"Your answer is not a valid permutation: some entries occur more than once.\")\n  )"}, {"name": "interpreted_answer", "description": "A value representing the student's answer to this part.", "definition": "student_permutation"}], "settings": [{"name": "correctAnswer", "label": "Correct answer", "help_url": "", "hint": "", "input_type": "code", "default_value": "", "evaluate": true}, {"name": "size", "label": "Size", "help_url": "", "hint": "", "input_type": "code", "default_value": "", "evaluate": true}], "public_availability": "always", "published": true, "extensions": []}, {"source": {"pk": 1, "author": {"name": "Christian Lawson-Perfect", "pk": 7}, "edit_page": "/part_type/1/edit"}, "name": "Yes/no", "short_name": "yes-no", "description": "<p>The student is shown two radio choices: \"Yes\" and \"No\". One of them is correct.</p>", "help_url": "", "input_widget": "radios", "input_options": {"correctAnswer": "if(eval(settings[\"correct_answer_expr\"]), 0, 1)", "hint": {"static": true, "value": ""}, "choices": {"static": true, "value": ["Yes", "No"]}}, "can_be_gap": true, "can_be_step": true, "marking_script": "mark:\nif(studentanswer=correct_answer,\n  correct(),\n  incorrect()\n)\n\ninterpreted_answer:\nstudentAnswer=0\n\ncorrect_answer:\nif(eval(settings[\"correct_answer_expr\"]),0,1)", "marking_notes": [{"name": "mark", "description": "This is the main marking note. It should award credit and provide feedback based on the student's answer.", "definition": "if(studentanswer=correct_answer,\n  correct(),\n  incorrect()\n)"}, {"name": "interpreted_answer", "description": "A value representing the student's answer to this part.", "definition": "studentAnswer=0"}, {"name": "correct_answer", "description": "", "definition": "if(eval(settings[\"correct_answer_expr\"]),0,1)"}], "settings": [{"name": "correct_answer_expr", "label": "Is the answer \"Yes\"?", "help_url": "", "hint": "An expression which evaluates to <code>true</code> or <code>false</code>.", "input_type": "mathematical_expression", "default_value": "true", "subvars": false}], "public_availability": "always", "published": true, "extensions": []}], "resources": []}