# Computer Laboratory

Course pages 2012–13

# Part III

Please check the official timetables for timetable details.

## Michaelmas term

• Advanced Computer Design (P34) – Dr Simon Moore – 16 h

The aim of this module is to provide an introduction to undertaking multithreaded multiprocessor computer architecture research using FPGAs as an emulation platform.

• Algebraic Path Problems, with applications to Internet Routing (L11) – Dr Timothy Griffin – 16 h

A great deal of interesting work was done in the 1970s in generalizing shortest path algorithms to a wide class of semirings - called “path algebras” or “dioids”. Although the evolution of Internet Routing protocols does not seem to have taken much inspiration from this work, recent “reverse engineering” efforts have demonstrated that an algebraic approach is very useful for both understanding existing protocols and for exploring the design space of future Internet routing protocols. This course is intended to present the basic mathematics needed to understand this approach. No previous background will be assumed. The course will start from scratch and end with open research problems. Many examples inspired by Internet Routing will be presented along the way.

• Automated Reasoning (L18) – Dr Mateja Jamnik – 16 h

Provides an introduction to how reasoning can be automated. In particular, the course will introduce students to fundamental techniques (logic, knowledge representation, proof, resolution, decision procedures, search, induction, etc.) for designing automated reasoners, provide some experience of how they work and how to use them, and present advanced uses and applications (ontologies, semantic web, diagrammatic reasoning, etc.) of theorem proving for solving problems via automated reasoning.

• Category Theory and Logic (L108) – Dr Samuel Staton – 16 h

We will investigate the connection between computer programs and mathematical proofs, via the language of category theory. For example, we will investigate the universal properties of types in functional programming, and the universal properties of connectives like AND and EXISTS in logic. By developing a theory of models for programs and proofs, we will be able to demonstrate why certain statements (like Peirce's law, ((P → Q) → P) → P) have no constructive proof.

• Chip Multiprocessors (R05) – Dr Robert Mullins – 16 h

Uni-processor designs can no longer be scaled to take full advantage of advances in fabrication technology. This has forced a shift to parallel architectures in an attempt to sustain performance growth. This module examines the motivation for such a shift in detail, and covers the research challenges facing industry and academia in attempting to exploit single-chip parallel architectures.

• Computer Security: Principles and Foundations (R209) – Prof Ross Anderson, Dr Frank Stajano, Dr Steven Murdoch, Dr Robert Watson – 16 h

NEW: This course aims to provide students with an introduction to the history and central themes of computer security, from its 1970s foundations to some current research topics, with a theme of how to defend cloud-based systems against capable motivated opponents. The course considers first local computer systems and then distributed systems; however, we will rapidly discover that this is an artificial distinction that only becomes more awkward as we enter the current period. Throughout the course, we will consider proposed systems along with the adversarial research intended to identify gaps and vulnerabilities.

• Image Processing and Image Coding (E4F8) – Dr Joan Lasenby – 16 h

Sophisticated processing of images by digital hardware is now fairly common, and ranges from special effects in video games to satellite image enhancement. Three of the main application areas are video data compression, image enhancement, and scene understanding. This module introduces the key tools for performing these tasks, and shows how these tools can be applied. This module is offered by the Department of Engineering.

• Innovative User Interfaces (R03) – Prof Peter Robinson – 16 h

Provides an overview of research in the area of innovative user interfaces including, amongst other topics, windows and icons; augmented reality; ubiquitous computing; and ambient displays.

• Introduction to Natural Language Processing (L100) – Prof Ann Copestake, Dr Stephen Clark – 16 h

This module aims to provide a brief introduction to linguistics for computer scientists and then goes on to cover some of the core tasks in natural language processing (NLP), with the emphasis on statistical techniques suitable for the extraction of meaning from large bodies of text. Finally we will consider some applications and evaluate how well they work given current techniques.

• Introductory Logic (R07) – Dr Bjarki Holm – 8 h

This module aims to provide the basic mathematical logic which will be assumed in later courses.

• Low Power Embedded Systems Programming (P31) – Dr Ian Wassell, Mr Brian Jones – 16 h

Teaches students how to write programs for low power embedded devices that communicate with other computers or devices to solve practical problems. The course will cover the relevant theoretical knowledge required for writing such applications, and the practical experience writing C programs for Atmel microprocessors. The module will also give students an appreciation for some of the research issues in low power embedded systems.

• Multicore Semantics and Programming (R204) – Dr Peter Sewell, Dr Timothy Harris – 16 h

In recent years multiprocessors have become ubiquitous, but building reliable concurrent systems with good performance remains very challenging. This module introduces some of the theory and the practice of concurrent programming, from hardware memory models and the design of high-level programming languages to the correctness and performance properties of concurrent algorithms.

• Network Architectures (R02) – Prof Jon Crowcroft – 16 h

The world needs more network architects! This module will discuss and critique historical and contemporary network architectures including ATM, TCP/IP and 3G, as well as cover emerging sensor networks and delay tolerant approaches.

• Programming for Mobiles (P36) – Dr Andrew Rice – 16 h

Developing applications for modern smart phones requires different considerations to writing for a conventional PC environment. This course will cover the relevant background knowledge required to effectively develop for modern smart phones, discuss the differences between current popular platforms and highlight some of the ongoing research questions. Practical experience will be provided implementing concepts from lectures in practical classes using the Android operating system.

• Research Skills (C00) – Prof Neil Dodgson – 16 h

Covers key research skills including: understanding the research process; how to read research papers; technical writing and technical presentation; and experiment design and statistical analysis of results. This module must be taken by all M.Phil students.

• Spoken Language Processing (L106) – Prof Phil Woodland, Dr Bill Byrne – 16 h

The aim of this module is to introduce the underlying statistical approaches and some of the major techniques used for spoken language processing. Core statistical models that are used in a wide-range of speech and language applications will be discussed along with their underlying theory. Examples of how these models may be applied to speech processing applications, such as speech recognition and speaker verification, will be described.

• Word Meaning and Discourse Understanding (L113) – Dr Simone Teufel – 16 h

Parsing a natural language sentence is only the start: one also needs knowledge about what each word means, how the meanings of words relate to each other, and how the sentence relates to other text pieces. This course looks at these phenomena and presents computational models for them, many of them recent research, with an emphasis on distributional models. The course is mostly lectures-based, with some exercises and discussions in class.

## Lent term

• Advanced Topics in Concurrency (L22) – Prof Glynn Winskel – 8 h

How can the ideas and methodology of denotational semantics and domain theory be extended and generalized to the richer world of interacting concurrent processes? Using ideas and techniques from semantics and category theory this half-module will guide the student to recent research in domain theory for concurrency.

• Biomedical Informatics (R211) – Dr Anna Korhonen, Dr Pietro Lio – 8 h

Biomedical informatics is a growing, interdisciplinary field that studies effective uses of biomedical data and information for scientific inquiry, problem solving, and decision making, motivated by efforts to improve human health. This course provides an introduction to biomedical informatics. It has a specific emphasis on computational techniques used in this field. A variety of data and text mining techniques are introduced and applied to study practical problems in biological sciences, clinical medicine and public health. The course provides also an overview of applications in the field.

• Building an Internet Router (P33) – Dr Andrew Moore – 16 h

This module requires the full design, implementation, testing and inter-operability of a complex hardware and software system.

• Categorical Models of Computational Languages (L24) – Prof Marcelo Fiore – 8 h

The course explores the mathematical structures used to model a wide range of computational languages. These will be considered from the following viewpoints: (i) type discipline; (ii) data structuring; (iii) calling mechanisms; (iv) programming primitives; (v) resource management; and (vi) operational semantics. Overall we will look at: (i) untyped and typed languages, and, amongst the latter, simple, polymorphic, and dependently typed; (ii) inductive and recursively defined datatypes; (iii) call-by-name, call-by-value, and mixed paradigms; (iv) computational effects and control operators; (v) linearity; and (vi) reduction vs interaction.

• Computer Security: Current Applications and Research (R210) – Prof Ross Anderson, Dr Steven Murdoch, Dr Robert Watson – 16 h

NEW: In the second security course in the ACS, we turn our attention to active research topics in computer security at the Computer Laboratory. One unifying theme is how to build secure systems at scale that contain more secure and less secure components. Building on the lessons from multilevel secure systems and security protocols discussed in the first course, we will explore infrastructure versus applications; services versus clients; the use of smartcards and other cryptographic processors; API security; and failure modes from covert channels to concurrency vulnerabilities.

• Data Centric Networking (R202) – Dr Eiko Yoneki – 16 h

This module provides an introduction to data centric networking, where data is a communication token in networking and its impact to the computer system's architecture. Integration of complex data processing with networking is a key vision for future computing. This course provides various aspects in data centric networking ranging from content-based routing, data-flow parallel computing (e.g. MapReduce), to a large graph structured data processing.

• Flows in Networks (L110) – Dr Richard Gibbens – 16 h

This module aims to provide a understanding of models for flows in networks and to illustrate these ideas by considering road and communication networks.

• Interactive Formal Verification (L21) – Prof Larry Paulson – 16 h

Introduces students to interactive theorem proving using Isabelle. It includes techniques for specifying formal models of software and hardware systems and for deriving properties of these models.

• Language and Concepts (R207) – Prof Ann Copestake – 16 h

The notion of a concept is crucial to the way that we think about representation of language and human cognition. Concepts are relevant to AI and NLP/computational linguistics as well as other areas of Computer Science which are concerned with modelling the real world in a way which is comprehensible to humans, including semantic web technology. The aim of this course is to start from a computational perspective but to provide an overview of the interdisciplinary issues involved in the study of concepts, including ideas from linguistics, cognitive science, philosophy and neuroscience. The course will be organised as a reading group and assessed by an essay.

• Machine Learning for Language Processing (L101) – Prof Ted Briscoe, Dr Stephen Clark – 16 h

This module aims to provide an introduction to machine learning with specific application to tasks such as document topic classification, spam email filtering, and named entity and event recognition for textual information extraction. We will cover supervised, weakly-supervised and unsupervised approaches using generative and discriminative classifiers based on graphical models, including hidden Markov models, Gaussian mixture models and conditional random fields.

• Nominal Sets and Their Applications (L23) – Prof Andrew Pitts – 8 h

Names and constructs that bind names are ubiquitous in programming languages. Nominal sets provide a mathematical theory of structures involving names, based on some simple, but subtle ideas to do with symmetry and computing with data structures that are infinite, but finite modulo symmetry. The theory has applications to programming language semantics, machine-assisted theorem proving and the design of functional and logical metaprogramming languages. The course introduces the theory of nominal sets, survey some of its applications and highlight potential areas for further research.

• Social and Technological Network Analysis (L109) – Dr Cecilia Mascolo – 16 h

Importance of network theory; graph theory; network analyses [measures]. Random and scale-free networks. Small world behaviour. Applications (to Internet & WWW). Social networks and online social network analysis. Network evolution and cascading.

• Statistical Machine Translation (L102) – Dr Stephen Clark, Dr Bill Byrne – 16 h

This module provides an in-depth introduction to Statistical Machine Translation, the dominant approach to providing large-scale, robust translation applicable to many language pairs (and the approach currently used by Google).

• Syntax and Semantics of Natural Language (L107) – Prof Ted Briscoe, Dr Stephen Clark – 16 h

We will take an in-depth look at how to describe formally a wide-coverage grammar of English using Categorial Syntax and Montague Semantics. We will then go on to study how practical parsers can be developed within this framework capable of returning the most likely compositional interpretation of sentences with high accuracy.

• System on Chip Design and Modelling (P35) – Dr David Greaves – 16 h

A current-day system on a chip (SoC) consists of several different microprocessor subsystems together with memories and I/O interfaces. This practical module covers SoC design and modelling techniques with emphasis on architectural exploration, assertion-driven design and the concurrent development of hardware and embedded software.

• Topics in Logic and Complexity (L15) – Prof Anuj Dawar – 16 h

The course covers the use of methods from logic in the study of computational complexity as well as aspects of logic that can be understood from the perspective of complexity. In particular, it focuses on the study of the expressive power of logical formalisms and methods for proving limitations on this.

• Usability of Programming Languages (R201) – Dr Alan Blackwell – 16 h

Compiler construction is one of the basic skills of all computer scientists, and thousands of new programming, scripting and customisation languages are created every year. Yet very few of these succeed in the market, or are well regarded by their users. This course addresses the research questions underlying the success of new programmable tools. A programming language is essentially a means of communicating between humans and computers. Traditional computer science research has studied the machine end of the communications link at great length, but there is a shortage of knowledge and research methods for understanding the human end of the link. This course provides practical research skills necessary to make advances in this essential field. The skills acquired will also be valuable for students intending to pursue research in advanced HCI, or designing evaluation studies as a part of their MPhil research project.