Lecture notes
Lecture 24 (12/06/2005):
Algorithms and Complexity.
-
Lecture 23 (12/01/2005):
Combinatorial circuits and normal forms.
-
Lecture 22 (11/29/2005):
Planar graphs.
- Section 10.5.1 and Theorem 10.14.
-
Lecture 21 (11/22/2005):
Trees.
-
Lecture 20 (11/17/2005):
Graphs.
-
Lecture 19 (11/15/2005):
Equivalence relations.
-
Lecture 18 (11/03/2005):
Relations.
-
Lecture 17 (11/01/2005):
Composing Functions & PHP.
-
Lecture 16 (10/27/2005):
Functions and their properties.
-
Lecture 15 (10/25/2005):
Permutations and Combinations.
- Sections 5.1.2-4, page 234-236.
-
Lecture 14 (10/20/2005):
Multiplication principles.
-
Lecture 13 (10/18/2005):
Solving recurrence relations.
-
Lecture 12 (10/13/2005):
Recurrence relations.
- Def 7.3, 7.5, Example 7.15, 7.18, 7.20, 7.21.
-
Lecture 11 (10/11/2005):
Combinatorial proof.
- Def 2.4, 2.9, Thm 5.9, Example 7.15.
-
Lecture 10 (09/29/2005):
Strong induction.
-
Lecture 9 (09/27/2005):
More induction.
- This is hard to see, but in the two last underlined "Inductive steps"
the > signs are actually greater-than-or-equal signs.
- Appendix B, Pages 119,126-128.
-
Lecture 8 (09/22/2005):
Proof by induction.
-
Lecture 7 (09/20/2005):
Well-orderedness and more on divisibility.
- Definition 3.9, page 98-100, 111, section 3.2.5, case n=2 of Proposition 3.9.
-
Lecture 6 (09/15/2005):
Predicate logic, contrapositive and contradiction.
- Pages 63-66, 109, Def 3.5, 3.6, and sections 3.2.3 and 3.2.4.
-
Lecture 5 (09/13/2005):
Sets and Quantifiers.
- Definitions 2.1,2.2,2.5,2.14; Proposition 2.2,2.3;
Table 2.1 (remainder); pages 61,62,107,108.
-
Lecture 4 (09/08/2005):
Sets.
- The book covers all standard set definitions in section 2.1
on just a few pages. We will be a bit more gentle and introduce
these definitions only as and when we need them.
- Examples 2.2,2.3,2.8; Definitions 2.6-2.8,2.14; Table 2.1 (first half).
- Our definition of set does not require the concept of a universal
set (more about this next time) -- ignore all references to universal
sets for the moment (such as Example 2.1).
-
Lecture 3 (09/06/2005):
Counterexamples and Propositional logic.
- Sections 2.3.1-2.3.7 and 2.4.1.
- Our definition of logical equivalence is slightly simpler, but
equivalent to that in 2.3.7.
-
Lecture 2 (09/01/2005): Proofs.
- Pages 102-104,137-138. (See also 29-32, if you like.)
-
Lecture 1 (08/30/2005):
Definitions and Theorems.
- Pages 33, 89, 91-93 (except for examples), 95-96 (except Theorem 3.1),
Definition 3.11.
- Definitions 3.7, 3.8 are slightly different from the textbook.
In general, if there is a disagreement between the lecture notes and
the book, then the lecture notes have priority. In case of doubt,
email me.