Skip to main content

Computer Science core 2

Contents

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.

Concurrent Programming

We want to make computer software run faster and we want to improve our ability to use the facilities provided by modern multi-core processors and multi-processor supercomputers to do this. We also want to be able to build reliable distributed systems -- systems that necessarily use more than a single computer working alone. The principal aim of this course is to begin to present some of the big programming challenges that arise naturally from these requirements and to begin to introduce practical techniques for tackling them. Happily it also turns out that many of the techniques (such as message-passing) that arise naturally when thinking about these challenges can be applied profitably to the design of programs that may only ever be run on one, single-core, processor. In this case the payoff is in the improvement in conceptual clarity and maintainability of the designs.

Compilers

This course aims to give a simple but practical account of the programming techniques used in implementing high-level programming languages by compiling into code for stack and register-based machines. The course is based on a working implementation, written in Objective Caml, of a compiler for a language comparable to C or Pascal.

Algorithms and Data Structures

This course presents a number of highly efficient algorithms and data structures for fundamental computational problems across a variety of areas, including amortised complexity analysis, maximum flows and applications, linear programming, approximation algorithms, and fixed parameter algorithms.