# Mathematics and Computer Science core 2

**In their second year, students in the Mathematics and Computer Science degree study two core Computer Science papers; Models of Computation, and Algorithms; and two core Mathematics courses comprising Linear Algebra and Metric Spaces and Complex Analysis.
**

Students also study two optional Computer Science courses. It is recommended that you take 32 lectures' worth of Mathematics options.

In addition to this list, further Computer Science options can be found here.

## Contents |

## Computer Science core

### Algorithms

**This will be core from 2017/18.**

More information on this course will follow.

### Models of Computation

On this course you will gain a basic understanding of the classical mathematical models used to analyse computing processes, including finite automata, grammars, and Turing machines. These mathematical models can be used to answer questions such as what problems can be solved by computer, and whether there some problems that are intrinsically harder to solve than others.

## Computer Science Options

### Computer Architecture

This course follows on from * Digital
Systems* by showing you how hardware components can be used to
design processors that achieve high performance. Central to the
course is the design of pipelined architectures that execute multiple
instructions simultaneously, detecting and resolving interactions
between instructions dynamically. The course covers the design of
instruction sets and different styles of processor implementation,
followed by a brief survey of parallel machines that achieve still
higher performance.

### Computer Graphics

This is an introductory course in Computer Graphics, and covers a wide range of the field of interactive computer graphics at all levels of abstraction, and with emphasis on both theory and practise. It follows a standard textbook in the field, with additional material used to keep the course up-to-date. You will cover a range of basic graphics techniques, from the generation of graphics on raster output devices to the types of hardware used to display three-dimensional objects. It will be of benefit to anybody who uses computer graphics to display objects or data.

### Computer Networks

In this course you will examine networked computer communications, including the underlying physical media, the representation of data, and the protocols that are used to achieve reliable, error-free transmission, and routing of data in large networks. You will also examine some actual network applications in detail.

### Concurrency

Computer networks, multiprocessors and parallel algorithms, though radically different, all provide examples of processes acting in parallel to achieve some goal. All benefit from the efficiency of concurrency yet require careful design to ensure that they function correctly. The concurrency course introduces the fundamental concepts of concurrency using the notation of Communicating Sequential Processes. By introducing communication, parallelism, deadlock, live-lock, etc., it shows how CSP represents, and can be used to reason about, concurrent systems. Students are taught how to design interactive processes and how to modularise them using synchronisation. One important feature of the module is its use of both algebraic laws and semantic models to reason about reactive and concurrent designs. Another is its use of FDR to animate designs and verify that they meet their specifications.

### Databases

Databases are at the heart of modern commercial application development. Their use extends beyond this to many applications and environments where large amounts of data must be stored for efficient update and retrieval. Their principles and fundamental techniques are being extended today to the Web and to novel kinds of data, like XML. The purpose of this course is to provide you with an introduction to the principles of database systems. You will begin by studying database design, covering the entity relationship model, and will then cover the relational data model, relational algebra and SQL. As a newer model, XML and some XML query languages will be covered. You will take a deeper look at database query languages and their connection with logic and with complexity classes. In the second half, we will discuss some database implementation issues such as storage, indexes, query processing, and query optimization.

### Intelligent Systems

This is an introductory course into the field of artificial intelligence (AI), with particular focus on search as the fundamental technique for solving AI problems.

The problem of navigating a road map with a known layout is a typical example of a problem studied in this course. Problems such as this one can be solved by enumerating all possible sequences of moves until a solution is found. Such a naive idea, however, is rarely applicable in practice because the size of the search space is typically vast. This course will introduce basic AI search techniques, such as depth?first, breadth?first, and iterative deepening search, and it will discuss heuristic techniques such as A* search that improve efficiency by pruning the search space.

### Logic and Proof

Logic plays an important role in many disciplines, including Philosophy and Mathematics, but it is particularly central to Computer Science. This course emphasises the computational aspects of logic, including applications to databases, constraint solving, programming and automated verification, among many others. We also highlight algorithmic problems in logic, such as SAT-solving, model checking and automated theorem proving.

The course relates to a number of third-year and fourth-year options.Propositional and predicate logic are central to Complexity Theory, Knowledge Representation and Reasoning, and Theory of Data and Knowledge Bases. They are also used extensively in Computer-Aided Formal Verification, Probabilistic Model Checking and Software Verification.

## Mathematics core

### Complex Analysis

The theory of functions of a complex variable is a rewarding branch of mathematics to study at the undergraduate level with a good balance between general theory and examples. It occupies a central position in mathematics with links to analysis, algebra, number theory, potential theory, geometry, topology, and generates a number of powerful techniques (for example, evaluation of integrals) with applications in many aspects of both pure and applied mathematics, and other disciplines, particularly the physical sciences.

In these lectures we begin by introducing students to the language of topology before using it in the exposition of the theory of (holomorphic) functions of a complex variable. The central aim of the lectures is to present Cauchy's Theorem and its consequences, particularly series expansions of holomorphic functions, the calculus of residues and its applications.

The course concludes with an account of the conformal properties of holomorphic functions and applications to mapping regions.

### Linear Algebra

The core of linear algebra comprises the theory of linear equations in many variables, the theory of matrices and determinants, and the theory of vector spaces and linear maps. All these topics were introduced in the Prelims course. Here they are developed further to provide the tools for applications in geometry, modern mechanics and theoretical physics, probability and statistics, functional analysis and, of course, algebra and number theory. Our aim is to provide a thorough treatment of some classical theory that describes the behaviour of linear maps on a finite-dimensional vector space to itself, both in the purely algebraic setting and in the situation where the vector space carries a metric derived from an inner product.

### Metric Spaces

The theory of functions of a complex variable is a rewarding branch of mathematics to study at the undergraduate level with a good balance between general theory and examples. It occupies a central position in mathematics with links to analysis, algebra, number theory, potential theory, geometry, topology, and generates a number of powerful techniques (for example, evaluation of integrals) with applications in many aspects of both pure and applied mathematics, and other disciplines, particularly the physical sciences.

In these lectures we begin by introducing students to the language of topology before using it in the exposition of the theory of (holomorphic) functions of a complex variable. The central aim of the lectures is to present Cauchy's Theorem and its consequences, particularly series expansions of holomorphic functions, the calculus of residues and its applications.

The course concludes with an account of the conformal properties of holomorphic functions and applications to mapping regions.

## Mathematics options

### Fluids and Waves

This course introduces students to the mathematical theory of inviscid fluids. The theory provides insight into physical phenomena such as flight, vortex motion, and water waves. The course also explains important concepts such as conservation laws and dispersive waves and, thus, serves as an introduction to the mathematical modelling of continuous media.

### Integration

The course will exhibit Lebesgue's theory of integration in which integrals can be assigned to a huge range of functions on the real line, thereby greatly extending the notion of integration presented in Mods. The theory will be developed in such a way that it can be easily extended to a wider framework, but measures other than Lebesgue's will only be lightly touched.

Operations such as passing limits, infinite sums, or derivatives, through integral signs, or reversing the order of double integrals, are often taken for granted in courses in applied mathematics. Actually, they can occasionally fail. Fortunately, there are powerful convergence and other theorems allowing such operations to be justified under conditions which are widely applicable. The course will display these theorems and a wide range of their applications.

This is a course in rigorous applications. Its principal aim is to develop understanding of the statements of the theorems and how to apply them carefully. Knowledge of technical proofs concerning the construction of Lebesgue measure will not be an essential part of the course, and only outlines will be presented in the lectures.

### Numerical Analysis

Scientific computing pervades our lives: modern buildings and structures are designed using it, medical images are reconstructed for doctors using it, the cars and planes we travel on are designed with it, the pricing of "Instruments" in the financial market is done using it, tomorrow's weather is predicted with it. The derivation and study of the core, underpinning algorithms for this vast range of applications defines the subject of Numerical Analysis. This course gives an introduction to that subject.

Through studying the material of this course students should gain an understanding of numerical methods, their derivation, analysis and applicability. They should be able to solve certain mathematically posed problems using numerical algorithms. This course is designed to introduce numerical methods - i.e. techniques which lead to the (approximate) solution of mathematical problems which are usually implemented on computers. The course covers derivation of useful methods and analysis of their accuracy and applicability.

The course begins with a study of methods and errors associated with computation of functions which are described by data values (interpolation or data fitting). Following this we turn to numerical methods of linear algebra, which form the basis of a large part of computational mathematics, science, and engineering. Key ideas here include algorithms for linear equations, least squares, and eigenvalues built on LU and QR matrix factorizations. The course will also include the simple and computationally convenient approximation of curves: this includes the use of splines to provide a smooth representation of complicated curves, such as arise in computer aided design. Use of such representations leads to approximate methods of integration. Techniques for improving accuracy through extrapolation will also be described. The course requires elementary knowledge of functions and calculus and of linear algebra.

### Probability

The first half of the course takes further the probability theory that was developed in the first year. The aim is to build up a range of techniques that will be useful in dealing with mathematical models involving uncertainty. The second half of the course is concerned with Markov chains in discrete time and Poisson processes in one dimension, both with developing the relevant theory and giving examples of applications.

### Quantum Theory

Quantum theory was born out of the attempt to understand the interactions between radiation, described by Maxwell's theory of electromagnetism, and matter, described by Newton's mechanics.

Although there remain deep mathematical and physical questions at the frontiers of the subject, the resulting theory encompasses not just the mechanical but also the electrical and chemical properties of matter. Many of the key components of modern technology such as transistors and lasers were developed using quantum theory.

In quantum theory particles also have some wave-like properties. This introductory course explores some of the consequences of this culminating in a treatment of the hydrogen atom.

### Rings and Modules

The first abstract algebraic object which are normally studied are groups, which arise naturally from the study of symmetries. The focus of this course is on rings, which generalise the kind of algebraic structure possessed by the integers: a ring has two operations, addition and multiplication, which interact in the usual way. The course begins by studying the fundamental concepts of rings: what are maps between them, when are two rings isomorphic etc. much as was done for groups. As an application, we get a general procedure for building fields, generalising the way one constructs the complex numbers from the reals. We then begin to study the question of factorization in rings, and find a class of rings, known as Principal Ideal Domains, where any element can be written uniquely as a product of prime elements generalising the case of the integers. Finally, we study modules, which roughly means we study linear algebra over certain rings rather than fields. This turns out to have useful applications to ordinary linear algebra and to abelian groups.

### Statistics

Building on the first year course, this course develops statistics for mathematicians, emphasising both its underlying mathematical structure and its application to the logical interpretation of scientific data. Advances in theoretical statistics are generally driven by the need to analyse new and interesting data which come from all walks of life.

Part A Probability is recommended for this course, but is not essential. If you are not doing Part A Probability then you should make sure that you are familiar with Prelims work on Probability, and you may also need to familiarise yourself with a couple of lectures' worth of material from Part A Probability. Should you be interested in taking courses involving statistics in Parts B or C, then it would be strongly advisable to take Part A Probability.

### Topology

Topology is the study of `spatial' objects. Many key topological concepts were introduced in the Metric Spaces course, such as the open subsets of a metric space, and the continuity of a map between metric spaces. More advanced concepts such as connectedness and compactness were also defined and studied. Unlike in a metric space, there is no notion of distance between points in a topological space. Instead, one keeps track only of the open subsets, but this is enough to define continuity, connectedness and compactness. By dispensing with a metric, the fundamentals of proofs are often clarified and placed in a more general setting.

In the first part of the course, these topological concepts are introduced and studied. In the second part of the course, simplicial complexes are defined; these are spaces that are obtained by gluing together triangles and their higher-dimensional analogues in a suitable way. This is a very general construction: many spaces admit a homeomorphism to a simplicial complex, which is known as a triangulation of the space. At the end of the course, the proof of one of the earliest and most famous theorems in topology is sketched. This is the classification of compact triangulated surfaces.

### ASO

ASO is a collection of short courses covering various subjects. This takes the place of a Mathematics option, and can include, but is not limited to Group Theory, Modelling in Mathematical Biology, Calculus of Variations, Graph Theory, Integral Transforms, Introduction to Manifolds, Number Theory, Projetive Geometry, and Special Relativity.