Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MATH1005/MATH6005 Final Exam
Marks Description
2 Demonstrates mastery of how to use a truth table to determine whether or not a logical
equivalence holds by correctly using a truth table, or truth tables, to show that this logical
equivalence holds.
1 A minor error but demonstrates knowledge of how a truth table may be used to show that a
logical equivalence holds
0 Otherwise
Problem 1b
Marks Description
2 Demonstrates mastery of writing the structural part of an argument that proceeds via the
contrapositive. Introduces the variable G. Makes the correct hypothesis. Makes the correct
conclusion (may give a statement that is logically equivalent to the one listed in the solutions).
1 A minor error (like forgetting to introduce G, or supposing that the chromatic number of G is
greater than or equal to 4), but demonstrates knowledge of how to structure an argument via
the contrapositive. At an absolute minimum the response contains p->q and ~q->~p.
0 Otherwise
Problem 1c
Marks Descriptions
1 Demonstrates mastery of the notation of sets and cartesian products by correctly answering the
question and using notation accurately throughout
0.5 A minor error such as forgetting the empty set but must use notation correctly
0 Otherwise
Problem 1d
Marks Descriptions
3 An excellent element proof. Introduces variables, uses notation correctly (uses ⇔ between
statements, never = between statements, etc), justifies each step with definitions and laws, and
does not skip steps.
2.5 Almost an excellent element proof. As for 3 but doesn’t introduce at least some of the
variables or does not justify every step or skips an important step.
2 Pretty good element proof. Perhaps makes at least two of the errors described in 2.5.
1 Demonstrates some understanding of what to do, but misuses notation in a significant way (like
writing = between statements, writing ⇔ between sets, proving only one containment) OR only
draws the Venn diagrams
0 Otherwise
Problem 1e
Marks Descriptions
2 Describes an explicit counterexample and demonstrates that it is a counterexample
1.5 Correctly identifies that the statement is false, describes an explicit counterexample but does
not demonstrate that it is a counterexample.
1 Correctly identifies that the statement is false, but does not provide an explicit counterexample
0 Otherwise
Problem 2a
Marks Descriptions
3 An excellent induction. The induction structure is explicit (does not have to be exactly like the
solutions, but a clear base step and inductive step, explicit inductive hypothesis and invokes the
principle of induction) and explicitly states when the inductive hypothesis is used. The inductive
step is effective.
2.5 Almost an excellent induction. As for 3 but a minor error or omission.
2 A pretty good induction. Perhaps cannot make the inductive step work, but structures the
argument well.
1.5 Cannot make the inductive step work, and the structure has a minor error.
1 Demonstrates some understanding of mathematical induction, but does not rise to the level of 2
0 Otherwise
Problem 2b
Marks Descriptions
1 Effectively invokes generalised pigeon hole principle, or the pigeon hole principle, to explain
why there is at least one PIN shared by four or more customers.
0.5 Mentions the pigeon hole principle, but the proof is not quite effective, or makes mention of
pigeons and pigeon holes without making explicit reference to the pigeon hole principle.
0 Otherwise
Problem 2c
Marks Descriptions
3 An excellent computation that demonstrates mastery of probability when outcomes are equally
likely. Explicitly justifies the use of formula P(E) = |E|/|S|, and explains how to correctly count the
sets to be counted.
2.5 Almost an excellent computation. As for 3 but omits the justification that counting can be used
to compute the probability, or part of the explanation needs expanding.
2 A pretty good computation. Perhaps a minor error in one part of the computation, or correct
computation but almost no explanation and no justification as to why counting can be used
1 Demonstrates some understanding of how to use counting to compute a probability.
0 Otherwise
Problem 2d(i)
Marks Descriptions
1 Demonstrates mastery of the ideas of how to think through a probability experiment by
explaining how each ordered pair represents what happened in the experiment and
correctly describing the outcomes as a set of 16 ordered pairs
0.5 Demonstrates some understanding of the ideas of how to think through a probability
experiment, perhaps by correctly describing the outcomes as a set of 16 ordered pairs.
0 Otherwise
Problem 2d(ii)
Marks Descriptions
2 Demonstrates knowledge of what it means for events to be independent by correctly computing
the three probabilities required and determining that the events are not independent.
1 Demonstrates some understanding of what it means for events to be independent, perhaps by
giving a correct definition or by computing (perhaps incorrectly) the probabilities of E1, E2 and
their intersection
0.5 Does not demonstrate understanding of what it means for events to be independent but
correctly computes the probabilities of E1 and E2.
0 Otherwise
NOTE: GRADES FOR 2d(i) and 2d(ii) are combined for entry in spreadsheet
Problem 3a
Marks Descriptions
3 Demonstrates mastery of the vocabulary of walks, paths and circuits by giving three correct
answers (numbers and lists) and walks are described as alternating lists of vertices and edges
(it is necessary to list the edges because there are parallel edges in the graph).
2 Demonstrates a pretty good understanding of the vocabulary of walks, paths and circuits, but
for a minor error (omitting the trivial circuits in (iii) or not having the same circuit starting at
different points in (iii) or lists the correct number of walks IN EACH CASE but writes walks as a
list of vertices without the edges in between
1.5 Demonstrates a good understanding of the vocabulary of walks, paths and circuits but writes
walks as a list of vertices without the edges in between (it is necessary to list the edges
because there are parallel edges in the graph) and therefore does not distinguish between
some walks that are different (would lead to answers infinitely many, 1, 8)
Answers to only two parts from three parts for instance (i) and (ii) are correct.
1 Demonstrates some understanding of walks, paths and circuits, but does not rise to the level of
2 or 1.5. Answers to only one part of the three parts are correct.
0 Otherwise
Problem 3b
Marks Descriptions
1 Mentions something about arranging CPUs for the purpose of parallel computing
0 Otherwise
Problem 3c(i)
Marks Descriptions
1 Demonstrates knowledge of the vocabulary of graph isomorphisms by stating a correct
definition (may leave out “for all u_1, u_2 \in V(G)” as we left this out in the lecture slides)
0 Otherwise
Problem 3c(ii)
Marks Descriptions
2 Demonstrates mastery of enumerative combinatorics and graph isomorphisms and knowledge
of the complete bipartite graph by correctly counting isomorphisms and explaining the
reasoning.
1 Demonstrates understanding of what the complete bipartite graph is, and some idea that an
isomorphism must map vertices of degree m to vertices of degree m. May have the incorrect
answer.
0.5 Demonstrates understanding of what the complete bipartite graph is
0 Otherwise
Note: Score for 3c(i) and 3c(ii) combined for entry into the spreadsheet.
Problem 3d
Marks Descriptions
3 Demonstrates mastery of Hamilton circuits and proofs by providing a well-structured and
effective argument that the graph has no Hamilton circuit.
2 Pretty good argument. As for 3 but omits one or more than one necessary justification. No
false statements are made.
1 Demonstrates knowledge of what a Hamilton circuit is.
0 Otherwise
Problem 4a
Marks Descriptions
1 Demonstrates knowledge of the Nearest Neighbour Algorithm by “correctly” listing the input and
output. To be correct, the input must list “weighted complete graph” and the output must list
“Hamilton circuit for G” and must NOT list other things
0.5 If missing “complete” for input and otherwise satisfying for 1
0 Otherwise (including if the response claims that the algorithm produces a minimal weight
Hamilton circuit)
Problem 4b
Marks Descriptions
1 Demonstrates knowledge of Fleury’s algorithm and Euler circuits by correctly identifying the
condition.
OR
If they mentioned at most 2 vertices are odd and must start at an odd degree vertex
0.5 If they mentioned at most 2 vertices are odd (but not starting at odd)
0 Otherwise
Problem 4c
Marks Descriptions
2 Demonstrates understanding of Kruskal’s algorithm by correctly naming it and drawing the
correct minimal spanning tree.
1 Meets 1 of the 2 criteria for a 2
0 Otherwise
Problem 4d
Marks Descriptions
3 Demonstrates understanding of Dijkstra’s algorithm by producing lists that are correct and
complete.
2.5 3 except no A in path
2 Demonstrates a pretty good understanding of Dijkstra’s algorithm but at least one of the lists is
incorrect or incomplete. There is evidence that the misunderstanding is a minor error or minor
misunderstanding.
1 Demonstrates some understanding of Dijkstra’s algorithm but at least one of the lists is incorrect
or incomplete
0 Otherwise
Problem 4e
Marks Descriptions
3 Demonstrates understanding of the vertex labelling algorithm by producing lists that are correct
and complete.
2 Demonstrates pretty good understanding of the vertex labelling algorithm but at least one of the
lists is incorrect or incomplete. There is evidence that the misunderstanding is a minor error or
minor misunderstanding.
1.5 Demonstrates some understanding of the vertex labelling algorithm but at least one of the lists
is incorrect or incomplete AND with understanding of virtual flow.
1 Demonstrates some understanding of the vertex labelling algorithm but at least one of the lists
is incorrect or incomplete
(if the solution does not demonstrate understanding of virtual flow then it cannot score more
than 1)
0 Otherwise
Problem 5a
Marks Descriptions
2 Demonstrates understanding of transition diagrams for Markov process by drawing a correct
directed graph with correct labels, including correct deductions about the labels on edges for
which explicit information is not given in the problem.
1 Demonstrates some understanding of transition diagrams for Markov process by drawing a
directed graph with labels on edges. May have made an error in transcribing information from
the problem or may omit edges (and/or their labels) not explicitly mentioned in the problem.
OR
Makes a correct transition matrix instead of a transition diagram.
0.5 Draws a directed graph
OR
Makes a transition diagram
0 Otherwise
Problem 5b(i)
Marks Descriptions
1 Demonstrates an understanding of webgraphs, and the ability to model a similar situation, by
correctly describing the vertices and edges (including the correct direction).
0.5 Describes the vertices correctly
0 Otherwise
Problem 5b(ii)
Marks Descriptions
2 Demonstrates understanding of the two key hypotheses of the PageRank model by making
analogous statements about the employee graph (language may be rough, but there is enough
evidence to suggest an understanding of both)
1 Makes at least one of the two statements listed in the solution (language may be rough, but
there is enough evidence to suggest an understanding of at least one hypothesis)
0 Otherwise
Note: Scores for 5b(i) and 5b(ii) and combined for entry in spreadsheet.
Problem 5c(i)
Marks Descriptions
1 A correct webgraph
0.5 If added transition probability and dotted arrow for D
0 Otherwise
Problem 5c(ii)
Marks Descriptions
2 A correct basic transition matrix (also accept the same matrix but with ¼, ¼, ¼ , ¼ along the
bottom row, even though this is technically incorrect).