Lectures, Tutorials, Course Outline, and Learning Objectives

Lecture notes

Title page and Table of Contents
Chapter 1 (Introduction)
Chapter 2 (Quantification, Implication, and Symbols)
Chapter 3 (Logical Connectives)
Chapter 4 (Proofs)—updated at 14:34 on Mon 24 Oct (just the last two pages)
Chapter 5 (Algorithm Analysis and Asymptotic Notation)
Chapter 6 (A Taste of Computability Theory)

Every week, specific sections of the course notes (see above) will be posted as readings. You will be expected to read these sections to prepare for the following week's lectures.

The readings are NOT taken from "How To Prove It", but from the course notes posted just above. Apologies for the original phrasing that made this unclear.

Sep 12–18: pages 1-17 (Chapters 1, 2)
Sep 19–25: pages 18-26 (Chapters 2, 3)
Sep 26–Oct 2: pages 26-32 (Chapter 3) — plus a problem-solving exercise: "Penny Piles" (covered in L5101; to be covered next week for L0101)
Oct 3–9: pages 30-36 (Chapters 3, 4)
Oct 11–16: pages 36-38 (Chapter 4) — plus a problem-solving exercise: "Origami Enigma"
Oct 17–23: pages 38-42 (Chapter 4)
Oct 24–30: pages 42-48 (Chapter 4) — plus a handout with extra proof examples (PDF) / extra proof examples (.tex)
Oct 31–Nov 6: pages 49-52 (Chapter 5) — plus a problem-solving exercise: "Product of Sums"
Nov 9–15: 52-56 (Chapter 5)
Nov 16–22: 56-64 (Chapter 5)
Nov 23–29: 66-71 (Chapter 6, except sections 6.1, 6.2)
Nov 30–Dec 6: 65-66, 71-74 (Chapter 6),
plus a transcript of Francois' notes for the last lecture.
See the Tests/Exam page for advice about studying for and writing the final exam.

Tutorial notes

Tutorial notes will be posted here every week, following the tutorials—because the same material will be covered on Thursdays and on the following Monday, this will happen sometime on Tuesdays or Wednesdays.

Sep 15 / Sep 19: Tutorial 1 Handout (PDF) / Tutorial 1 Solution (PDF) / Tutorial 1 Source (.tex).
Sep 22 / Sep 26: Tutorial 2 Handout (PDF) / Tutorial 2 Solution (PDF) / Tutorial 2 Source (.tex).
Sep 29 / Oct 3: Tutorial 3 Handout (PDF) / Tutorial 3 Solution (PDF) / Tutorial 3 Source (.tex).
Oct 20 / Oct 24: Tutorial 4 Handout (PDF) / Tutorial 4 Solution (PDF) / Tutorial 4 Source (.tex).
Oct 27 / Oct 31: Tutorial 5 Handout (PDF) / Tutorial 5 Solution (PDF) / Tutorial 5 Source (.tex).
Nov 17 / Nov 21: Tutorial 6 Handout (PDF) / Tutorial 6 Solution (PDF) / Tutorial 6 Source (.tex).
Nov 24 / Nov 28: Tutorial 7 Handout (PDF) / Tutorial 7 Solution (PDF) / Tutorial 7 Source (.tex).
Dec 1 / Dec 5: Tutorial 8 Handout (PDF) / Tutorial 8 Solution (PDF) / Tutorial 8 Source (.tex).

Course outline

Lecture topics

The following topics will be covered in this course, in the order listed. For each topic, we have indicated the approximate number of weeks required to cover that topic as well as a list of the relevant sections in the textbook.

Quantifiers and Implication [2 weeks]
Logical Connectives [2 weeks]
Proof Techniques [5 weeks]
Algorithm Analysis [3 weeks]

Learning objectives

By the end of this course, students should:

be able to understand technical communications, written using logical notation,
be able to express themselves clearly and precisely, using logical notation,
be able to derive correct conclusions from logical arguments, and to generate correct logical arguments,
be able to analyze the complexity and correctness of algorithms (up to, but not including, the level of CSC236H1).

CSC 165 H1 "Mathematical Expression and Reasoning for Computer Science" — Fall 2011