The University of Southampton
×
Electronics and Computer Science➞Undergraduate

COMP1215 Foundations of Comp Sci

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, probability and algebra.
  • 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 & Objectives

Aims

Knowledge and Understanding

Having successfully completed the module, you will be able to demonstrate knowledge and understanding of:

A1.  Principles of mathematical proof and sound logical reasoning

A2.  The interplay of syntax and semantics in mathematics, logic and computer science

A3.  The language of set theory and common operations on sets, including infinite sets.

A4.  Functions and relations as fundamental structures in computer science.

A5.  Logical systems and the concept of formal proof.

A6.  Basic counting techniques and their applications to common data structures.

A7.  Elementary ideas of probability theory and statistics.

A8.  Elementary concepts of linear algebra.

Intellectual Skills

Having successfully completed the module, you will be able to:

B1.  Use the language of logic and set theory in order to make precise formal statements.

B2.  Recognise, understand and construct rigorous mathematical proofs.

B3.  Critically analyse and solve counting problems on finite, discrete structures.

B4.  Apply operations on vectors and matrices and solve systems of linear equations.

B5.  Calculate probabilities of events and recognise probability distributions

B6.  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 & Teaching

Learning & teaching methods

ActivityDescriptionHours
Lecture36
Tutorial12

Assessment

Assessment methods

MethodHoursPercentage contribution
Homework assignments-25%
Exam2 hours75%

Referral Method: By examination

Share this module FacebookTwitterWeibo