SCQF Level: 10
Availability: Autumn, Advanced module
Course Prerequisite: MAT9K4
Credit Value: 20 (1 module)
To provide techniques for the solution of problems concerning task assignment, scheduling, networks, searching and counting; and to establish algorithms where appropriate.
Students should be able to select and implement counting techniques, find systems of distinct representatives of appropriate sets, employ graph-theoretical arguments, and apply criteria for the traversability of networks.
1. Introduction - Methods of counting, selections, binomial coefficients.
2. Pairing problems - Matchings, distinct representatives, optimal assignment algorithm.
3. Recurrence relations - Growth rates, counting problems, generating functions.
4. Inclusion-exclusion principle - Derangements, rook polynomials, forbidden permutations.
5. Graphs - Paths and cycles, matrices, vertex degrees, trees, graph-colouring and timetabling, planarity.
6. Properties of networks - Traversability, connectivity, Menger's Theorem.
Problem solving, logical skills.
I. ANDERSON, A first course in combinatorial mathematics, 2nd edn. OUP, 1989.
R.J. WILSON and J. J. WATKINS, Graphs - an introductory approach, Wiley, 1990 or
R.J. WILSON, Introduction to Graph Theory, 4th Edn., Prentice Hall, 1996.
3 one-hour lectures and a 1 hour tutorial per week.
1/3 coursework (2 class tests) and 2/3 examination.