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.

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.