$\newcommand{\nnn}{\mathbb N}$
$\newcommand{\zzz}{\mathbb Z}$
$\newcommand{\rrr}{\mathbb R}$
$\newcommand{\ccc}{\mathbb C}$
$\newcommand{\fff}{\mathbb F}$
$\newcommand{\eee}{\mathrm e}$
$\newcommand{\vf}{\varphi}$
$\DeclareMathOperator{\Div}{\mathrm Div}$
$\DeclareMathOperator{\lcm}{\mathrm lcm}$
$\DeclareMathOperator{\var}{\mathrm Var}$
$\DeclareMathOperator{\cov}{\mathrm Cov}$
$\DeclareMathOperator{\period}{\mathrm per}$
$\DeclareMathOperator{\rank}{\mathrm rk}$
$\DeclareMathOperator{\trace}{\mathrm Tr}$
$\DeclareMathOperator{\span}{\mathrm Span}$
$\DeclareMathOperator{\sgn}{\mathrm sgn}$
$\DeclareMathOperator{\inv}{\mathrm Inv}$
$\DeclareMathOperator{\diam}{\mathrm diam}$
CMSC 37110: Discrete Mathematics
Autumn 2016
This page is under construction. Refresh your browser
to find the latest material.
Instructor: László Babai
Pre-final review: Tuesday, Dec 6, 3:30-5:20, Ry-276
Final Exam:
Thursday, December 8, 10:30-12:30, Ry-251
Midterm: Tuesday, November 8
Class schedule
- Lectures: TuTh 12:00-13:20 Ry 251
- Problem session: Thu 16:30-17:30 Ry 276
TA office hours
- Hing Yin (Joseph) Tsang: Mo 17:00-18:00 Ry 162 "Theory lounge"
- Kai Li: Thu 10:30-11:30 Ry-162 "Theory lounge"
Grading: HW 40% Midterm 20%
Final exam 35%
Class participation 5%
Instructor's online
Linear Algebra text
Class notes by Jacob Burroughs
- Class 19, Thu Dec 1
Similar matrices. Matrix of a linear map. Change
of basis. Diagonalizability. Eigensubspaces.
Geometric and algebraic multiplicity of eigenvalues.
Norm, orthogonality in $\rrr^n$. Elements of
spectral graph theory. Rate of convergence
of random walk on a graph: spectral estimate.
- Class 18, Tue Nov 29
Finite Markov Chains. Stationary distribution.
Evolution of MCs.
Perron--Frobenius Theorem for non-negative matrices.
Transition digraph. Period. Irreducible and ergodic MC.
Convergence to stationary distribution.
- Class 17, Tue Nov 22
Determinant, trace. Complex numbers. Fields.
Basis, rank, dimension. Systems of linear equations.
Rank-nullity theorem. Nonsingular matrices.
Eigenvalues, characteristic polynomial.
Eigenbasis. Standard dot product, orthogonality,
orthonormal basis. Spectral Theorem: real symmetric
matrix has orthonormal eigenbasis.
- Class 16, Thu Nov 17
Abelian group. Vector space over $\rrr$. Polynomial, degree.
Matrix multiplication.
- Class 15, Tue Nov 15
Planarity, Kuratowski's Theorem. Linear independence,
eigenvectors, eigenvalues, subspaces, span.
WARNING: Notes NOT proofread by instructor.
Compare with online notes (Discrete Math LN and Lin Alg text).
- Class 14, Thu Nov 10
Plane multigraphs, duality. Permutations, determinants.
- Class 12, Thu Nov 3
Monotone subsequences, Inclusion--Exclusion,
planarity, multigraphs, Euler's formula
- Class 11, Tue Nov 1
Ramsey Theory, Erdös's probabilistic method,
planar graphs
- Class 10, Thu Oct 27
Variance, Chebyshev's Inequality, Law of Large Numbers.
Digraphs, strong components, cut, tournaments.
- Class 9, Tue Oct 25
Finite probability spaces - refresher. Indicator
variables. Independence of random variables.
Variance, covariance. The Erdös-- Rényi
model of random graphs.
- Class 8, Thu Oct 20
Finite probability spaces. Events, independence.
Random variables, expected value.
- Class 7, Tue Oct 18
Automorphisms. Platonic solids. Trees. Independence
number, chromatic number.
- Class 6, Thu Oct 13
Asymptotic notation: little-oh, big-Oh, big-Omega, big-Theta
notation. Graph Theory: adjacency, degree, subgraphs, cliques,
cycles, paths, bipartite graphs, connected components, trees,
complement, isomorphism.
- Class 5, Tue Oct 11
Fermat's little Theorem, infinitude of primes,
primes in arithmetic progressions. Asymptotic equality,
Prime Number Theorem stated, Stirling's formula stated.
Counting; binomial, multinomial theorem,
permutations with repeated entries
- Class 4, Thu Oct 6
Division vs. congruence,
linear congruence, simultaneous linear congruences,
Chinese Remainder Theorem, gcd of a set of integers,
$56 = 7\cdot 8$
- Class 3, Tue Oct 4
Subgroups of $\zzz$, existence of gcd, Bézout's lemma,
Euclid's algorithm, multiplicative inverse
- Class 2, Thu Sep 29
Equivalence relation, congruence mod $m$, gcd definition,
Fermat's little Theorem stated
- Class 1, Tue Sep 27
Divisibility, sumset. Understanding the empty set.
Mathematical formalism, quantifiers.
Nuts and bolts of proofs:
assumptions, desired conclusion, translation of assumptions
and desired conclusion into terminology on a lower level
of abstraction using the definitions.
Additionally, please consult the pages of previous courses.