RUBRIC AND GRADING NOTES FOR THE SECOND MIDTERM
================================================================
PROBLEM 1
2 points per problem. No partial credit.
================================================================
PROBLEM 2a (Parth)
2 points for the correct answer.
2 points for an appropriate explanation.
Common deductions:
-1 : Using the word 'connected' instead of 'adjacent'. eg. 'The two
vertices with degree 4 are connected' is wrong. However, if you said
something like 'connected immediately', 'neighbors' or something
similar, no points were deducted.
-1/2 to -1: Having the correct explanation, but not having the correct
number of the subgraph you refer to. eg. 'There exist 6 C3's in G1
and 4 C3's in G2' if instead the correct answer should've been 'There
exist 8 C3's in G1 and 3C3's in G2'. Both answers say that the number
of C3's in G1 was more than those in G2, but the counting was wrong.
-1: Too vague an explanation
================================================================
PROBLEM 2b (Kevin, Leila)
+1 point for identifying that the total number of paths is a product
of the paths to and from the choke point node
+1 for the correct number of paths from the beginning node to the choke point
+1 for the correct number of paths from the choke point to the ending
node
(+3 credit is also given if these are not explicitly stated but
the student described all of the paths in detail.)
+1 for work. this can be a description of their methodology or some
labeled paths.
+1 for free. point to be removed if the student included a walk in the
total number of paths
================================================================
PROBLEM 3 (Tom, Sarah)
(a) 1 point
(b) 1 point
(c) 2 points
(d) 2 points
================================================================
PROBLEM 4: Chromatic number (Margaret and Andrew)
Total of 6 points
Basic answer (max of the two input chromatic number): 2.5 points
-0.5 to -1 for technical bugs (e.g. using cases to express max)
-1 to -1.5 for right idea with serious flaws (e.g. adding 1)
The special case: 1.5 points
1 point for correctly describing the special case
(both inputs have chromatic number 2). Half-credit
for noticing the issue only in the case of 2-node graphs.
0.5 points for saying output chromatic number in this case is 3
It was also ok to cover the special case with a general
argument that the output chromatic number must always
be >= 3 because the output contains a triangle. (This
was often bundled together with the justification for
the general case.)
Justification for the general case: 2 points
The model solutions have a complete justification. We
didn't expect you to cover all the points in detail for
full credit. However, we gave little or no partial credit
for discussing only the special case or simply repeating
the claim that the output chromatic number was the max of
the input chromatic numbers.
================================================================
PROBLEM 5: Tree Induction. (Lenny and Fatemeh)
Here is a rubric for the 4-ary version of the Tree Induction problem.
The other version dealt with 5-ary trees, and everything below is the
same, except replace "4" with "5", and replace "3" with "4".
BASE CASE 1 point.
-.5 if case for h=0 is omitted
-.5 for other minor errors.
okay to include extra cases
IH: 2 points
Deductions of .5 points for each of the following errors, among others:
Must say "any full 4-ary tree of height..." (instead of just "a tree of
height...."
Must use both a variable h and k, as in "... tree of height h<k has at
least 3h+1 leaves" or as in "... tree of height h=0,1,2,...,k-1 has
height at least 3h+1. If you only used one variable, you've probably
written something like: "any tree of height 0,1,2..., h has at least
3h+1 leaves", which is wrong because the number of leaves depends on
the number in the range, not just the endpoint. (I.e, you'd be
asserting that every tree of height 0 had at least 3h+1 leaves, every
tree of height 1 had at least 3h+1 leaves, etc.)
Must quantify the bounding variable (e.g., "for some k") and give any
constraints on it (at least 0 (if doing the induction from k to k+1)
or at least 1 (if doing the induction from k-1 to k). In any case,
the bound on k must allow the largest base case to be incorporated
into the assumption, Otherwise your inductive step can't proceed from
the inductive hypothesis to the first non-base case.
Must state that the full 4-ary tree of depth h has at least 3h+1
leaves.
INDUCTIVE STEP (4 points)
(It is okay to do the induction from k-1 to k, or from k to k+1. The
following assumes going from k-1 to k.)
1 point for noting that the root has exactly 4 children. Loss of .5 if
you suggest that it might have 0 or 4 children, and then say that 0 is
just the base case. This is because the value of k that you're using
should be one larger than your largest base case, and at least 1 in any
case, so the tree has height at least 1, and 0 children is not a
possibility.
1 point for noting that AT LEAST one subtree has height EQUAL TO k-1, and
the others MAY have heights between 0 and k-1. This point is lost if
you said that all have height equal to k-1. Many people lost this point.
1 point for applying the IH: .5 for mentioning it, and .5 for correctly
using the expression 3(k-1) + 1.
1 point for noting that at the least, the other subtrees contributed
at least one leaf, and then correctly adding at least 3 more (worth
.5) for the other subtrees and summing to get 3(k-1)+1 + 3 = 3k+1
(another .5).
MANY people tried to do induction at the leaves, by starting with a
tree of height k-1, and replacing a leaf node at level k-1 (often
called height k-1) with an interior node with 4 children. This
argument gets between 1 and 2 out of the 4 points available for the
Inductive Step, depending on what other elements were
correct/incorrect.
(Almost) NEVER DO TREE INDUCTION BY ADDING TO THE LEAVES!!!
It is important to understand why tree inductions often DO NOT WORK
when the induction is by adding something to a leaf. A correct
induction for the case k must start with an *arbitrary* full 4-ary
tree of height k. You make no other assumption whatsoever about its
form, because you need to prove that the claim holds for every
possible full 4-ary tree of height k. We then see how this arbitrary
tree might be composed of trees of smaller heights. This is how the
model solution progressed.
However, if you instead *start with a tree of height k-1* and then say
"to get a tree of height k, we replace a leaf with an interior node
with 4 children", you are implicitly assuming that *all* full 4-ary
trees can be built by this process.
If the replaced node is not at level k-1, then you do not reach level
k, and your induction does not work.
If you DO replace a node at level k-1, you're basically asserting that
every tree of height k is obtained by a tree of height k-1 with one
leaf replaced by an interior node and 4 children. But this is false.
Consider a tree of height two with root, 4 children of the root, and 4
children for each of these, making the complete perfect tree with 16
leaves. This tree cannot be obtained by replacing a leaf node of a
tree of height 1 with an interior node and 4 children. In fact, if
you think about it carefully, this attempted proof only really proves
the claim for very skinny trees, where at each level, there is a
single interior node and 3 leaves.
The advice to never add on to a tree at the leaves in an induction
holds for other structures as well. In general, when doing an
induction on objects defined by some parameter k, you should start the
inductive step with a k-valued object, and see how it is composed of
k-1 (or smaller) valued objects. Do not start with a k-1 valued
object, and build onto it to get a k-valued object, because then you
implicitly assume that all k-valued objects can be obtained via this
process. Sometimes the flaws can be quite subtle, and it is very easy
to get tricked.
As an aside, we did see one inductive argument at the leaves that got
full credit. It started, as it should, with an arbitrary full 4-ary
tree of height k. Then, chop off all leaves at level k, to obtain a
tree of height k-1. This trimmed tree by inductive hypothesis has at
least 3(k-1)+1 = 3k-2 leaves. Now, notice that what was trimmed must
have been at least one leaf, otherwise the tree didn't have height k.
And, if it had a leaf, the leaf has 3 siblings, since the tree is full
4-ary. Thus, the original tree had at least 4 leaves which were
replaced upon trimming by their parent, for a net gain of 3, and hence
the original tree has at least 3k-2+3 = 3k+1 leaves.
================================================================
PROBLEM 6: Inductive Proof (Ryan and Lance)
Rubric for Problem 6 (10 points total)
Base cases (3 points)
checking for:
correct base cases n=0,1
use of definition of function at base values
evaluating prospective closed form at base values
verifying that these agree
Notes:
extra base cases are okay
Order of equality matters!
need to start from facts and use forward flowing implications to arrive at desired result
2nd most common error was WTS: gets at most 1pt
instead of verifying that the two functions agreed
some students just asserted from the start that they were the same
once this is so blatantly asserted, a proof can no longer be given
since the desired result is now in the list of what is presumed to be true
unless it is prefaced with phrases like 'Want To Show', 'WTS', 'does',
'testing whether', or 'is it true that', etc;
writing an equals sign means you are asserting an equality to be true
the solutions for hw7 clearly explained this logical fallacy in all 3 problems
and warned against making this error
the rubric for hw7 clearly said to take off points for this error,
you should have collected your hw and learned from this error before taking the exam
Inductive hypothesis (3 points)
checking for:
uses strong induction
indication that this is an assumption
eg: 'assume' or 'suppose'
correct formula for the proposition
recursively defined function = prospective closed form
correct bounds on n
must include bases
correct lower bound on k
Notes:
Inconsistencies between IH and IS: lose 1pt
eg: IH n=0,...,k and then prove the prop for n=k
most common error: lose 0.5pt
fail to put a lower bound on k, or put the wrong one
if the bound is too low then the IS will be trying to use
the recursive part of the def for base values where it doesn't hold
if the bound is too high then the IS will never be applied
and the claim will have only been proven for at most the base values
the bound has to be just write:
if n=0,1,...,k then k>=1 (so k+1>=2)
if n=0,1,...,k-1 then k>=2 (so k-1+1>=2)
Inductive step (4 points)
checking for:
in terms of k instead of n
that the prop is being checked for the next value
use of recursive definition
using IH twice
correct algebra
arrived at the desired result