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:
- Use the language of logic and set theory in order to make precise formal statements
- 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
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
- The language of set theory and common operations on sets, including infinite sets
- Logical systems and the concept of formal proof
- The interplay of syntax and semantics in mathematics, logic and computer science
- Elementary ideas of probability theory
- Basic counting techniques and their applications to common data structures
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 |
|---|---|
| Lecture | 36 |
| Revision | 18 |
| Wider reading or practice | 50 |
| Completion of assessment task | 10 |
| Preparation for scheduled sessions | 6 |
| Tutorial | 12 |
| Follow-up work | 18 |
| 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 |
|---|---|
| Problem Sheets | 10% |
| Written exam | 90% |
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% |