Module overview
Aims and Objectives
Learning Outcomes
Knowledge and Understanding
Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:
- Basic counting techniques and their applications to common data structures
- The language of set theory and common operations on sets, including infinite sets
- Elementary ideas of probability theory
- The interplay of syntax and semantics in mathematics, logic and computer science
- Principles of mathematical proof and sound logical reasoning
- Logical systems and the concept of formal proof
- Functions and relations as fundamental structures in computer science
Subject Specific Intellectual and Research Skills
Having successfully completed this module you will be able to:
- 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
- Calculate probabilities of events and recognise discrete probability distributions
- Recognise, understand and construct rigorous mathematical proofs
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 |
Preparation for scheduled sessions | 6 |
Lecture | 36 |
Tutorial | 12 |
Completion of assessment task | 10 |
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% |