MAS1003: Discrete Mathematics

Lectures: 10am Mondays, 9am Tuesdays, 12pm Wednesdays C95 for 12 weeks, starting Monday 4 October 1999.

Lecturer: Robin Chapman, room 811,

web page: http://www.maths.ex.ac.uk/˜ rjc/rjc.html ,
course web page: http://www.maths.ex.ac.uk/˜ rjc/courses/dm99/dm99.html .

Brief syllabus: Sets and counting: Sets. Operations on sets. Addition principle. Multiplication principle. Sieve principle. Permutations and combinations. Binomial coefficients and the binomial theorem. Recursion and recurrences: Recursive definitions. Recurrence relations with constant coefficients. Modular arithmetic: Simple congruences. Divisibility tests. Latin squares. Permutations: Arithmetic of permutations. Cycle notation. Order of permutations. The sign of a permutation. Counting permutations of given cycle structure. Graphs: Trees. Hamiltonian and Eulerian graphs. Planar graphs.

Recommended Book: Norman L. Biggs, Discrete Mathematics, (revised edition) Oxford University Press, 1989.

Course Work: Fortnightly example sheets, to be handed in to and discussed with course tutors.

Problem sheets: I grade difficulty on each exercise from 1 to 5. This is only a rough estimate of course, but I would interpret these ratings as follows:

1. Completely straightforward.

2. Straightforward.

3. A reasonable problem, may require combining more than one idea or method.

4. A challenge.

5. A REAL challenge.

The examination questions will be comparable to questions rated at 1, 2 or 3. As generalization, problem-solving and exploration are important mathematical skills, each problem sheet will contain problems that are somewhat different to examples done in lectures. Also a few problems will be “exploratory” or “open-ended” in nature: these will typically ask for some numerical investigation, leading to some data with a pattern to be described, or if possible explained.

Examination: There will be a 50-minute test at 9.05am on Tuesday 23rd November 1999, counting as 25% of the final assessment. The remaining 75% will be based on a three-hour examination to be sat during the break between semesters. This examination will comprise two parts: Section A will consist of short compulsory questions and count for 40% of the mark; Section B will consist of four longer questions of which you choose three for a total of 60% of the mark.