Here are some explanation for shorthand used for marking the midterm
and some remarks.
- NAeq - "Not answered" equivalent. I would prefer if "Not
answered" was written but other forms were accepted.
- PT - Proved true. Assumed the conclusion and arrived at true (see
common mistakes in proofs)
- UI - "Upwards" induction. For question 7, adding a vertex to a
tree rather than removing a vertex. See common mistakes in
proofs. The proof would require also showing that all trees can be
built by adding one vertex at a time.
- Proved Q implies P rather than P implies Q. See updated common
mistakes in proofs.
- A variant of the previous error involves proving that some
statement is true for n implies the same statement is true
for n-1. There is nothing wrong in proving this except that
it does not help complete a proof by induction. Induction works
because we've proven a statement for some base case
(e.g., n=1) and then we need to prove if the
statement is true for n-1 implies the same statement is true
for n. Applying the latter with n=2 gives us the
statement for n=2. After this, applying the latter
with n=2 gives us the statement for n=3. And so
Proving that some statement is true for n implies the same
statement is true for n-1 only shows that for any value less
or equal to the base case, the statement is true (which is usually
not many cases).
- For question 6, some rather vague arguments about why d
must appear twice were accepted. A more formal answer would have
been preferred. Many errors are made assuming that something "must"
- The midterm is marked out of 33 instead of the originally
intended 37. The maximum possible score was 40. As a consequence,
many students got more than 100% (and they do get to keep the extra