# Lectures, Tutorials, Course Outline, and Learning Objectives

## Lecture notes

Course Notes for CSC165H (PDF)
by Gary Baumgartner and Danny Heap and François Pitt.

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

1. Sep 10–Sep 16: pages 1–18 (Chapters 1, 2)
2. Sep 17–Sep 23: pages 18–25 (Chapter 2)
3. Sep 24–Sep 30: pages 25–32 (Chapter 2) — plus a problem-solving exercise: "Penny Piles"
4. Oct  1–Oct  7: pages 33–38 (Chapter 3)
5. Oct  9–Oct 14: pages 38–42 (Chapter 3)
6. Oct 15–Oct 21: pages 42–48 (Chapter 3) — plus a problem-solving exercise: "Origami Enigma"
7. Oct 22–Oct 28: pages 49–54 (Chapter 4) — plus a handout with extra proof examples (PDF) / extra proof examples (.tex)
8. Oct 29–Nov  4: pages 54–57 (Chapter 4)
9. Nov  5–Nov 11: pages 57–60, and Exercise 5 on page 64 (Chapter 4) — plus a problem-solving exercise: "Product of Sums"
10. Nov 14–Nov 20: pages 60–65 (Chapter 4)
11. Nov 21–Nov 27: pages 69–72 (Chapter 5)
12. Nov 28–Dec  5: pages 72–78 (Chapter 5)
See the Tests/Exam page for advice about studying for and writing the final exam.
13. Materials from the "Exam Jam" on Dec 6th: Examples of reductions, Big-Oh questions from December 2011 Exam — both updated at 17:29 on Fri 7 Dec.

## Tutorial notes

Every week, a tutorial exercise will be posted below. This exercise will contain some number of problems that you should be able to solve easily given that week's lecture material. Think of the tutorial exercise as an "early warning system": if you have any difficulty solving it, then this is a strong indication that you need to review the lecture material and ask questions.

During tutorials, the TAs will go over the week's exercise and make sure that everyone understands how to solve them. This will be followed by a brief (10 minute) quiz at the end of each tutorial.

Tutorial exercises and their solutions 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.

1. Sep 13 / Sep 17: Tutorial 1 Exercise (PDF) / Tutorial 1 Solution (PDF) / Tutorial 1 Source (.tex)
2. Sep 20 / Sep 24: Tutorial 2 Exercise (PDF) / Tutorial 2 Solution (PDF) / Tutorial 2 Source (.tex)
3. Sep 27 / Oct 1: Tutorial 3 Exercise (PDF) / Tutorial 3 Solution (PDF) / Tutorial 3 Source (.tex)
4. Oct 4 / Oct 8: no tutorial (because of Thanksgiving on Oct 8)
5. Oct 11 / Oct 15: Tutorial 4 Exercise (PDF) / Tutorial 4 Solution (PDF) / Tutorial 4 Source (.tex)
6. Oct 18 / Oct 22: Tutorial 5 Exercise (PDF) / Tutorial 5 Solution (PDF) / Tutorial 5 Source (.tex)
7. Oct 25 / Oct 29: Tutorial 6 Exercise (PDF) / Tutorial 6 Solution (PDF) / Tutorial 6 Source (.tex)
8. Nov 1 / Nov 5: Tutorial 7 Exercise (PDF) / Tutorial 7 Solution (PDF) / Tutorial 7 Source (.tex)
9. Nov 8 / Nov 12: no tutorial (because of Fall Break on Nov 12, 13)
10. Nov 15 / Nov 19: Tutorial 8 Exercise (PDF) / Tutorial 8 Solution (PDF) / Tutorial 8 Source (.tex)
11. Nov 22 / Nov 26: Tutorial 9 Exercise (PDF) / Tutorial 9 Solution (PDF) / Tutorial 9 Source (.tex)
12. Nov 29 / Dec 3: Tutorial 10 Exercise (PDF) / Tutorial 10 Solution (PDF) / Tutorial 10 Source (.tex) —updated at 16:16 on Sat 8 Dec (fixed a small typo on the last line of the first solution)

## 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.

• Logical Notation [3 weeks]
• Proof Techniques [3 weeks]
• Algorithm Analysis [4 weeks]
• Computability Theory [2 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),
• understand what it means for a function to be "computable", and be able to generate simple reductions to show that specific functions are non-computable.