The descriptions are for modules currently being taught. They should be viewed as an example of the modules we provide. All modules are subject to change for later academic years.

Mathematical Foundations of Computer Science (MFCS) 2015/6

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

Module Prerequisites

Prerequisite knowledge

Basic knowledge of algebra and arithmetic is assumed.

Workload

  • 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.

Private Study

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.

Assessment

Closed Assessments

  • 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.

Formative Feedback

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
Tests and practicals are not only an important part of the learning process; they provide an opportunity for feedback. Problem sheets are issued for each practical, to be completed in advance of the following practical. Lecturers and graduate demonstrators offer feedback on students' solutions. Model solutions are provided for comparison.

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

Description

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.

Aims

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

Learning Outcomes

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.

Content

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.

Teaching Materials

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.

Recommended Books

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
Back to top

Last updated: 19th September 2016