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

Sept-Dec 2014 Wan, Yeo