Fundamentals of Computation

The building of real-life computing systems, e.g. mobile phone, TV/video remote control, internet shopping, air-traffic control, internet banking, etc., is always a complex task. Mistakes can be not just annoying, but also costly and sometimes life threatening. Formal methods and techniques to support the building and understanding of such systems are essential. This course unit provides the basic computer science ideas underlying such methods. It introduces mathematical models that allow the description, verification, and analysis of computing systems and their limitations. 

Students who are not from the Department of Computer Science must have permission from both Computer Science and their home Department to enrol. Computer Science and Maths students do not need COMP11120.

COMP11120 is a co-requisite except for BSc(Hons) Computer and Science and Maths students

This course unit provides a first approach to answering the following questions. What methods are there that can help understanding complicated systems or programs? How can we make sure that a program does what we intend it to do? How do computers go about recognising pieces of text? If there are two ways of solving the same problem, how can we compare them? How do we measure that one of them gives the solution faster? How can we understand what computers can do in principle, and are there problems that are not solvable by a computer? 

ILO 1: Describe computational complexity and identify the complexity of programs

ILO 2: Define models of computation and use those models to demonstrate what can and cannot be computed

ILO 3: Develop program specifications and proofs of program correctness

ILO 4: Identify classes of formal languages and demonstrate translations between those classes

ILO 5: Describe formal languages using a variety of mechanisms

ILO 6: Develop key properties of classes of formal languages and determine when those properties hold

There are two groups of topics covered. One of the lectures will be an introduction to the course unit, and one is reserved for revision. That leaves 10 lectures for each part.

The first part (10 lectures) is concerned with expressing particular strings, and collections of strings, and here we will introduce the methods by which a computer goes about it. The ability to recognize key strings (such as programming constructs or variable names) are, for example, required in every compiler, but they are also used by search engines such as Google.The formalisms introduced include finite state automata, regular expressions (most often used in pattern matching), (regular) grammars. The emphasis is on students being able to use these formalisms to solve problems.

The second half of the course (10 lectures) provides an introduction to the topics of complexity, correctness and computability. There are four big topics:

                • the WHILE programming language

                • asymptotic complexity

                • partial and full program correctness

                • computability

This unit is delivered in a blended manner with a mix of asynchronous and synchronous activities. Self-study materials are made available in the form of detailed notes which include exercises, as well as videos and formative self-assessment quizzes that allow students to check their understanding. Each week there is a synchronous session that allows students to ask questions about the materials and beyond, and discuss the ideas underlying the taught material. Further there are weekly synchronous examples classes where solutions to the assessed exercises are discussed.

 

Asynchronous video content, approximately 1 hour of content per week.

Synchronous Q&A/worked examples sessions, 1 hour per week.

Synchronous examples classes, 1 per week (starting in week 2)

 

Students are expected to spend 4-5 hours each week engaging with asynchronous materials such as notes, video and exercises.

Weekly online self-assessment quizzes.

Students present their solutions to set exercises once a week in examples classes. They receive oral feedback to their solutions.

Written feedback is given for summative exercises.

1. Michael Sipser. (2013). Introduction to the Theory of Computation. Cengage Learning. ISBN: 113318779
    
2. Sipser, Michael. (2013). Introduction to the theory of computation. Cengage Learning. ISBN: 9781133187813
    
3. Huth, Michael. (2004). Logic in computer science: modelling and reasoning about systems. Cambridge University Press. ISBN: 9780511810275
    
4. Hopcroft, John E., 1939-. (2014). Introduction to automata theory, languages, and computation. Pearson Education. ISBN: 9781292056166