Theoretical Computer Science

Information on the specialist area Theoretical Computer Science.

Theoretical Computer Science (TCS) is the use of mathematical thinking and techniques to understand computer science. It ranges from logical, even philosophical, questions such as ‘what is computation?’, to quite practical questions such as ‘how can we know whether our algorithm is the fastest possible for this problem?’. Edinburgh has been a world leader in TCS for some decades, and the courses here reflect the current interests of staff, as well as the necessary foundations for any TCS course. A particular feature of the Edinburgh understanding of TCS is its connexion to reality: the late Robin Milner saw TCS as an experimental subject, where we make theories, and test them by implementation. Milner’s vision continues to inspire many here.

The primary aims of the theoretical courses are, therefore, to introduce students to core areas of TCS, to provide practical experience of that theory and to introduce students to the technologies through which theory-based tools are implemented, including preparation for PhD study. The courses offered combine a good grounding in the core areas of the subject with experience in the practical application of theory across a range of theory-based Software Engineering tools. These courses will be of particular interest to students with a mathematics background. The practical components of these courses will consider both the use and implementation of tools. Most of the courses in this specialist area aims to provide a balance between theoretical topics and their application in software development, while a few are more purely mathematical. In many of the courses the theory suggests the construction of tools to aid software production. Students will meet a variety of these tools during the course and will have the opportunity to develop skills in their use as well as studying the techniques used in their implementation.

Students registered in this Specialist Area are recommended to select at least fifty credit points from the following courses; however, some students prefer to take only three or four courses, chosen to match with more practical courses. There are no compulsory courses in this specialism. Please note courses are subject to availability.

 

Semester 1 Semester 2
Main Optional Courses (see notes below)

Automated Reasoning (level 9)

Advances in Programming Languages

Computational Complexity

Extreme ComputingIntroduction to Quantum Computing

Performance Modelling

Social and Technological Networks

Types and Semantics for Programming Languages

Algorithms and Data Structures (level 10)

Introduction to Theoretical Computer Science (level 10)

Advanced Topics in Foundations of Databases (20 credits)

Algorithmic Game Theory and its Applications

Categories and Quantum Informatics

Computer Algebra

Introduction to Modern Cryptography

Probabilistic Modelling and Reasoning (20 credits)

Randomness and Computation

Parallel Programming Languages and Systems

Choosing courses

You may be guided either by your mathematical interests, or by the extent to which you would like to understand the theory behind your practical interests. If you are interested in the fundamentals of computation, then you might consider Computational Complexity. 

If you like logic, computer assisted reasoning and artificial intelligence, then consider Automated Reasoning, Computer Algebra, and Logic Programming.

If your interest is in databases, then try Advanced Topics in Foundations of Databases (and Applied Databases, may complement it).

If you want to learn about ways to expand computation over multiple machines up to the scale of the web, look at Distributed Systems, and Extreme Computing.

If you enjoy the challenges of probabilistic and stochastic systems, then consider Probabilistic Modelling and Reasoning or Social and Technological Networks. 

If you are interested in designing algorithms and analysing how well they behave, then look at Algorithms and Data Structures (if you haven't already done a basic algorithms course), Algorithmic Game Theory and its Applications, and Computational Complexity.

If you are interested in programming languages, then consider Advances in Programming Languages, Types and Semantics of Programming Languages, and Parallel Programming Languages and Systems.

Preparation and pre-requisites

Most of the courses will assume a good command of the material in the first two (English or European three-year bachelor's) or three (Scottish or American bachelor's) years of a computer science degree. If you don't have this, then don't worry too much: as long as you have a strong mathematical ability and reasonable knowledge, most TCS courses can be done, though it will be harder work, as you'll have to learn many new concepts. A good place to check your knowledge is to look through the syllabuses of our second year courses Informatics 2A and 2B (and 2D for AI and computer reasoning); if you're not happy that you know most of this, then use the course slides (publicly available) and recommended texts to catch up. Then look at the MSc TCS courses you're interested in, and see if they have pre-requisites here, and check those. (We are flexible about prerequisites and co-requisites: if you are missing something for a particular course, then talk with the course lecturer, and if they're happy, we are.)

Informatics 2A - Processing Formal and Natural Languages

Informatics 2B - Algorithms, Data Structures, Learning

Informatics 2D - Reasoning and Agents 

Related links

Informatics sortable course list

Informatics course timetable