Registry

Module Specifications

Archived Version 2009 - 2010

Module Title	Computing for Mathematics
Module Code	CA167
School	School of Computing
Online Module Resources
Module Co-ordinator	Dr David Gray	Office Number	L2.54
Level	1	Credit Rating	15
Pre-requisite	None
Co-requisite	None

Module Aims

The module aims to develop in students the skills and experience to design, code, and test moderate-sized programs in C++, especially mathematically oriented programs.

Learning Outcomes

· An understanding of algorithms and their realisation as computer programs.· An understanding of the structure of high-level programming languages in general, and C++ in detail.· The ability to analyse moderate-sized computational problems, implement solutions, and test and de-bug them. · Appreciate the importance of, and be able to apply, good software engineering practices, including encapsulation and program structure.· Understand computer arithmetic, and be able to manage its limitations when implementing simple numerical algorithms in C++.

Indicative Time Allowances
	Hours
Lectures	72
Tutorials	24
Laboratories	48
Seminars	0
Independent Learning Time	81

Total	225
Placements
Assignments

NOTE

Assume that a 15 credit module load represents approximately 225 hours' work, which includes all teaching, in-course assignments, laboratory work or other specialised training and an estimated private learning time associated with the module.

Indicative Syllabus

Fundamental notions: The idea of an algorithm; programming languages; computers; compilation. The design-code-test cycle; programming style. Machine limitations; word size; reals; computation time; reliability. Using program development environments. Program testing.Types and type constructors : Integers, booleans, characters, floating point, strings, arrays, structures. Constants and expressions in each of these types; operator precedence; elementary algebra of booleans. Elementary use of pointers. Type conversion.Statements: Variables; declarations and scope; assignment statement, statement sequencing; if-then statements, loop constructs. Elementary reasoning about loops: induction; termination; loop invariants. Using loops with arrays. Standard input/output. Functions: Role of functions; definition and invocation; parameters and arguments; return values. Recursion; reasoning about recursion; termination. Void return type. Floating point. Floating-point format; floating addition/subtraction, multiplication, division; overflow and underflow; round-off error, accuracy, minimising round-off error, determining accuracy, precision and speed.Basic algorithms: Linear and binary search; elementary sorting and quicksort. Elementary arithmetic algorithms, e.g. prime generation, factorisation; binomial coefficients; base conversion. Elementary numerical algorithms: e.g. series summation; root finding (bisection method, Newton-Raphson); numeric integration; solution of linear systems; basic vector and matrix operations. Random number generation; applications. Elementary string algorithms, e.g. finding tokens. Algorithm design: Introduction to elementary algorithm design techniques, e.g. divide-and-conquer, recursion, backtracking; examples. Designing for efficiency. Algorithm complexity: Computational complexity; analysing the complexity of elementary algorithms. Big-O notation. Files: Binary vs. text files. Sequential and random access. Index files. Simple visualisation of data.Classes: The idea of classes. Class definition; objects; constructors & destructors; initialisation. Member functions; using "this"; static members; access control. Overloading. Programming with classes: Encapsulation; information hiding; structuring larger programs. Nested classes; object arrays. Encapsulating mathematical structures, e.g. complex numbers, sets. Templates; elementary use of the standard library; e.g. set, multiset, vector, map. Bottom-up vs. top-down design.