• CS202
• 2007
• Schedule

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.