University of Waterloo
CS240 Spring 2022 Assignment 1 Post-Mortem
This document goes over common errors and general student performance on the assign- ment questions. We put this together using feedback from the graders once they are done marking. It is meant to be used as a resource to understand what we look at while marking and some common areas where students can improve in.
• A few students submitted blurry pictures of their handwritten answers. In accordance with the course policy, one mark was deducted from each question for difficult-to-read submissions.
• Properties that were not used or derived in course material must be proved before being used.
• Some proofs were not sufficiently detailed, or many steps were skipped along the way. Your work should give a clear idea of what is being done, with justification for non- obvious steps.
Question 1 [3+3+4=10 marks]
• When proving order notation from first principles, explicit values for c and n0 that satisfy the relationship must be given.
• The values c and n0 should be derived rather than guessing and stating them first and then proving they are valid.
Question 2 [3+3+4=10 marks]
• Many students forgot to mention what rule or theorem (e.g. l’Hopital’s rule) they used in their proof and instead jumped to the next step without any justification.
• Many students forgot that the derivative of log2(n) is 1 rather than 1 (the derivative nlog2 n
of ln(n)).
• While using the limit rule, a few students calculated limn→∞ g(n) instead of limn→∞ f(n) f (n) g(n)
and thus reached the incorrect answer.
程序代写 CS代考 加微信: cstutorcs
Question 3 [4+4+4+4+4=20 marks]
• For a), some students forgot to explicitly state a value of n0 when proving that f(n) ∈ Ω(g(n)).
• For b), some students attempted to prove the false statement using the zero function(s) f(n) = g(n) = 0, but the question required f(n) and g(n) to map positive integers to positive integers and 0 is not a positive integer.
• For c), some students attempted to prove the (false) statement using the values of c and n0 from the definition of f(n) ∈ O(g(n)) and stating without proof that these values work for 2f(n) and 2g(n).
• For d). some students attempted to prove the (false) statement by using the limit rule and incorrectly differentiating log(n)log(n).
Question 4 [2+4=6 marks]
• For a), many students used the value n0 = 0 in their proof, but the definition of g(n) ∈ O′(f(n)) applies for all n > 0 and 0 ≯ 0. Thus, a value of n0 that is atrictly larger than 0 would be an appropriate choice.
• For b), some proofs were too informal to be considered correct. At minumum, a correct
proof for this question should define constants c (based on the first few terms of the
sequence g(n) or f(n) ) and a value for n0 such that g(n) ≤ cf(n)) for all n ≥ n0. f (n) g(n))
Question 5 [4+4+5=13 marks]
• A few students did not provide a Theta (Θ) bound like the question asked for and instead proved something else (e.g. O-notation). Remember that both upper and lower bounds need to be proved to get a tight Θ-bound.
• For a), a few students incorrectly wrote Pni=1 i2 ∈ n2 and thus had a Θ-bound of ‘ : xn2 logn instead of n3 logn.
• For b), some students deduced that i with initial value 2 was squared ⌈log n⌉ times instead of ⌈log log n⌉ times by incorrectly stating that 2k ≥ n instead of 22k ≥ n, where k is the number of times i is squared in the loop.
• For a), many students did not state that the children are ordered from left-to-right in the array. An ordering is necessary for the array structure to be unambiguous.
• For b), some students only proved an upper bound. Remember that both upper and lower bounds need to be proved to get a tight bound.
Programming Help, Add QQ: 749389476
• For c), many students reached a final answer of Θ(n3) or Θ(n4) instead of Θ(n3 log n). Note that the partial sum of the harmonic series is in Θ(log n); this can be found in the Useful Sums slide in the course lectures.
Computer Science Tutoring