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.
- 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.
|Sept-Dec 2014||Wan, Yeo|