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.

- 2010-09-02
WhatYouShouldKnowAboutMath. WhyYouShouldKnowAboutMath. Start of MathematicalLogic: basic principles and propositional logic. Boolean operators, truth tables, tautologies and logical equivalence. Readings: §§1.1–1.2.

- 2010-09-07
More MathematicalLogic: predicate logic. Variables, predicates, quantifiers, function symbols, equality. Models and inference rules for predicate logic. Nested quantifiers at the playground and the sad tale of ∃x ∀y ¬likes(y,x). Readings: §§1.3–1.4.

- 2010-09-09
Still more MathematicalLogic. How axioms shape models. Inference rules and proof strategies. Defining and proving basic facts about the natural numbers. Readings: §§1.5–1.7.

- 2010-09-14
SetTheory: sets, membership, operations on sets. Too much axiomatic set theory and not enough naive set theory. Readings: §§2.1–2.2.

- 2010-09-16
More SetTheory: relations, Functions, and sequences. Injections, surjections, bijections, and the true meaning of counting. Readings: §2.3.

- 2010-09-21
- Cardinal arithmetic and infinite sets. Readings: §2.4, specifically pp. 158–160.
- 2010-09-23
Sequences and SummationNotation. Readings: Earlier parts of §2.4.

- 2010-09-28
Start of Relations: relations and directed graphs, equivalence relations, partial orders, total orders. Readings: §§8.1, 8.3, 8.5–8.6.

- 2010-09-30
More Relations (especially partial orders): operations on posets, lexicographic order, maximum/maximal/minimal/minimum elements, various types of closures, topological sorting, lattices. Readings: §8.4, more of §8.6.

- 2010-10-05
NumberTheory: The division algorithm and ModularArithmetic. Readings: §3.4.

- 2010-10-07
More NumberTheory and applications: divisibility, the Euclidean algorithm, GCDs, and inverses mod m. Readings: §3.5–3.7.

- 2010-10-12
Still more NumberTheory: Further applications of the extended Euclidean algorithm, unique factorization, Euler's theorem, the ChineseRemainderTheorem, and RSA encryption.

- 2010-10-14
Start of LinearAlgebra: matrices, matrix operations, and Gauss-Jordan elimination. Readings: §3.8.

- 2010-10-19
More LinearAlgebra: matrix identities.

- 2010-10-21
The

**midterm exam**was given Thursday, 2010-10-21, at the usual class time and location. It was a closed-book, cumulative exam covering all material discussed in lecture prior to the test date.Sample solutions: 2010-midterm-solutions.pdf. Exam without solutions: 2010-midterm.pdf.

Sample solutions from past years' exams: 2008-midterm-solutions.pdf, 2007-midterm-solutions.pdf, 2005-midterm-solutions.pdf. Midterm exams without solutions: 2008-midterm.pdf, 2007-midterm.pdf, 2005-midterm.pdf.

- 2010-10-26
More LinearAlgebra: vectors and geometry. Subspaces and bases.

- 2010-10-28
End of LinearAlgebra: linear transformations and matrices. Rank. Projections.

- 2010-11-02
HowToCount: basic counting principles. The Pigeonhole Principle. Permutations and combinations. Readings: §§5.1–5.3.

- 2010-11-04
More HowToCount: BinomialCoefficients and the binomial theorem. Negative binomial coefficients. Ramsey numbers and Paul Erdős's destroy-the-aliens story as an extreme version of the usual somebody-walks-up-to-you-and-asks-you-for-the-value-of-something story (you do not need to know about this). Readings: §5.4.

- 2010-11-09
More BinomialCoefficients tricks. Inclusion-exclusion. Getting into trouble with GeneratingFunctions (basically §§1–4 and the corresponding parts of §10 in the notes): i.e., how to convert a counting problem into a generating function. Getting out of trouble (converting a generating function back into a sequence in the general case) we did not cover much. Readings: §7.4.

- 2010-11-11
Start of ProbabilityTheory: Probability spaces, events, independence, conditional probability. Readings: §§6.1–6.2.

- 2010-11-16
RandomVariables: Definition of a random variable. Expectations. Readings: §6.4.

- 2010-11-18
More RandomVariables. Joint distributions, independence, conditional expectations, and Markov's inequality. (Everything up through §3 in the notes.)

- 2010-11-30
GraphTheory. Readings: §§9.1–9.2.

- 2010-12-02
FiniteFields and applications. Readings: See notes.

- 2010-12-14
The

**final exam**was given Tuesday, 2010-12-14, starting at 2:00pm, in Rosenfeld GR109 (same room as lecture). It was a closed-book test covering all material discussed during the semester.Solutions: final-2010-solutions.pdf.

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