Computational Mathematics

This module runs in alternate years: 2012-13, 2014-15 and so on.

Prerequisites: Calculus 1: Single Variable; Algebra 1: Techniques & Applications; Discrete Mathematics (or equivalent)

BUEM010S6 (30 credits)

Aims

This module introduces the mathematics of computation, and involves the implementation and analysis of both exact and numerical algorithms. Ideas introduced in earlier modules will be developed in greater depth, giving a deeper and more thorough understanding of the topics covered, and illustrating the inter-relationships between different branches of mathematics.

Teaching and Assessment

Teaching for this module will take place throughout the year, with eight evenings of lectures in each of the Autumn and Spring Terms and two evenings of revision and consolidation in the Summer Term.

Of the final course mark, 80% is based on a three-hour exam in the summer term and the other 20% is from assessed coursework.

Coursework  will consist of short, problem based assignments. You will have around three weeks to complete each one.

The examination in the summer term will consist of 8 short (5 mark) questions, which are compulsory, and 4 long (20 mark) questions from which candidates must answer two.

Syllabus

Sorting
Algorithms for sorting a list: exchange sort, insert sort, merge sort, quick sort, heap sort; divide and conquer algorithms, rooted trees, binary trees, sifting procedures.

Asymptotic behaviour of functions
Comparing the growth rates of two functions, Big O notation, partial orders on a set of functions based on their growth rate, the maximum rule, the relationship between the growth rate of two functions f and g and the limit of f(n)/g(n) as n tends to infinity, other asymptotic concepts: Omega and Theta notation.

Time complexity of an algorithm
Analysis of an algorithm through counting significant operations, analysis of sorting algorithms, analysis of algorithms from linear algebra and graph theory, worse case and average case time complexity.

Computational Complexity
Comparison of polynomial and exponential growth; P, NP and NP-complete problems; examples of problems that are in P, examples of problems that are in NP but not known to be in P, examples of NP-complete problems; the SAT problem.

Errors
Sources of error: rounding errors, truncation errors, underflow and overflow; representing approximations of a real number and fixed point arithmetic, ill-condition problems.

Systems of linear equations
Gauss elimination and its computational time complexity; errors arising due to rounding; LU decomposition and iterative refinement; matrix and vector norms and error estimation; tests for determining ill conditioned equations; the Jacobi and the Gauss-Seidel iterations and conditions for their convergence.

Nonlinear equations
Methods for finding the approximate root of a nonlinear equation: bisection, fixed point iteration, Newton-Raphson; tests for the convergence of these methods and the speed of convergence, the order of a process; roots of polynomials and the Horner scheme.

Polynomial interpolation and quadrature
Approximating a function by a polynomial, Lagrange polynomials, divided differences, forward differences, numerical integration: the rectangular rule, the trapezium rule, Newton-Cotes Formulas, composite rules, error estimation.

Learning Outcomes

Subject Specific

• Knowledge and understanding of, and the ability to use, mathematical and/or statistical techniques.
• Knowledge and understanding of a range of results in mathematics.
• Appreciation of the need for proof in mathematics, and the ability to follow and construct mathematical arguments.
• Appreciation of the power of generalization and abstraction in the development of mathematical theories.
• Knowledge and understanding of the processes and limitations of mathematical approximation and computational mathematics.
• A deeper knowledge of some particular areas of mathematics.
• Appreciation of the historical and cultural aspects of mathematics.

Intellectual

• Ability to comprehend conceptual and abstract material.
• Develop a logical and systematic approach to problem solving.

Practical

• Problem-solving skills, including the ability to assess problems logically and to approach them analytically.
• Highly developed quantitative skills.
• Ability to transfer knowledge and expertise from one context to another.

Personal and Social

• Ability to learn independently using a variety of media.
• Ability to work independently with patience and persistence.
• Time-management and organizational skills.
• Good communication skills, including the ability to write coherently.
• Ability to complete a sustained and substantial task.
• Ability to complete work in a limited time period.