Workload - Private Study - Assessment - Description - Aims - Learning Outcomes - Content - Teaching Materials - Recommended Books

Module Code | COM00005C |
---|---|

Lecturers | Colin Runciman, Mark Bartlett |

Taken By | CS 1, CS/Math 1, CS/Phil 1, CSESE 1, CSYS 1, MEng CS 1, MEng CS/Phil 1, MEng CSAI 1, MEng CSESE 1, MEng CSYS 1, MMath 1 |

Number of Credits | 20 |

Teaching | Autumn 2-9, Spring 2-10, Summer 1-4 |

Closed Assessments | [50%] Closed Exam Spring 1, 1.50 hours |

[50%] Closed Exam Summer 5-7, 1.50 hours | |

Reassessment |
[100%]
Closed Exam - August Resit Week, 1.50 hours |

Basic knowledge of algebra and arithmetic is assumed.

- Lectures: 24 x 1hr
- Problem Classes: 24 x 1hr
- Practicals: 6 x 1hr
- Private Study: 143hrs
- Assessment: 3hrs

In the Autumn Term, there are six two-hour problem classes. In the spring and summer terms, practicals comprise problem classes and software labs.

Expect to spend a couple of hours each week reviewing your lecture notes and studying textbooks. Another two or three hours may be needed to complete solutions to problem sheets on which work has been started in practicals. Working through exercises is an essential part of understanding the material. Some private-study time has also been allowed for revision.

- Closed Exam Spring 1, 1.50 hours
- Closed Exam Summer 5-7, 1.50 hours

The two separate 90-minute exams, one at the start of the Spring Term and the other in the Summer Term, are of equal weight.

Unassessed tests

- Autumn week 5, 0.5 hour
- Autumn week 9, 0.5 hour
- Spring week 6, 0.5 hour
- Spring week 10, 0.5 hour
- Summer week 4, 0.5 hour

After each exam, summary feedback is provided for the whole class. Students also have supervised access to their marked exam scripts.

This module lays the foundations in discrete mathematics commonly required in many areas of computer science. It reinforces the concept of mathematical proof, including constructive proof by giving an algorithm.

The aims of this module are to:

- Lay the foundations in discrete mathematics commonly required in many areas of computer science
- Reinforce the concept of mathematical proof, including constructive proof by giving an algorithm

On completion of this module, students will be able to:

* read, understand and apply definitions and theorems in basic discrete mathematics;

* formulate simple definitions, examples and proofs in discrete mathematics;

* understand the concepts of formal languages, automata and grammars, and the relation between them;

* understand in more detail (1) regular languages and finite automata, (2) context-free languages and pushdown automata.

Part 1

Propositional logic; logical arguments; predicate logic. Proof methods including case analysis, algebraic calculation, induction. Set theory. Relations and their properties; representation as pair-sets, directed graphs, boolean matrices. Special classes of relations and their properties: functions, orderings and equivalences; composition, closures.

Part 2

Introduction to formal languages, automata, and grammars. Regular expressions, regular languages, limitations. Deterministic and non-deterministic finite-state machines. Relationship to regular languages and regular grammars. Automata minimization. Decidable problems. Context-free grammars. Pushdown automata and their ability to accept context-free languages. Correspondence between types of grammars and automata: Chomsky's hierarchy.

Copies of lecture slides are provided (either in hard copy, or on the module website) as a convenient starting point when students are making their own notes during lectures. Problem sheets and example solutions are available on the module website.

Rating | Author | Title | Publisher | Year |
---|---|---|---|---|

** | Dean N. | The Essence of Discrete Mathematics | Prentice Hall | 1997 |

** | Haggarty R. | Discrete Mathematics for Computing | Addison Wesley | 2002 |

** | Truss J. | Discrete Mathematics for Computer Scientists | Addison Wesley | 1999 |

** | Cohen D.I.A. | An Introduction to Computer Theory (2nd ed.) | Wiley | 1997 |

** | Linz P. | An Introduction to Formal Languages and Automata (4th ed.) | Jones and Bartless | 2006 |

* | Rodger S.H. and Finley T.W. | JFLAP: An Interactive Formal Language and Automata Package | Jones and Bartless | 2006 |

* | Solow D. | How to Read and Do Proofs | Wiley | 2005 |

Last updated: 19^{th} September 2016