EVALUATION STRATEGY AND COMMON MISTAKES --------------------------------------- -------------------------------------------------------------------------------- Q1,2,3 are corrected by AH -------------------------------------------------------------------------------- Q1 -- Propositional Logic Encoding missing / wrong [-4] Formal Deduction and Solving missing / wrong [-6] Predicate-logic instead of propositional encoding -- Formulation without propositions [-4] -- Deduction through predicate-logic rules [-6] Deduction only with Textual Statements [-2] Wrong Deduction [-5] Q2 -- Loop Invariants not considered / wrong [-7] Loop Invariants not / wrongly proven [-5] Loop Termination Guarantee not proven [-2] Arguments for integer v not present [-2] Only described the Algorithm textually [-9] Q3(a) ----- Trivially proven only with same n values for x1 and x2 [-5] Error in the proof with contradiction -- Logical mistake in the proof [-4] -- Inequality comparison has mistake [-3] Only shown set of non-overlapping intervals for x and f(x) [-4] Q3(b) ----- Proven the statement (totally wrong) [-4] Only stated false (without or wrong justification) [-3] Found more elements (apart from {0}) in the range of f(x) [-2] -------------------------------------------------------------------------------- Q4,5,6 are corrected by AD -------------------------------------------------------------------------------- Q4(a) ----- Two marks each for proving reflexivity, antisymmetry, and transitivity. Reflexive: Generally no issues Anti-symmetric: All cases should be carefully considered. Two possible ways: (1) Prove that a != b leads to a contradiction (2) Handle the two cases "a is even" and "a is odd" Lack of handling all the cases carefully [-1] Transitive: Handle all cases carefully. Two possibilities again. (1) Consider the four possibilities a = b = c, a = b but b != c, a != b but b = c, and both a != b and b != c. (2) One of the elements a, b, c is even and is odd. Lack of handling all the cases carefully [-1] (For example, many said if a is even and b is odd (this case may arise), then there is no c such that b is related to c. The correct conclusion is that this forces b = c.) More errors/omissions: Marks deducted on a case-by-case basis Proving not symmetric (asymmetry) [-2] This is not part of a partial-order proof. For example, equality is both symmetric and antisymmetric (so both a partial order and an equivalence relation). Q4(b)+(c) --------- Both answers are NO. No marks for telling the correct answer without justification. Need counterexamlpes. Setting up a theoretical argument implies only the possibility (but not the existence) of counterexamples. [-2] (each) Part(b): Mentioning only one directed pair (like 1 is not related to 5) is not sufficient (you should also mention that 5 too is not related to 1). [-2] Part(c): Use of Hasse diagram. Hasse diagram is only a pictorial presentation of a poset. You must mention how the picture helps you to construct a counterexample. [-2] glb or lub does not exist. Of what? [-2] Q5(a) ----- Fixing n [-1] Fix an n and prove using bijection with S or by diagonalization that a SUBSET of T1 is uncountable. Some said that T1 is the union of all such fixed-n subsets. But the union is not disjoint, so duplicate counting must be avoided. One more sentence is needed to complete the proof: If a subset of T1 is ucountable, T1 itself has to be uncountable. Invalid diagonalization proof [-5] Many answers contain such proofs (without fixed n). It is needed to show that IRRESPECTIVE OF the initial listing, the new sequence produced MUST BE in T1. Without this, no diagonalization proof is valid in any slightest sense. Using countability of T2 [-5] S is the disjoint union of T1 and T2. Some answers proved the countability of T2 independently in Part(a). As clearly stated in the question, it is forbidden to use the countability of T2 (the result of Part(b)). Proving countability [-5] Stating uncountability without justifiation [-5] Q5(b) ----- Failing to count the string 000...0... (all zeros) [-1] Failing to count the string 111...1... (all ones) [-1] Claiming |T2| = 2 (or some finite positive number) [-4] Claiming |T2| = 0 [-5] Proving uncountability [-5] Stating countability without justifiation [-5] Q6 -- Five marks for identifying that pn = 0 if and only if n has an odd number of divisors. Five marks for completely characterizing those n which have odd numbers of divisors. One mark deducted for failing to mention that n has to be a perfect square. GENERAL ------- In the question paper, it is mentioned in the Instructions: Write all the proofs in mathematically precise language. Unclear and/or dubious statements would be severely penalized. Whatever you have written and is understood by us is what you meant. What you had in your head is not our concern. It is your duty to write sensibly and force a reader to understand. It is not our duty to dig out what you have implied but have not written.