Assignments

To recieve any marks on an assignment, you must follow these rules:

• Submit the assignment using MarkUs.
• Typeset the assignment using LaTeX, and submit both the LaTeX source and a compiled pdf.
• Include the following information on the first page (see Collaboration and academic integrity):
  • All people you discussed the assignment with (even briefly), or "No outside discussion" if you didn't talk to anyone other than the instructor or TAs.
  • All material you used, other than official course material or your own lecture notes. If you didn't use any other material, write "No extra material consulted".

Assignment 10

Due at 11:59pm on Monday, April 13.

• Assignment 10
• LaTeX template; image file used by the template.

Assignment 9

Due at 11:59pm on Wednesday, April 1.

• Assignment 9 solutions
• Assignment 9 (Updated March 27: crossed out part of question (a).)
• LaTeX template

Grading notes:

• Part c: Some people proved a loop invariant that was not useful. Generally these got at most 10/20.
• Part d: Some people did not justify why i=len(A) after the last iteration (7/10) or wrote proofs that were not clear (5/10).
• Part e: 17/20 for very minor mistakes; 15/20 for larger mistakes that are still simple to fix; 10/20 for some solutions with the right approach but are incomplete, lack clarity, or contain many mistakes to the point that they disturbed the flow of the argument.

Assignment 8

Due at 11:59pm on Wednesday, March 18 March 25.

• Assignment 8 solutions
• Assignment 8
• LaTeX template

Assignment 7

Due at 11:59pm on Wednesday, March 11.

• Assignment 7 solutions
• Assignment 7
  • Hint added at the end of part (b) Monday March 9. Download the pdf again to see it.
  • Minor correction added to part (a) on Monday March 9: replaced \( n f(n) \) with \( (n+1) f(n) \).
    • If you already wrote your answer, no need to change it! We will accept answers that use \( n f(n) \).
    • The reason for the change is that \( n f(n) \not\in \mathcal{F} \); see the updated a7.pdf for details. We'll ignore this issue when grading part (a), so again, if you've already answered it, don't worry.
• LaTeX template

Grading notes:

• Part (a) -- 20 marks total
  • 20/20: A correct solution.
  • 15/20 or 10/20: A solution that forgot to take into account some minor aspects of the definition of big-O

• Part (b) -- 40 marks total

  • 40/40: A correct solution.
  • 39/40: A correct solution, but poorly presented. Check the annotation to see the issue.
  • 30/40: A solution that is almost correct, but contains an erroneous step that can be fixed with some minor revision.
  • 20/40: A solution with the right idea, but either is missing multiple crucial steps or misinterpreted the basic definition of Big-O.
  • 10/40: An overall incorrect solution, but showed some steps that might be helpful in solving the problem.

  Some people defined g(n) as an infinite sum \( f_0(n) + f_1(n) + f_2(n) + \dotsb \), which will not work since this sum won't converge for any n.

  Some others defined \( g(n) \) to be \( (n+1) f_i(n) \) for a specific \( i \). This won't work as it is possible for some other function down the sequence to be larger than \( g \).

  A few people also forgot to consider the constant \( c \) in big-O, so they effectively only proved the case where \( c = 1 \).

Assignment 6

Due at 11:59pm on Wednesday, March 4.

Warning: this assignment is due two days after the midterm. You should probably get started on it early, so you also have time to study.

• Assignment 6 solutions
• Assignment 6
  • Updated Feb 14 and 18: see this thread and this thread.
  • If you need help understanding Q1, try this thread, which contains a different way to write Theorem 1.
• LaTeX template

A couple of notes on Question 1:

• Some people took the minimum of some set but forgot to argue why the minimum can't be zero.
• Some submissions did not use well-ordering, even though the question asked for it. Some mentioned the fact that some set had a minimum element but didn't actually use that fact. These solutions got at most 35/50.

Assignment 5

Due at 11:59pm on Wednesday, February 12.

• Assignment 5 solutions
• Assignment 5
• LaTeX template

Grading notes:

• We decided to give Q2 a bit more weight than Q1 (60 vs 40). Several people had trouble applying basic definitions in Q1.
• Question 1:
  • Some people misunderstood the definition of logical equivalence or truth assignment.
    • Some people assumed that "A and B aren't logically equivalent" means the same thing as "A is logically equivalent to NOT(B)". In fact, "A and B aren't logically equivalent" just means there exists at least one truth assignment for which A and B have different truth values.
    • Some people used some incorrect laws of propositional formulas. For example, thinking (A AND B) IFF C is equivalent to (A IFF C) AND (B IFF C) (not correct: e.g. take A=true, B=false, C=false) or that NOT (A IFF B) is equivalent to NOT(A) IFF NOT(B) (not correct: e.g. take A=true, B=false).
  • Grading scheme:
    • 40/40: A sound and complete solution.
    • 36/40: Solution that is correct but with minor errors, mostly of a cosmetic nature.
    • 32/40: Solution that is sound and mostly complete.
    • 24/40: Solution with the right general idea, but is either missing a critical piece of argument or contains an erroneous step that can fixed with some effort.
    • 0-16/20: Part marks for: setting up a structural induction correctly; and/or a non-trivial attempt on the problem that correctly uses definitions in propositional logic (e.g. logical equivalence, truth assignment).
• Question 2:
  • Most people got the idea of strengthening the induction hypothesis, though it wasn't always presented well.
  • 10 Marks: Base Case + Strengthening the induction hypothesis.
  • 10 Marks: Arguing that -x is an integer.
  • 30 Marks: Using the strengthened induction hypothesis to show that the fraction part is an integer.
  • 10 Marks: Clarity / formatting.

Assignment 4

Due at 11:59pm on Wednesday, February 5.

• Assignment 4 solutions
• Assignment 4 (Updated January 31 to incorporate the below hint.)
• LaTeX template (a4_template.tex)

Note:

• For a small hint on question 2, see this forum thread.

Question 1 (added March 25):

The grader left many comments, mostly around proof techniques. Some of the more common ones:

• Use of a Lemma: prove smaller sizeable subcomponent(s) of your proof at the beginning in a Lemma. When you use it in your main proof, you can then easily cite it.
• Cite all theorems/facts you use, e.g. Lemma, inductive hypothesis, geometric sum etc. You do not, however, need to cite basic algebra.
• It's common to end your proof with a QED.
• Proving (simple) induction: when showing that \( P(n+1) \) is true, try to leave it in exactly the \( P(n+1) \) form rather than further simplifying it. e.g. leave it in \( 2^{-(n+1)} + (n+1) - 1 \) rather than \( 2^{-(n+1)} + n \)

The most common mistake:

• Base Case: be careful where you start. It will not always be \( P(0) \) (in this case, you had to start at \( P(1) \)).

On Question 2, the most common mistakes were:

• Failing to properly handle small values of \( n \) in your induction argument. For example, the relation \( A(n) = 2 (n-1) + \sum_{ i=1 }^{ n-2 } A(i) A(n-1) \) is not true when \(n = 2\), and is unclear in meaning when \(n=3\) (because you have a sum starting at 1 and ending at -1). So, if you use that relation in your induction step, you shouldq say you're assuming \(n > 3\), and separately handle \(n \le 3\), either as separate case(s) of your induction step or by adding base cases.
• Not justifying why it's possible to split the sum into two groups.

Assignment 3

Due at 11:59pm on Wednesday, January 29.

• Assignment 3 solutions
• Assignment 3
• LaTeX template (a3_template.tex)

Graders' notes:

• Question 1:
  • 0/50: The solution was completely lacking either in content, or structure. Not a formal proof, and no justification given.
  • 10/50: The solution had the "correct" answer, normally taking \( c = c_1 + c_2 \), but was not a correct formal proof or did not give nearly enough justification for any of their steps.
  • 20/50: The solution had the correct answer, and parts of a formal proof, but some major mistakes. Often this was providing very little justification, skipping MANY steps, using "arithmetic" to justify a statement that really needs to be proven in its own indented block. These solutions normally at least had the formal proof structure.
  • 30/50: The solution is a formal proof with some mistakes, or one major one. Often students didn't introduce \( n \) as an arbitrary variable, and use "arithmetic" to justify jumping between statements that are universally quantified. Solutions with a lot of typos / missing steps also got this mark. However, these solutions did provide better justification, good structure, and are mostly correct outside of the mistake.
  • 40/50: The solution is a formal proof with some minor mistakes. At this point, the solutions is basically correct, and there are only small issues. Sometimes students skipped steps line introducing a variable from an existentially quantified statement, used incorrect justifications for a few steps. Overall, these are good solutions.
  • 45/50: Some solutions got this, normally because of a couple minor mistakes that I think warranted pointing out. Things like not giving justification for \( c \in R \), and not mentioning that transitivity of \( \ge \) is being used. Solutions that laid everything out correctly, but skipped (in my opinion) too many steps also got this.
  • 50/50: A pretty much perfect solution. I ignored (obvious) typos, and nor using the exactly correct justification name, but everything is justified in one way or another, and every step follows very clearly from the ones mentioned.
• Question 2: Since Question 1 already tested the students on their ability to write a formal proof, grading for Question 2 is focused on testing whether students have the ability to formulate intuitions into a sound and complete mathematical proof. As such, solutions with little technical justifications will receive very little marks.
  • 50/50: A sound and complete solution, possibly with negligible mistakes and some typos.
  • 45/50: A solution that is almost correct, but with minor issues, mostly of a cosmetic nature.
  • 40/50: A solution that is almost correct, but with a major mistake. Submissions in this category often missed a corner case, or made a wrong step in reasoning that could easily be avoided if done a little bit differently. Solutions that skipped very few important steps also belong here.
  • 30/50: A solution with a right general approach, but nevertheless failed on execution. Submissions in this category often have made a (or a few) wrong step(s) in reasoning that might need some revision.
  • 20/50: A solution with a wrong approach, but contains a considerable amount of technical details required to form a correct solution; A solution with a right general approach, but skipped way too many critical steps in its reasoning.
  • 10/50: An overall wrong solution, but successfully solved some corner cases.

Assignment 2

Due at 11:59pm on Wednesday, January 22, unless you enrolled after on or after January 17. If you enrolled on or after January 17, it's due at 11:59pm on Monday, January 27, and there might be special submission instructions: check the website after January 23 (update: please just submit via MarkUs, and I'll manually recalculate the late penalty if you enrolled on or after January 17. Email me if you have trouble.). (Updated January 21: changed "after" to "on or after".)

• Assignment 2 solutions
• Assignment 2
• LaTeX template to help you write your answers in LaTeX.

Common mistakes and grader's notes:

• Question 1:

  • Rubric for each part:
    • 10: Coming up with the correct English sentence
    • 5: Reasoning that whenever the formula is true, the sentence should be true as well
    • 5: Reasoning that whenever the sentence is true, the formula should be true as well
  • "A lot of the students missed the last part. I annotated these solutions with 'Missing the semantic to syntax direction'. One other common mistake was giving solutions that were similar to the bad example given in the question."

• Question 2:

  • Some submissions argued it's not valid because it's false when the domain is empty. However, interpretations must have a non-empty domain. See for example online lecture 4.
  • There were many errors related to quantifiers, including:
    • "The order of mixed quantifiers matter. I found a very concise resource that explains this well so I cited it for them: link"
    • Many submissions claimed \(a(x)\) IFF \(\forall y \in D .\> b(x, y)\) is logically equivalent to \(\forall y \in D .\> (a(x)\) IFF \(b(x, y))\), but they are not: for example, take \(D = \{0, 1\}\), \(x = 0\), \(a(0) =\) F, \(b(0, 0) =\) F, \(b(0, 1) =\) T: then the first formula is true but the second one is false.

Assignment 1

Due at 11:59pm on Wednesday, January 15.

• Assignment 1 solutions*
• Assignment 1
• LaTeX template to help you write your answers in LaTeX.

* Added January 29 3:10pm: for Question 1 only, if you are not sure how your grade was computed, feel free to submit a re-mark request to ask. For Question 2, the regular re-marking policy still applies: i.e. you must include a specific reason; we might re-mark your entire assignment; and your grade may go up or down.

Before submitting any re-mark requests, please read this description of how the questions were graded.

• Question 1: The person doing the grading considered many comparisons and trade-offs when giving the final grade. The following is a guideline only, since there are different ways to put together a solution.
  • 5: Realizing that (true MYS true) should be (false).
  • 5: The witness for the existential quantifier (x_0) cannot be between 5 and 10
  • 10: (x_0) is either greater than 10 or less than 5. Therefore, either (true MYS false) or (false MYS true) is (true)
  • 5: (true MYS false) should be equal to (not (false MYS false))
  • 5: (false MYS true) should be equal to (not (false MYS false))
  • 5: (false MYS false) is (false)
  • 5: (true MYS false) and (false MYS true) are (true)
  • 10: for giving the correct truth table (without any reasoning)
• Question 2:
  1. Formula Semantics (30 marks): This category checks that you correctly expressed a predicate in first order logic. Marks from this section were mostly assigned following a ternary scheme. Correct formula (with possibly negligible typos): 30 marks. Minor but noticeable issues: between 20 to 25. Major issues but with the right approach: 15. Otherwise 0.
  2. Formula Syntax (10 marks): This category checks whether your answer uses the language of predicate logic and only the syntax permitted by the problem. 3 marks were deducted for each type of mistake, up to a maximum of 10 marks. Some common mistakes include grouping quantifiers, and significant readability issues due to not parenthesizing subformulas. Note that if you used syntax not allowed by the question or not allowed in first order formulas in general (such as defining as many variables as the length of the input string using "...", or such as defining the formula recursively) it automatically received a grade of 0 from this section; this usually lead to a 0 for the entire question.
  3. Word reasoning (10 marks): This category checks if you demonstrated the correct intuition about the approach and were able to explain your solution.

Note: if you were not enrolled on January 10, e.g. because you were on the waitlist, I won't count your grade for Assignment 1. I'll replace it with an average of other grades. However, I still recommend trying it, and you're welcome to ask me for feedback after I've posted the solutions.

Clarifications on allowed syntax:

• "..." isn't on the list of allowed syntax. For example, you can't write \(\forall x_1 \in D.\forall x_2 \in D.\cdots\forall x_n \in D.\)
• \(P(s)\) isn't on the list of allowed syntax, so you can't use P inside your definition for P. In other words, you can't define it recursively.
• A clarification on "You may define and use any new predicates if the domain of every variable of your predicates is \(\mathbb{N}\)" --- inside the definition of these new predicates, you don't need to follow the syntax rules. You can write the definition in English if you like. The only rule is that the domain of every variable in these predicates must be \(\mathbb{N}\).

Practice non-assignment

This is not a real assignment. It will not count toward your grade. But you should try submitting it, to make sure you have LaTeX working, and to make sure you can submit with MarkUs.

• The assignment: practice_non_assignment.pdf
• LaTeX template to help you: practice_template.tex
• The solution is just the LaTeX source of the assignment: practice_non_assignment.tex.
  • I'm posting it right away since this is only for practice, but please try the assignment before looking.

Submitting assignments

Submit through MarkUs here. Use your CDF login and password. Email me if you have trouble.

Note: if you are not enrolled in the course (e.g. you are on the waitlist), you will probably not be able to submit through MarkUs. If you enrol in the course after an assignment is due, you don't need to submit that assignment. Please email me if you have any questions.

Late assignments

If you submit an assignment after the deadline, you'll lose 5% for every full hour since the deadline passed until your grade for that assignment reaches zero. If you re-submit an assignment, the time of your last submission will be used for this calculation.

Example: suppose the assignment is due at 11:59pm on January 15. You submit it early, at 3:30pm, then you submit an updated version at 2:59am on January 16, and you make no further submissions. Then if you would have otherwise gotten 80% on the assignment, you get 65% instead, since you last submission was three hours late.