# Advanced options in Computer Science

In the fourth year, students spend 62% of their time on advanced options.

The list of options varies from year to year according to the research interests of teaching staff, but the following examples illustrate courses that have been offered recently.

### Graph Representation Learning

Machine learning studies automatic methods for identifying patterns in complex data and for making accurate predictions based on past observations. In this course, we develop rigorous mathematical foundations of machine learning, in order to provide guarantees about the behaviour of learning algorithms and also to understand the inherent difficulty of learning problems.

The course will begin by providing a statistical and computational toolkit, such as generalisation guarantees, fundamental algorithms, and methods to analyse learning algorithms. We will cover questions such as when can we generalise well from limited amounts of data, how can we develop algorithms that are computationally efficient, and understand statistical and computational trade-offs in learning algorithms. We will also discuss new models designed to address relevant practical questions of the day, such as learning with limited memory, communication, privacy, and labelled and unlabelled data. In addition to core concepts from machine learning, we will make connections to principal ideas from information theory, game theory and optimisation.

### Advanced Security

The Advanced Security course is designed to bring students towards the research boundaries in computer security, covering contemporary topics in depth. It is split into two modules:

- Bootstrapping Security. Modern technology brings many opportunities for connecting devices together by means such as wifi, Bluetooth or connection to the internet. In many cases we want to make these connections secure: authenticating the identity of the device connected to, making them secret and carrying out (e.g. financial) transactions using them. In this module we examine the theory and practice of doing this using both conventional means (using a pre-existing security structure) and methods based on things such as co-location and human judgement.
- Information Hiding. Steganography is the art and science of hiding a secret payload inside an innocent cover, typically hiding inside digital media such as images, movies, or mp3 audio. The course covers the definitions, practice, and theory of hidden information in way accessible to newcomers. We will cover the details of getting inside digital images in order to hide information, the different sorts of embedding operations commonly used, and how hidden information can be detected. Some linear algebra allows for more efficient hiding. Finally, we see some mathematical theory which explains how the amount of hidden data grows with the space in which is can be hidden.

### Concurrent Algorithms and Data Structures

This is an advanced course on concurrent programming. The course will combine principles and practice. Principles to be studied include correctness conditions for concurrent datatypes, and the relative power of different synchronization operations. More practical topics will include how to implement concurrency primitives - such as locks and monitors - and concurrent datatypes - such as linked lists, queues, and hash tables.

This course is largely independent of the second year Concurrent Programming course, although there are clearly strong links between the two. Concurrent Programming is based upon the message-passing paradigm; much of the emphasis is on using concurrency as a way of structuring large programs. This course will be based upon low-level concurrency primitives, such as compare-and-swap; the emphasis will be on speed. MSc students could take this course in Michaelmas, followed by Concurrent Programming in Hilary.

### Database Systems Implementation

This course examines the data structures and algorithms underlying database management systems such as Oracle or PostgreSQL. It covers techniques from both research literature and commercial systems. At the end of this course, students should have a good insight into how DBMSs function internally, and understand how to analyse the performance of data-intensive systems. They will become familiar with a variety of programming techniques for large-scale data manipulation, and be able to apply the insights achieved to build the major components of a mini-DBMS.

### Probabilistic Model Checking

Probabilistic model checking is a formal technique for analysing systems that exhibit random behaviour. Examples include randomised algorithms, communication and security protocols, computer networks, biological signalling pathways, and many others. The course provides a detailed introduction to these techniques, covering both the underlying theory (Markov chains, Markov decision processes, temporal logics) and its practical application (using the state-of-the art probabilistic checking tool PRISM, based here in Oxford). The methods used will be illustrated through a variety of real-life case studies, e.g. the Bluetooth/FireWire protocols and algorithms for contract signing and power management.

### Probability and Computing

Probabilistic techniques have numerous Computer Science applications, including combinatorial optimisation, computational geometry, data structures, networks, and machine learning. Randomised algorithms, which typically guarantee a correct result only with high probability, are often simpler and faster than corresponding deterministic algorithms. Randomisation can also be used to break symmetry and achieve load balancing in parallel and distributed computing. This course introduces students to those ideas in probability theory that most are most relevant to Computer Science. This background theory is motivated and illustrated by a wide-ranging series of computer-science applications.