The University of Cambridge provides world class Computer Science courses. Stephen works as a Computer Science supervisor (mostly for Churchill College) and this page describes his work from his perspective.

Operating Systems

Years supervised: 2012/2013, 2013/2014, 2014/2015, 2015/2016 (will also be supervising for 2016/2017)

My most supervised course (5 years in a row), this is a first year course that goes through the basic details of operating systems, including:

  • Kernel design: Microkernel vs Monolithic
  • Scheduling algorithms
  • Paging, page tables, page replacement, etc.
  • I/O
  • File systems
  • Linux and Windows case studies (Windows returned as a case study last year)

C and C++

Years supervised: 2012/2013, 2013/2014, 2014/2015 (will also be supervising for 2016/2017)

This course goes through the key details of the C and C++ programming languages. I really like this course but it’s a difficult one for the students (C and C++ are complex); the recommended number of supervisions was recently increased to reflect this.

Prolog

Years supervised: 2014/2015

Prolog is a very interesting programming language because it expresses programs declaratively (describing what needs to be done to compute the result) rather than imperatively (describing how to compute the result). Here’s an example of a routine to concatenate two lists:

concat([], L, L).
concat([H|T], L, [H|R]) :- concat(T, L, R).

In an imperative language it might look something like:

concat(A, B):
	new_list = B
	for element in reversed(A):
		new_list = [element | new_list]
	return new_list

The course focuses on how Prolog is evaluated, since this is needed to understand the ‘cut’ operator (which prevents backtracking) and structures such as difference lists.

Complexity Theory

Years supervised: 2014/2015

Computational problems can be put into groups depending on how long it takes to solve them. For example, P is defined as the set of all decision problems (i.e. problems with a yes/no answer) that can be solved in a polynomial number of steps (O(N^X) where N is related to the input size and X is a constant) on a deterministic Turing machine.

Complexity theory defines many of these sets, such as P, NP, NP-hard etc. and attempts to answer questions like the famous open problem of whether P = NP.

The course shows that different problems are actually related to each other through the conversions used and also suggesting that some common problems may require exponential time (in practice these problems are usually solved by faster algorithms that are very good but not optimal).

Compiler Construction

Years supervised: 2014/2015

Compilers are important tools and deploy a lot of theory, including:

  • Regular expressions in the lexer
  • Context-free grammars in the parser
  • Flow analysis in the optimiser
  • Graph colouring in the register allocator
  • etc.

This course covers how to get from source code to machine code mostly without worrying about optimisation (that’s covered by the third year course ‘Optimising Compilers’).

Numeric Methods

Will be supervising for 2016/2017