Discrete Mathematics: 2011-2012
OverviewIn order to be able to formulate what a computer system is supposed to do, or to prove that it does meet its specification, or to reason about its efficiency, one needs the precision of mathematical notation and techniques. For instance, to specify computational problems precisely one needs to abstract the detail and then use mathematical objects such as sets, functions, relations, orders, and sequences. To prove that a proposed solution does work as specified, one needs to apply the principles of mathematical logic, and to use proof techniques such as induction. And to reason about the efficiency of an algorithm, one often needs to count the size of complex mathematical objects. The Discrete Mathematics course aims to provide this mathematical background.
This is an introductory course on discrete mathematics. Students will learn:
- some fundamental mathematical concepts and terminology;
- how to use and analyse recursive definitions;
- how to count some different types of discrete structures;
- techniques for constructing mathematical proofs, illustrated by discrete mathematics examples.
The course is to be divided into eight topics, each topic with an associated proof technique or style. The weekly "extra topic" is to round out the material and will only be covered in lectures if time permits.
Week 1: Sets. Definition of sets, subsets, some standard set; union, intersection, relative complement, symmetric difference, complement, cartesian products, power sets; algebraic laws; cardinality of finite sets. Writing mathematical proofs, double inclusion proofs for set equality, proof by cases. Extra topic: bags.
Week 2: Functions. Intervals; functions, domain and codomain, partial functions, restriction; 1-1, onto, and bijective functions; composition and inverse. Proof of the contrapositive and proof by contradiction. Extra topic: binary operators.
Week 3: Counting. Counting laws of sum, subtract, product; permutations, factorial function, combinations, binomial coefficients; inclusion-exclusion principle, derangements; floor and ceiling functions. Proofs techniques for counting, with many examples. Extra topic: multinomial coefficients.
Week 4: Relations. Binary relations; properties of relations: reflexivity, irreflexivity, symmetry, antisymmetry, transitivity, seriality; equivalence relations, equivalence classes, and partitions; relational compositive, converse, and transitive closure; graphical representation of relations. Extra topic: counting relations.
Week 5: Sequences. Sequences and recurrence relations; sigma notation and partial sums of sequences; recurrence relations arising from counting problems, including derangements and partitions. Proof by induction. Extra topic: solving linear recurrence relations.
Week 6: Modular Arithmetic. Definition of modular arithmetic via an equivalence relation; properties of addition, multiplication, and exponentation (mod n); Euclid's algorithm, binary MOD and DIV functions, multiplicative inverses (mod p). The Pigeonhole Principle, illustrated by some pure number theoretic results. Extra topic: representing positive integers as sums of two squares.
Week 7: Asymptotic Notation. Big-O notation, tail behaviour of sequences, examples drawn from running times of common algorithms. Proofs of sentences of the form (exists x.forall y.P) with examples of asymptotic behaviour proofs including simplified Stirling's formula. Choosing the right inductive hypothesis for big-O proofs. Extra topic: solving recurrence relations of divide-and-conquer type, up to asymptotic order.
Week 8: Orders. Pre-orders, partial orders, and linear orders; chains; product and lexicographic order on cartesian products; upper and lower bounds, lub and glb. Proofs of sentences of the form (forall x.exists y.P), with examples from interesting orders. Extra topic: order isomorphisms.
SyllabusSets: union, intersection, difference, power set, algebraic laws. Functions: injectivity & surjectivity, composition & inverse. Relations, equivalence relations, and partitions; relational composition & converse, transitive closure; orders, least upper and greatest lower bounds. Combinatorial algebra: permutations, combinations, sums of finite sequences. Functions associated with combinatorial problems: ceiling, floor, factorial, combinatorial coefficients. The inclusion-exclusion principle. Recurrence relations arising from combinatorial problems. Modular arithmetic, Euclid's algorithm, and applications.
- A. D. Ker, Discrete Mathematics Lecture Notes, 2009.
Comprehensive, book-style, notes (not repackaged overheads). Available in weekly installments during lectures, and online at the end of the corresponding week.
- K. A. Ross and C. R. B. Wright, Discrete Mathematics (Fifth Edition), Prentice Hall, 2003
This book has much to commend it, including an enormous number of examples and exercises and a computer science oriented exposition. It is pitched at a somewhat easy level, suitable for supplementing the lecture notes. It is rather expensive (about £50) but there are many copies in Oxford libraries.
- A. Chetwynd and P. Diggle, Discrete Mathematics, Arnold, 1995.
Very basic, but easy to read. Only covers the first half of the course. Cheap.
- R. P. Grimaldi, Discrete And Combinatorial Mathematics (Fifth Edition), Addison Wesley, 2003.
Some of the book is rather advanced, but also covers the basics quite well. Has many good practice questions (some difficult). Earlier editions are equally useful.