CMSC 37110
Discrete MathematicsPrerequisites: Consent of instructor
Catalog Description: This course emphasizes mathematical discovery and rigorous proof, illustrated on a variety of accessible and useful topics, including basic number theory, asymptotic growth of sequences, combinatorics and graph theory, discrete probability, finite Markov Chains. The course includes an introduction to linear algebra.
Long Description: This course is an introduction to mathematical thinking.
The course emphasizes mathematical discovery and rigorous proof, illustrated on a refreshing variety of accessible and useful topics. Basic counting is a recurring theme and provides the most important source for sequences, another recurring theme, which in turn feeds into the study of asymptotic behavior (limits, asymptotic notation, rates of growth). Further topics to be covered include the quantifier notation; proof by induction; recurrences, Fibonacci numbers, generating functions; graph theory, connectivity, chromatic number, planar graphs, Ramsey's Theorem, trees, directed graphs; number theory, g.c.d., prime property, congruences, Fermat's little theorem, the Chinese Remainder Theorem, the Prime Number Theorem (stated); counting, binomial coefficients, Inclusion-Exclusion; finite probability spaces, random variables, expected value and variance, independence, concentration inequalities; random graphs, nonconstructive proof of existence; linear algebra, determinant, rank, linear transformations, eigenvalues, Euclidean spaces, Gram-Schmidt orthogonalization, the Spectral Theorem; finite Markov chains, ergodicity, eigenvalue gap vs. rapid mixing.
Creative problem solving is central to the course. The text is augmented by substantial web-based material. Past assignments and tests are available on the web.
Instructors: Laszlo BabaiQuarter offered: Autumn
Last Verified by Sharon Salveter on 23 June, 2009.