COM1002 Foundations of Computer Science
Summary |
The course consists of (around) 10 blocks of 2-3 weeks
work each. Each block develops mathematical concepts and
techniques that are of foundational importance to computing.
Lectures and problem classes will be used. The intention is
to enthuse about these topics, to demonstrate why they are
important to us, to lay the foundations of their knowledge
and prepare students for future computing courses. It is not
expected that the course will cover ALL of the maths that is
needed later, either in terms of depth or scope. |
Session |
Academic Year 2024/25 |
Credits |
20 |
Assessment |
Blackboard quiz, formal exams.
|
Lecturer(s) |
Dr Maksim Zhukovskii, Dr Robert Loftin, Dr Mark Stevenson & Dr Xu Xu |
Resources |
|
Aims |
The aims of this module are to:
- introduce the fundamental mathematical concepts needed
in the computer science degree.
- enhance the students' confidence in mathematics.
- stimulate the students' interest in mathematics for
computing.
|
Learning Outcomes |
By the end of this course the students should be able to:
- Demonstrate how mathematical techniques can contribute to the analysis of problems within computer science;
- Apply techniques from mathematical logic and set theory to appropriate problems related to computer science;
- Apply a range of relevant mathematical techniques from fields such as number theory, linear algebra and probability theory to problems relevant to computer science.
|
Content |
Semester 1
- Introduction: The role of mathematics in
modelling computing systems
- Propositional logic: Syntax and
semantics, truth tables, translation of natural language
sentences
- Sets: Basic definitions and operations on
sets, Russell's paradox
- Boolean algebras and circuits: Axioms and
proofs, relationship with sets and propositional logics,
modelling hardware systems
- Predicate logic: Syntax and semantics,
predicates and quantifiers, translation of natural
language sentences
- Proof strategies: How to use natural
deduction to prove mathematical theorems
- Functions and Relations: Basic
definition, operations on functions and relations,
cardinality, Cantor's diagonal argument
- Induction and Recursion: induction
principles, definition and examples of recursive
functions, proofs by induction
Semester 2
- The Integers: Factors and Primes,
Division, Euclid's Algorithm, Linear Diophantine
Equations
- Modular Arithmetic: Integers Modulo n,
Solving Equations, Chinese Remainder Theorem, Fermat's
Little Theorem, RSA Cryptography
- Matrices and Systems of Linear Equations:
Elementary Row Operations, General Solutions, Reduced
Echelon Form, Vectors and Linear Transformations
- Matrix Algebra: Matrix Multiplication,
Inverses, Determinants Eigenvalues and Eigenvectors,
Diagonalisation
- Probability: Counting Elements of Sets,
Permutations and Combinations, Probability Space,
Conditional Probability
- Variables and Processes: Random
Variables, Difference Equations, Markov Processes,
PageRank
|
Teaching Method |
Lectures and problems classes. |
Feedback |
Feedback on tutorial exercises, assignments and during lectures. |
|