CMSC 17400
Discrete MathematicsPrerequisites: Placement into MATH 15100 or equivalent, or consent of departmental counselor.
Catalog Description: This is a directed course in mathematical topics and techniques needed by students taking Algorithms (CMSC 27000). It is also a prerequisite to several other courses, including Honors Combinatorics and Probability (CMSC 27400).
The course emphasizes mathematical discovery and rigorous proof, which are 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. Further topics to be covered include proof by induction; recurrences, Fibonacci numbers, generating functions; graph theory, trees, directed graphs; number theory, congruences, Fermat's little theorem, the Chinese Remainder Theorem, the Prime Number Theorem; counting, binomial coefficients, Inclusion-Exclusion; combinatorial probability; random variables, expected value and variance, independence; random graphs; finite Markov chains; limits of sequences, asymptotic equality, rates of growth.
Instructors: L.BabaiQuarter offered: This course is no longer offered. See CMSC 27100 for current version.
Last Verified by Sharon Salveter on 19 January, 2010.