[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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.


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

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.


NumberTheory: The division algorithm and ModularArithmetic. Readings: §3.4.


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


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


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


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.

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.

2014-06-17 11:57