Aims

1. To introduce the notation, terminology, and techniques underpinning the discipline of Theoretical Computer Science.
2. To provide the mathematical foundation necessary for understanding datatypes as they arise in Computer Science and for understanding computation.
3. To introduce the basic proof techniques which are used for reasoning about data and computation.
4. To introduce the basic mathematical tools needed for specifying requirements and programs, and for analysing algorithms.

Syllabus

1. Number systems and proof techniques: natural numbers, integers, rationals, real numbers, prime numbers, proof by contradiction and proof by induction.
2. Approaches to describing collections of objects: sets and set operations, unary and binary relations, properties of binary relations, partial orders and equivalence relations, inverse relations, and compositions of relations.
3. Functions: properties of functions, inverse functions and compositions of functions, the pigeonhole principle.
4. Propositional logic: syntax and construction of formulas, semantics, interpretations and truth tables, tautologies, contradictions, semantic consequence and logical equivalence
5. Combinatorics: notation for sums, products, and factorials, Binomial coefficients, counting permutations, subsets, subsequences and functions.
6. Discrete Probability: sample spaces, events, conditional probability, independence, random variables and expectation.
7. Growth rates of functions: polynomial versus exponential.

Recommended Texts

To be advised

Learning Outcomes

At the end of this module students should be able to:

1. reason about simple data types using basic proof techniques;
2. interpret set theory notation, perform operations on sets, and reason about sets;
3. understand, manipulate and reason about unary relations, binary relations, and functions;
4. represent statements in propositional logic, and to recognise, understand, and reason about formulas in propositional logic;
5. apply basic counting and enumeration methods as these arise in analysing permutations and combinations;
6. perform simple calculation about discrete probablility.

Learning Strategy

Formal Lectures: Students will be expected to attend three hours of formal lectures in a typical week. Formal lectures will be used to introduce students to the concepts and methods covered by the module.

Tutorials: Supporting tutorials are held each week in which students work under staff guidance on problem sets designed to reinforce understanding of the lecture material with the possibility of immediate feedback.

Private study: In a typical week students will be expected to devote 6 hours of unsupervised time to private study; private study will provide time for reflection and consideration of lecture material and background reading and completion of the assessment tasks

Assessment: Two continuous assessment tasks, each consisting of a piece of written work and a class test on that written work, will be used to test to what extent practical skills have been learnt. A final examination at the end of the module will assess the academic achievement of students.