WhyYouShouldKnowAboutMath. WhatYouShouldKnowAboutMath. Basics of mathematical reasoning and PropositionalLogic. Readings: Sections 1.1-1.4, 3.1-3.5.

More logic: PredicateLogic, InferenceRules and ProofTechniques. Readings: Sections 1.4-1.6, 3.6.

SetTheory. Readings: Chapter 2.

The NaturalNumbers (including the PeanoAxioms). Start of InductionProofs. Readings: Sections 4.1-4.3.

More InductionProofs. SummationNotation. Readings: Sections 4.4 and 4.6.

RelationsAndFunctions. Readings: Chapter 5.

Recursive definitions and StructuralInduction. SolvingRecurrences. Readings: Section 4.5, 4.8.

The PigeonholePrinciple and HowToCount. Readings: Sections 6.1-6.4.

More HowToCount: counting two ways; counting functions, words, selections, and permutations. Readings: Sections 10.1, 10.2, 10.4-10.6.

BinomialCoefficients and applications. Readings: Sections 11.1-11.4.

Start of GeneratingFunctions: basic idea, finding generating functions for aⁿ and n^k, extracting sums of coefficients, extracting individual coefficients, solving recurrences, and simplification using partial fraction expansions. Readings: Sections 25.4, 25.1 and 25.2.

More GeneratingFunctions: counting combinatorial objects with generating functions. The generating function for the Catalan_numbers, which blew up in class because of an error (see notes for the correct version).

ProbabilityTheory basics: axioms for probability spaces. Uniform discrete probability spaces.

More ProbabilityTheory: Computing probabilities in uniform discrete spaces. Random subsets and random permutations. Independence. RandomVariables.

RandomVariables. Expectation of a random variable. Calculating expectations. Markov's inequality. Variance.

Operations on RandomVariables: expectation of a product, variance of a sum. Chebyshev's inequality.

Last of ProbabilityTheory and RandomVariables: conditional probabilities and expectations.

Relations, particularly equivalence relations and their use in constructing the integers and rationals. Readings: §7.2-7.4. See also §18.1 for directed graphs, a way to represent a relation that we will see more of later.

CS202/Assignments/MidtermExam. In class.

More Relations: orders. BiggsBook skimps on orders, so you'll have to look at the notes.

GraphTheory: (undirected) graphs, isomorphism, degree, paths, and cycles. Readings: §15.1-15.4.

More GraphTheory: paths and cycles, connected components, trees, proving things about graphs. Readings: §15.4-15.5.

BipartiteGraphs and matchings. Readings: Sections 17.1, 17.4, and 17.5. Click on the date for notes on the error in lecture.

Start of NumberTheory. Divisibility, the DivisionAlgorithm, Euclid's GCD algorithm, prime factorizations. Readings: Chapter 8.

More NumberTheory: The Fundamental Theorem of Arithmetic, ModularArithmetic. Readings: §8.6, 13.1-13.3.

More ModularArithmetic: The ChineseRemainderTheorem, Euler's Theorem, and applications. Readings: Euler's Theorem appears in §13.3 of BiggsBook. The ChineseRemainderTheorem does not appear explicitly in the main text of BiggsBook, but does appear in Exercises 9 and 10 in §13.6, and in disguised form as Theorem 20.6 about cyclic groups.

Start of GroupTheory: definition, examples, arithmetic in groups. Readings: §20.1-20.3. For more on magmas, monoids, and semigroups see AlgebraicStructures.

The SymmetricGroup: properties of permutations, cycle decompositions, operations on permutations. Also more GroupTheory: subgroups, homomorphisms, isomorphims, and embeddings. Readings: §10.6, 20.7, 20.5. Note that BiggsBook doesn't talk about group homomorphisms that aren't isomorphisms, so you may also want to read through the appropriate sections of GroupTheory.

More on the SymmetricGroup: embedding arbitrary finite groups, permutation types, odd and even permutations. Readings: §21.5, 12.5, 12.6.

Still more GroupTheory: Lagrange's Theorem on the size of subgroups. Cosets, normal subgroups and quotient groups. Readings: §20.8.

Subgroups and homomorphisms. Kernels and the First Isomorphism Theorem. Generalization to algebras. Readings: GroupTheory.

AlgebraicStructures with two binary operations: rings and fields. Readings: §22.1–22.3.

Polynomials. Readings: §22.4-22.8.

More Polynomials. Construction of FiniteFields. Readings: §23.1–23.4.

LinearAlgebra: vector space basics. Readings: notes.

More LinearAlgebra: linear transformations, matrices, and subspaces.

Still more LinearAlgebra. Computing inverses of matrices and solving matrix equations. Orthogonality, projection, and least-squares solutions.

AsymptoticNotation and algorithm analysis. Readings: §14.5-14.6.