Department of Computer Science

Mathematics for Computer Science (MCS) 2009/0

Workload - Private Study - Assessment - Description - Learning Outcomes - Content - Teaching Materials - Recommended Books

Module Prerequisites

Prerequisite knowledge

Knowledge of A-level Mathematics is assumed.

Workload

• Lectures: 28 x 1hr
• Problem Classes: 14 x 1hr
• Practicals: 4 x 1hr
• Private Study: 131hrs
• Assessment: 3hrs

Working through exercises is an essential part of understanding the material.

Private Study

Lecture notes and problem sheets will be provided. For the first part of the course, the material will closely follow 'Engineering Mathematics' by Stroud, which is an essential text for the course and contains notes and exercises. Additional exercises and material on the second part of the course may be found in Cohen and Linz.

Assessment

Closed Assessments

• , 3.00 hours
• , hours

The exam is in two parts, each worth 50 marks. Candidates must answer two questions (out of three) from each part.

Formative Feedback

Problem sheets will be issued each week and handed in for the next week. The answers will be discussed in small groups with a demonstrator, during each week's problem class. Each group will have an half hour session.

Description

This course covers a variety of mathematical methods and techniques which today's well equipped Computer Scientists will have in their armouries. As such it forms a prerequisite for many of the courses to follow.

Learning Outcomes

On completion of this module, students will be able to:

• know how to use a range of mathematical skills, which are required for the study and practice of computer science;
• understand the mathematical basis of a variety of numerical algorithms and tools;
• appreciate that there is a hierarchy of grammars and that these grammars can be used to measure the power of a range of finite state automata.
• recognise more complex induction proofs, and proofs by construction.
• recognise the significance of these results to certain classes of algorithms particularly concerned with lexical and syntactic analysis.
• understand some elementary decidability results.

Content

Part 1

Continuous Mathematics and Probability. Series; Maclaurin, Taylor, common function series. Complex numbers; arithmetic, polar and exponential forms. Vectors; scalar and vector product. Linear algebra; matrices, special matrices, determinant, inverse, eigenvalues, decomposition, rank, linear operators. Partial differentiation; small increments, rate-of-change, extrema of multivariate functions. Fitting data; models, least squares.Simultaneous linear equations; matrix representation, Gaussian elimination, approximate solution. Differential equations; formation and solution of differential equations. Statistics; central tendency, dispersion, variance, joint statistic. Probability; laws of probability, independence, distributions.

Part 2

Introduction to Formal Languages and Automata: Introduction to automata, languages and grammars. Regular expressions, regular languages, limitations. Deterministic and non-deterministic finite-state machines. Relationship to regular languages and regular grammars. Finite automata with output and their applications. Automata minimization. Decidable problems. Context-free grammars. Push down stack automata and their ability to accept context free grammars. Correspondence between types of grammars and automata: Chomsky's hierarchy.

Teaching Materials

Notes and copies of overheads available on the web for part 2 of the course. Problem sheets are available on the web, and sample solutions are distributed in the following problem class.

Recommended Books

Last updated: 26^th May 2011