41.520 Discrete Mathematics

This course will bring the students up to speed with some of the classical topics in discrete mathematics. It will also introduce a number of new developments which involve computer algebra. Basic knowledge of standard first year mathematical courses and elementary probability will be assumed.Topics include: Logic, sets and proofs.  Examples:  propositional equivalences, predicates and quantifiers, set operations, proof by induction and contradiction, cardinality of infinite sets, construction of the reals. Functions, relations and algorithms. Example: growth of functions, big-O notation, complexity of algorithms, asymptotics. Integers and algorithms. Examples:  fundamental theorem of arithmetic, greatest common divisors, Euclidean algorithm, Chinese remainder theorem, public key cryptography, RSA encryption, factorization, primality checking, Diophantine equations, number sieves. Recursive algorithms and generation functions. Examples: recurrence relations, Fibonacci numbers, tower of Hanoi, coin change problem, divide-and-conquer, inclusion-exclusion, derangement. Advanced counting. Examples: pigeonhole principle, permutations/combinations with repetition, generating permutations and combinations, combinatorial proofs. Graphs.  Examples:  directed/undirected graphs and their representations, isomorphisms, connectivity, Euler and Hamilton paths, shortest path problem, planarity, graph colouring. Modelling computation.  Examples:  languages and grammars, finite-state machines and automata, language recognition, regular sets and grammars, Turing machines, program correctness. Creative telescoping (unified approach to binomial sums). Examples: the algorithms of Celine, Gosper, and Zeilberger, hypergeometric function. Integer relations (recognizing a number as a closed form). Examples: PSLQ algorithm, BBP formula. 12 Credits Faculty: Sept-Dec 2014 Wan , Yeo