Skip to navigation | Skip to main content | Skip to footer
Menu
Menu

COMP10020: Mathematical Techniques for Computer Science (2008-2009)

This is an archived syllabus from 2008-2009

Mathematical Techniques for Computer Science
Level: 1
Credit rating: 20
Pre-requisites: No Pre-requisites
Co-requisites: No Co-requisites
Duration: 22 weeks through first and second semester
Lectures: 44 in total, 2 per week
Examples classes: 22 in total, 1 per week (assessed)
Labs: none
Lecturers: Graham Gough
Course lecturers: Graham Gough

Andrea Schalk

Additional staff: view all staff
Timetable
SemesterEventLocationDayTimeGroup
Sem 1 w1-5,7-12 Lecture 1.1 Fri 10:00 - 11:00 -
Sem 1 w1-5,7-12 Lecture UNI PL B Mon 10:00 - 11:00 -
Sem 1 w3-5,7-12 Examples LF15 Tue 11:00 - 12:00 C,X
Sem 1 w3-5,7-12 Examples LF15 Fri 12:00 - 13:00 D,Y
Sem 1 w3-5,7-12 Examples LF15 Tue 14:00 - 15:00 A,Z
Sem 1 w3-5,7-12 Examples LF15 Mon 16:00 - 17:00 W
Sem 2 w19-26,30-33 Lecture 1.1 Wed 11:00 - 12:00 -
Sem 2 w19-26,30-33 Lecture 1.1 Tue 13:00 - 14:00 -
Sem 2 w20-26,30-33 Examples IT407 Mon 12:00 - 13:00 W
Sem 2 w20-26,30-33 Examples LF15 Fri 14:00 - 15:00 A+Z
Sem 2 w20-26,30-33 Examples IT407 Mon 15:00 - 16:00 C+X
Sem 2 w20-26,30-33 Examples IT407 Mon 16:00 - 17:00 D+Y
Assessment Breakdown
Exam: 77%
Coursework: 15%
Lab: 0%
Degrees for which this unit is core
  • Artificial Intelligence BSc (Hons)

Aims

This full-year course unit focuses on the use of mathematics as a tool to model and analyse real-world problems arising in computer science. Four principal topics, drawn from the traditional areas of discrete mathematics as well as some continuous mathematics, will be introduced: symbolic logic, probability, discrete structures, and vectors and matrices. Each topic will be motivated by experts introducing relevant real-world problems arising in their own specialism.

Abstraction is fundamental to computer science. Hence, a fundamental emphasis of this course unit is to introduce mathematical techniques and skills to enable the student to design and manipulate tractable and innovative abstract models of chunks of the real-world. These techniques and skills include appropriate mathematical notations and concepts. These range over the four principal areas mentioned above. Formalisation in mathematics has, in general, significant cost. Therefore, to be of practical use, the benefits arising from formalisation, such as succinctness, unambiguity, provability, transformability and mechanisability, must outweigh the costs. A key aim of the course is for the student to appreciate this issue and know how and when to use particular techniques.

The specific aims of the course unit are:

To demonstrate the relevance of mathematics to computer science.
To introduce fundamental mathematical techniques of abstraction.
To demonstrate applicability of particular mathematical techniques and skills for particular types of computer science problem.
To appreciate the costs and benefits of mathematical modelling.

The delivery style will place more emphasis on students undertaking appropriate background reading, i.e. being more independent learners, and use the lectures more to demonstrate examples and solutions and not working through every detail of a particular or concept.

The course unit is delivered by staff from both the School of Computer Science and the School of Mathematics .

Learning Outcomes

On successful completion of the course unit, the student should:

Be familiar with the idea of a discrete structure, and the notions of formal language and parse tree.
Have an understanding of the basic ideas of sets and functions, including boolean combination of sets, and be able to manipulate such expressions.
Have an understanding of the standard propositional logic connectives and be able to convert logical expressions into conjunctive and disjunctive normal form.
Have an understanding of the universal and existential quantifiers.
Be able to formulate natural language logical statements as formal sentences of 1st order logic.
Be familiar with the general concept of binary relation, equivalence and order relations and methods of combining relations; be familiar with the standard graphical representations of relations.
Be familiar with the principle of mathematical induction and be able to perform proofs using this principle, also be aware of simple examples of structural induction on lists.
Have a good appreciation of the basic laws of probability.
Have the skills to tackle simple problems on discrete probability distributions, conditional probability and independence.
Have an understanding of vectors and matrices and their associated operations.
Be able to use vectors and matrices to solve simple geometrical problems.
Have an understanding of the role of vectors and matrices in graphics-based computation.

Assessment of Learning outcomes

All learning outcomes are assessed by examples class assessment, mid-semester test and examinations (January and May/June).

Contribution to Programme Learning Outcomes

A1, B1

Syllabus

Semester 1


Motivational Guest Lecture --- for the whole course


Why mathematics is important for real-world computer scientists.

Introduction to Discrete Structures - 4 lectures


Standard number systems and arithmetical operations on them; introduction to syntax. A brief introduction to sets and set theoretic operations.

Logic - 7 lectures


About propositions, truth and falsity, logical connectives and their meaning (via truth tables); propositional formulas --- the logical language, truth table semantics.

Validity, contingency, unsatisfiability; logical equivalences (laws);

Simple logical manipulation and reasoning, normal forms, satisfiability algorithms;

Predicates and individuals, universal and existential quantifiers, first order logic in use;

Probability - 8 lectures


Random experiments. Finite or countable discrete sample spaces. Events, disjoint events. Algebra of events. Definition of probability of an event when outcomes are equally likely. General definition of probability of an event. Axioms of probability. Addition Rule of two events

Conditional probability. The product rule. The total probability of two events. Definition of a partition of a sample space (exhaustive events). The total probability rule for a partition set. Bayes Theorem. Independent events and the product rule for independent events.

Definition of a random variable. Discrete random variables and their distributions. The probability mass function and the cumulative distribution function for a discrete random variable. The Binomial and Poisson distributions.

Semester 2


Discrete Structures - 9 lectures


Sets, functions and maps, use in specification, mathematical induction.

Binary relations, domain and range, properties of relations, relational composition, closure properties, equivalence relations, partitions.

Graphs and networks, directed/undirected, acyclic/cyclic, paths, networks in action, structural induction.

Motivational Guest Lecture


The importance of vectors and matrices in graphics.

Vectors and Matrices - 12 lectures


Vectors:

Reminder of 2-D and 3-D coordinate systems and right-angle trig; Vectors (Equality, Parallel, Addition / Subtraction, Multiplication by a scalar); Vectors in a cartesian system; Scalar and Vector Products; Vector Equations of lines and planes.

Matrices:

Concept, Equality, Addition, Subtraction and Multiplication by a scalar; Matrix Multiplication; Associative Law; Multiplication of matrix times vector; Matrices and systems of equations.

Geometrical Transformations:

Homogeneous Coordinates; Affine Transformations; The transformation matrix; Translation, Rotation, Reflection, Scaling, Shear; Transformations and inverse transformations; Combined Transformations and the Associative Law.

Reading List

Title: Discrete mathematics for Computer Scientists (2nd edition)
Author: Truss, J.K.
ISBN: 0201360616
Publisher: Addison-Wesley
Edition: 2nd
Year: 1999
This book covers the course unit topics of discrete structures and logic but also contains additional material some of which is covered in latercourse units.


Title: Applied statistics and probability for engineers (5th edition)
Author: Montgomery, D. and Runger
ISBN: 9780470505786
Publisher: Wiley
Edition: 5th
Year: 2010
This book provides excellent coverage of probability.


Title: Mathematical techniques: an introduction for the engineering, physical, and mathematical sciences (4th edition)
Author: Jordan, D.W. and P. Smith
ISBN: 9780199282012
Publisher: Oxford University Press
Edition: 4th
Year: 2008
This will provide excellent coverage of probability and is a introduction for the engineering, physical and mathematical sciences.


Title: Interactive computer graphics: a top-down approach with WebGL (7th edition)
Author: Angel, Edward and Dave Shreiner
ISBN: 9781292019345
Publisher: Pearson
Edition: 7th
Year: 2015
This book contains a chapter dealing with geometrical transformations and is used for a second year course unit.