The University of Southampton
Courses

# COMP1215 Foundations of Computer Science

## 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:

• Principles of mathematical proof and sound logical reasoning
• The interplay of syntax and semantics in mathematics, logic and computer science
• The language of set theory and common operations on sets, including infinite sets
• Functions and relations as fundamental structures in computer science
• Logical systems and the concept of formal proof
• Basic counting techniques and their applications to common data structures
• Elementary ideas of probability theory and statistics
• Elementary concepts of linear algebra
##### 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
• Recognise, understand and construct rigorous mathematical proofs
• Critically analyse and solve counting problems on finite, discrete structures
• Apply operations on vectors and matrices and solve systems of linear equations
• Calculate probabilities of events and recognise probability distributions
• Use statistical analysis, including sampling, hypothesis testing and regression

### 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. - Probability and statistics - Introduction to probability: elementary probability formulae, discrete and continuous probability distributions. - Introduction to statistics: sampling, confidence intervals, hypothesis testing, regression. Algebra - Linear and quadratic equations, systems of equations. - Polynomials: basic properties and operations. - Vectors: basic properties, scalar product, vector product. - Matrix algebra: basic properties, inverse, determinant, Eigenvalues, Eigenvectors, - Solving systems of linear equations.

### Learning and Teaching

TypeHours
Revision10
Tutorial24
Lecture36
Follow-up work18
Preparation for scheduled sessions18
Total study time162

compiled by Pawel Sobocinski. Foundations of Computer Science.

### Assessment

#### Summative

MethodPercentage contribution
Assignment 25%
Exam  (2 hours) 75%

#### Repeat

MethodPercentage contribution
Exam 100%

#### Referral

MethodPercentage contribution
Exam 100%

#### Repeat Information

Repeat type: Internal & External