More stuff

Final take-home assessment

• Questions; solutions

From class

I recommend taking notes during lecture, since the material here isn't guaranteed to cover everything that was said in class (the slides might not make much sense when you look at them later), and because taking notes will help you remember the material.

See also the Topics page, which lists reading related to each topic covered in the course.

There are two kinds of file here:

• The slides that I write on during class.
• For week 4 (and possibly beyond), rough notes based on my own notes I prepared for the lecture.

The files:

• Week 1 lecture: Annotated slides
• Week 2 problem session: Annotated slides
  • Based on 2019 Problem Sessions 2-4
• Week 3 problem session: Annotated slides
  • The first three problems are from 2019 Problem Session 5, but the last isn't listed elsewhere on this site.
• Week 4 lecture: Rough notes (LaTeX source), Annotated slides
• Week 5 lecture: Rough notes (LaTeX source), Annotated slides
  • Updated February 5: Corrected the induction template on the first page of the rough notes. (See page 3 of the annotated slides: I accidentally wrote P(n) in a few places where I should have written P(k).)
• Week 6 lecture: Rough notes (LaTeX source), Annotated slides
• Week 7 lecture: Rough notes (LaTeX source), Annotated slides
• Week 8 lecture: Rough notes (LaTeX source), Annotated slides. This week's lecture was only 50 minutes.
• Week 9 lecture: Rough notes (LaTeX source), Annotated slides.

Midterm

• The midterm. A correction and some clarifications that were announced during the midterm are given after questions 4 and 5.
• Solutions (Updated ~2pm March 3: correction to Q5 solution: replaced "removing the largest element" with "removing the smallest element" at the start of Solution B.)

Grading notes:

• Question 1:
  • To get more than 2/5, the solution had to say \( a \not= 0 \).
• Question 2:
  • For 10/10, solutions had to specify an interpretation that makes the formula false and one that makes it true.
  • Some solutions lost marks for trying to specify different predicates for \( P(x) \) and \( P(y) \). (They're both \( P \).)
• Question 3:
  • Notes about the constructor case:
    • Verify both upper and lower bounds: as a quick check to yourself to see if you only have to prove the lower bound \( i \geq 1 \), simply plug in some larger values of \( i \) for both constructor cases (or just look to see what values of \( i \) the statement no longer holds true).
      • Once you have established the upper and lower bounds, please prove it holds for BOTH upper and lower bounds of BOTH constructor cases.
• Question 4:
  • Proofs that are correct except for some minor mistakes, or that don't have enough explanation, generally got 15/20, or 18/20 if the mistakes were really minor.
  • Proofs that handled one important case but missed other(s) generally got 10/20.
• Question 5:
  • For proofs that were structured something like Solution B in the official solutions:
    • Noting that you can repeatedly remove the maximum element (or the minimum or both) to get a sequence of elements was generally worth 4/20.
    • Using max and/or min on the resulting sequence of elements to find a stopping point, or some similar argument, was worth an additional 4-8 marks, depending on whether the argument was complete.
    • Showing that this means \( A \) must be finite (or, for contrapositive proofs, arguing that every time an element is removed \( A \) remains infinite) was worth up to 4 more marks.
    • Adding up the three points above would give up to 16/20. The remaining 4/20 marks went to clear and well-organized proofs without (significant) mistakes.
  • For proofs structured more like Solution A in the official solutions, or some other variation, we applied similar criteria, but adapted for that style of proof.
  • Some proofs were completely different from Solution A or Solution B. We handled those on a case-by-case basis, with the same principle that a proof that is essentially correct is worth from 16/20 to 20/20 depending on whether there are significant mistakes and whether the proof is clear and well-organized.

Sample problems

• 2019's CSC240 sample midterm; solutions
  • Note: last year, students had 50 minutes for the midterm. This year, you'll have 1 hour 50 minutes, so the midterm will be longer.
  • Note: last year's students had a slight advantage on question 1(a) since it is related to Problem 3 from 2019 Problem Session 3 (available below). You should still be able to solve it, though.
  • Solutions will be posted on February 28. Please try the questions before then! (Update: solutions are posted. Please try the questions before looking at them.)
• 2019 CSC240 midterm; solutions
  • This is the actual midterm that was given last year.
  • Last year, students had 50 minutes for the midterm. This year, you'll have 1 hour 50 minutes, so the midterm will be longer.
  • The definition of "well-ordered" in question 2(b) is slightly different from the one we're using this year. The relation \(\preceq\) isn't a total order, so under our definition, it wouldn't be considered a well-ordering. However, it is still a partial order, and still has the property that every nonempty set \(C\) has a "smallest" element --- meaning there exists \(x \in C\) such that for all \(y \in C\), either \(x \preceq y\) or \(x\) and \(y\) are incomparable.
  • Solutions will be posted on February 28. Please try the questions before then! (Update: solutions are posted. Please try the questions before looking at them.)

Slides from 2019 problem sessions

These cover what was discussed in class in weeks 1-3 last year. There is a lot of overlap with the Week 2 and 3 problem sessions this year, because most of my problems were re-used from these. Each problem session was done in class after students watched the corresponding online lecture video.

• 2019 Problem Session 1
• 2019 Problem Session 2
• 2019 Problem Session 3
• 2019 Problem Session 4
• 2019 Problem Session 5
• 2019 Problem Session 6

Quizzes

• Week 1 quiz; solution
• Week 2 quiz; solution
  • (Won't be counted since not everyone was able to write it.)
• Week 3 quiz; solution
• Week 4 quiz; solution
• Week 5 quiz; solution
• Week 6 quiz; solution
• Week 7 quiz; solution
• (There was no quiz on week 8.)
• Week 9 quiz; solution
• Week 10 quiz; solution
  • Optional Latex template in case you decide to use Latex and want a starting point.
• Week 11 quiz; solution
  • Optional Latex template in case you decide to use Latex and want a starting point.

Tutorials

• Week 1 regular tutorial slides
• Week 2 regular tutorial slides
• Week 3 tutorial: Proving properties about sets; some slides; more slides
• Week 4 tutorial: An example induction problem; Proving the complete induction axiom using simple induction
• Week 5 regular tutorial notes (Latex source)
• Problems from Week 6 tutorial (Latex source)
• Week 7: midterm review
• Week 9 regular tutorial problems; solutions
• Week 10:
  • Practice problems: part 1 (This corresponds to the material in the first lecture video.)
  • Solutions for Part 1
  • Practice problems: part 2 (This corresponds to the material in the second lecture video.)
  • Solutions for Part 2
• Week 11 tutorial problems; solutions
  • This covers the first two videos. If I make a third video this week, any corresponding problems will go in next week's set.
  • March 30: minor correction to the problems: 1(b) and 3(c) described sets \( \{ x \in \Sigma^* \mid q \in \delta^*( s, x ) = q \} \) for NFSAs. The extra "\( = q \)" at the end didn't make sense and has been deleted.
• Week 12 tutorial problems; solutions

LaTeX resources

• There's some information about installing LaTeX on the LaTeX project website. If you don't want to install it, you can also make an account at overleaf.com.
• There's a variety of documentation online. The Not So Short Introduction to LaTeX2e is a great guide, but it is long. There's plenty of other documantation, e.g. here's the overleaf.com documentation page.
• Try the practice non-assignment on the Assignments page.