Department of Computer Science

## 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. Academic Year 2021/22 20 Blackboard quizzes, formal exam. Dr Paul Watton, Dr Mike Stannett & Dr Mark Stevenson 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. By the end of this course the students should be able to: apply different mathematical concepts and techniques in analysing and understanding important areas of computing; appreciate how mathematical techniques contribute to the study of computing; construct suitable models of computing systems and structures, and validate and analyse them. develop logical arguments and understand their relevance in contexts involving computing; 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 Lectures and problems classes. Feedback on tutorial exercises, assignments and during lectures. Notes and supporting material will be provided. Some other recommended books include: F.Moller & G. Struth, Modelling Computing Systems: Mathematics for Computer Science: The Mathematics of Computer Science (Springer, Undergraduate Topics in Computer Science) J. Gersting, Mathematical Structures for Computer Science. M. Piff, Discrete Mathematics, (Cambridge University Press) 1991. D. I. A. Cohen, Introduction to Computer Theory, (Wiley) 1991. G James, Modern Engineering Mathematics, 2nd Edition. (Addison-Wesley), 1996. JH McColl, Probability, (Edward Arnold), 1995