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.
WhatYouShouldKnowAboutMath. WhyYouShouldKnowAboutMath. Start of MathematicalLogic: basic principles and propositional logic. Boolean operators, truth tables, tautologies and logical equivalence. Readings: §§1.1–1.2.
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.
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.
SetTheory: sets, membership, operations on sets. Too much axiomatic set theory and not enough naive set theory. Readings: §§2.1–2.2.
- Cardinal arithmetic and infinite sets. Readings: §2.4, specifically pp. 158–160.
Sequences and SummationNotation. Readings: Earlier parts of §2.4.
Start of Relations: relations and directed graphs, equivalence relations, partial orders, total orders. Readings: §§8.1, 8.3, 8.5–8.6.
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.
More NumberTheory and applications: divisibility, the Euclidean algorithm, GCDs, and inverses mod m. Readings: §3.5–3.7.
Start of LinearAlgebra: matrices, matrix operations, and Gauss-Jordan elimination. Readings: §3.8.
More LinearAlgebra: matrix identities.
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 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.
More LinearAlgebra: vectors and geometry. Subspaces and bases.
End of LinearAlgebra: linear transformations and matrices. Rank. Projections.
HowToCount: basic counting principles. The Pigeonhole Principle. Permutations and combinations. Readings: §§5.1–5.3.
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.
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.
Start of ProbabilityTheory: Probability spaces, events, independence, conditional probability. Readings: §§6.1–6.2.
RandomVariables: Definition of a random variable. Expectations. Readings: §6.4.
More RandomVariables. Joint distributions, independence, conditional expectations, and Markov's inequality. (Everything up through §3 in the notes.)
GraphTheory. Readings: §§9.1–9.2.
FiniteFields and applications. Readings: See notes.
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.
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.