Unless otherwise specified, all readings are in RosenBook. As always, the future is uncertain, so you should take parts of the schedule that haven't happened yet with a grain of salt.

# 1. Detailed schedule

- 2007-09-05
WhyYouShouldKnowAboutMath; WhatYouShouldKnowAboutMath; mathematics, truth, and MathematicalLogic. Start of PropositionalLogic. Readings: §1.1–1.2.

- 2007-09-07
More PropositionalLogic. Start of PredicateLogic. Universal and existential quantifiers. Readings: §1.3. More details: /2007-09-07.

- 2007-09-10
More PredicateLogic: nested quantifiers, functions, and equality (with a brief appearance by the PeanoAxioms). Readings: §1.4.

- 2007-09-12
InferenceRules and ProofTechniques. Readings: §§1.5–1.7.

- 2007-09-14
The NaturalNumbers and InductionProofs. Readings: §4.1. More details: /2007-09-14.

- 2007-09-17
SetTheory. Naive set theory vs axiomatic set theory. Elements and subsets. Russell's paradox and the good parts of ZFC. Readings: §2.1.

- 2007-09-19
More SetTheory. Operations on sets (∪, ∩, set difference, Cartesian product, etc.) and proving facts about sets. Readings: §2.2.

- 2007-09-21
Functions. Readings: §2.3.

- 2007-09-24
More Functions. Composition of functions, functions with multiple arguments, monotone functions, sequences. Start of SummationNotation. Readings: §2.4.

- 2007-09-26
More SummationNotation. Computing sums and SolvingRecurrences (easy ones). Readings: §7.1.

- 2007-09-28
HowToCount. The PigeonholePrinciple. Readings: §§5.1–5.2.

- 2007-10-01
More counting: permutations, combinations, and BinomialCoefficients. Readings: §§5.3–5.5. More details: /2007-10-01.

- 2007-10-03
More BinomialCoefficients tricks. Start of GeneratingFunctions. Readings: §7.4. More details: /2007-10-03.

- 2007-10-05
Still more GeneratingFunctions: how operations on sets of objects of differing weights translate to operations on generating functions. Extracting coefficients by differentiating. Extracting coefficients using the binomial theorem.

- 2007-10-08
More GeneratingFunctions: extracting coefficients by partial fraction expansion and the cover-up method. Solving ugly recurrences.

- 2007-10-10
Last of GeneratingFunctions: partial fraction expansion with repeated roots, Catalan numbers.

- 2007-10-12
ProbabilityTheory basics: interpretations of probability, events, axioms, independence. Readings: §§6.1–6.2.

- 2007-10-15
More ProbabilityTheory: inclusion-exclusion, conditional probabilities. Readings: §6.3.

- 2007-10-17
RandomVariables and expectations. Readings: §6.4.

- 2007-10-19
More RandomVariables: conditional expectations and applications.

- 2007-10-22
Still more RandomVariables: Markov's inequality, variance, Chebyshev's inequality.

- 2007-10-24
The

**midterm exam**was given Wednesday, 2007-10-24, at the usual class time in room**SCL 160**. It was be a closed-book, cumulative exam covering all material discussed in lecture prior to the test date.2007 midterm sample solutions: 2007-midterm-solutions.pdf.

2005 midterm sample solutions: 2005-midterm-solutions.pdf.

2005 midterm without solutions: 2005-midterm.pdf.

- 2007-10-26
More RandomVariables: Computing variance of a sum; covariance.

- 2007-10-29
Start of LinearAlgebra: matrices, matrix operations. Readings: §3.8.

- 2007-10-31
More LinearAlgebra: inverting matrices.

- 2007-11-02
More LinearAlgebra: vectors and vector operations. Dot-products. Mx equivalent to dot-product with rows or linear combination of columns.

- 2007-11-05
Last of LinearAlgebra: linear combinations, linear independence, bases, and orthogonal projection.

- 2007-11-07
Start of Relations: basic properties, equivalence relations. Readings: §8.1, §§8.3–8.5.

- 2007-11-09
More Relations: partial orders. Readings: §8.6. See also footnote on definition for partial order in Relations notes. The completely tangential joke about "How to Draw like Leonardo Da Vinci" is originally due to Ben_Edlund, from a page that showed "How to Draw The_Tick" and advertised a sequel called "How to Draw like Albrecht_Dürer."

- 2007-11-12
More Relations: More partial orders: maximum, maximal, minimal, and minimum elements; total orders, well orders, and lattices. Closure operations.

- 2007-11-14
NumberTheory: the DivisionAlgorithm and ModularArithmetic. Readings: §3.5.

- 2007-11-16
More NumberTheory: Euclid's GCD algorithm and division in ℤ

_{m}. RSA_encryption. Readings: §3.6.- 2007-11-26
More NumberTheory: The Fundamental Theorem of Arithmetic; Euler's theorem and totients. Readings: §3.7.

- 2007-11-28
AlgebraicStructures: rings, fields, groups, semigroups, etc. Readings: Appendix A-1 (for field axioms); AlgebraicStructures.

- 2007-11-30
More AlgebraicStructures: subalgebras, homomorphisms, products, congruences and quotients (i.e. subsets, functions, products, equivalence relations, and quotients that respect the algebra operations).

- 2007-12-03
Start of GraphTheory: basic definitions; some standard graphs; graph homomorphisms. Readings: §§9.1—9.3.

- 2007-12-05
More GraphTheory: paths, cycles, connectivity, and trees. Readings: §9.4, §10.1.

- 2007-12-07
AsymptoticNotation: definitions, basic tricks, applications to GeneratingFunctions. Readings: §3.2.

The **final exam** was given Thursday, December 20th, 2007, starting at 9:00 a.m., in AKW 200. It was a closed-book test covering all material discussed during the semester.

This year's exam final-2007.pdf and sample solutions final-2007-solutions.pdf.

Sample solutions from past years' exams: final-2004-solutions.pdf, final-2005-solutions.pdf. Final exams without solutions: final-2004.pdf, final-2005.pdf.