Format: 3 lecture hours per week, 1 tutorial hour per week, 10 weeks.

Text: Course notes created by the instructor.

This is a junior-level course in modelling using discrete mathematical structures. There is also an emphasis on combinatorial algorithms.

Syllabus:

1. Some concepts of combinatorics and graph theory
   • Combinations, permutations, compositions, parititions
   • Networks, Hamiltionian paths and cycles
   • Matchings in graphs, graph colouring, the chromatic polynomial
   • Permanents, the assignment problem and systems of distinct representatives
2. Computer representation of combinatorial objects
   • Representation of integers, sets, combinatorial configurations, graphs and networks.
   • Generation of combinations, permutations, set partitions and other configurations
   • Gray codes, revolving door order
   • Steiner triple systems
3. Complexity of combinatorial computations
   • Computational efficiency, polynomial-bounded algorithms
   • Matchings in graphs, graph colouring, the chromatic polynomial
   • The Chinese postman prolbem
   • NP-complete problems and DNA computing
4. Shortest paths and flows in networks
   • Max-flow min-cut theorem
   • The Belman-Ford algorithm, Dijkstra's algorithm
   • The Floyd-Marshall method, minimal cost flow problems
5. Some other algorithms for graph theory
   • Hamiltionian path generation, the branch and bound method
   • The travelling salesman problem
   • Determination of connectivity, spanning trees