This course is designed to show some of the interdependence of mathematics and computing, and is designed for students in both computer science and mathematics.

Topics to be covered include:

Foundations - Relations on sets, including equivalence, partial order relations and relational databases; properties of functions, permutations, arithmetic of integers modulo n.

Grammars and Automata - Phrase structure grammars, finite state automata, and the connections between the language accepted by an automaton, regular sets and regular grammars.

Graph Theory - Hamiltonian circuits, vertex colouring and the chromatic polynomial of a graph, planar graphs, applications including the travelling salesperson problem and scheduling problems.

Game Theory - Games of strategy as an application of graph theory, matrix games and solution of matrix games.

On satisfying the requirements of this course, students will have the knowledge and skills to:

Assessment will be based on:

• Learning Portfolio (10%; LO1-7)
• Assignments (3) (30%; LO 1-7)
• Mid-semester test (15%; LO1-5)
• Final examination (45%; LO1-5)

36 lectures and ten tutorials

MATH1005 or MATH1013 or MATH1115.

with MATH2001, MATH2006, MATH2063.