Module overview
This module aims to:
- Introduce the logical and mathematical foundations of computer science.
- Illustrate the use of formal languages in computer science, including in algorithms and programming.
- Extend students' mathematical sophistication and skills.
- Present basic concepts and techniques of combinatorics, statistics and probability.
- Give mathematical background necessary for other compulsory modules.
- Develop the study skills necessary for students to learn new concepts of mathematics and programming (including those we do not cover in the degree).
- Instill a range of useful problem solving skills.
Aims and Objectives
Learning Outcomes
Subject Specific Intellectual and Research Skills
Having successfully completed this module you will be able to:
- Calculate probabilities of events and recognise discrete probability distributions
- Recognise, understand and construct rigorous mathematical proofs
- Critically analyse and solve counting problems on finite, discrete structures
- Use the language of logic and set theory in order to make precise formal statements
Knowledge and Understanding
Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:
- Functions and relations as fundamental structures in computer science
- Principles of mathematical proof and sound logical reasoning
- Logical systems and the concept of formal proof
- The language of set theory and common operations on sets, including infinite sets
- The interplay of syntax and semantics in mathematics, logic and computer science
- Basic counting techniques and their applications to common data structures
- Elementary ideas of probability theory
Syllabus
Mathematical proof
- Proof by case analysis, proof by contradiction.
- Induction and recursion.
- Universal properties.
Sets, functions and relations
- Basic notation, representations and examples. Membership and subsets.
- Operations on sets: union, sum, intersection and complement.
- Pairs, tuples, cartesian products, powersets.
- Relations, equivalence relations and partial orders.
- Functions: injections, surjections, bijections.
- Cardinality, infinite sets.
Logic
- Propositional logic. Logical connectives.
- Syntax and semantics.
- Natural deduction, soundness and completeness.
- Quantifiers and predicate logic.
Combinatorics
- Basic principles of counting: product and sum rules, inclusion-exclusion principle, pigeonhole principle.
- Combinations, permutations and arrangements, binomial theorem.
Introduction to trees and graphs: directed, undirected and weighted.
Introduction to probability
- Elementary probability formulae, discrete probability distributions
Learning and Teaching
Teaching and learning methods
The content of this module is delivered through lectures, the module website, directed reading, pre-recorded materials and tutorials.
Students work on their understanding through a combination of independent study, preparation for timetabled activities, tutorials, and problem classes, along with formative assessments in the form of problem sheets.
| Type | Hours |
|---|---|
| Revision | 18 |
| Wider reading or practice | 50 |
| Completion of assessment task | 10 |
| Lecture | 36 |
| Follow-up work | 18 |
| Tutorial | 12 |
| Preparation for scheduled sessions | 6 |
| Total study time | 150 |
Assessment
Assessment strategy
This module is assessed by a combination of problem sheets and a final assessment in the form of a written examination.Summative
This is how we’ll formally assess what you have learned in this module.
| Method | Percentage contribution |
|---|---|
| Written exam | 90% |
| Problem Sheets | 10% |
Referral
This is how we’ll assess you if you don’t meet the criteria to pass this module.
| Method | Percentage contribution |
|---|---|
| Written exam | 100% |
Repeat
An internal repeat is where you take all of your modules again, including any you passed. An external repeat is where you only re-take the modules you failed.
| Method | Percentage contribution |
|---|---|
| Written exam | 100% |