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. Through creative problem-solving, students gain hands-on experiece in approaching mathematical questions, developing concepts, formalizing ideas, turning intuition into rigorous proof.
These phases of mathematical thinking are illustrated on a variety of accessible and useful topics. Students practice the quantifier notation both as a mathematical shorthand and as one of the organizing principles of formal statements.
Basic counting is a recurring theme and provides a source for sequences, another recurring theme, which in turn feeds into the study of asymptotic behavior (rates of growth). Further topics to be covered include proof by induction; the elements of number theory (gcd, congruences, the Chinese Remainder Theorem, Fermat's little Theorem); recurrences, Fibonacci numbers, generating functions; the elements of graph theory; finite probability spaces, random variables, expected value and variance, independence, concentration inequalities, random graphs; basic linear algebra, including determinants, rank, eigenvalues, the Spectral Theorem; finite Markov chains, ergodicity, eigenvalue gap vs. rapid mixing.
Instructors: Laszlo BabaiQuarter offered: Autumn
Last Verified by Sharon Salveter on 26 January, 2010.