Skip to navigation | Skip to main content | Skip to footer
Menu
Menu

COMP11212 Fundamentals of Computation syllabus 2017-2018

COMP11212 materials

COMP11212 Fundamentals of Computation

Level 1
Credits: 10
Enrolled students: 192

Course leader: Sean Bechhofer


Additional staff: view all staff

Requisites

  • Co-Requisite (Compulsory): COMP11120

Additional requirements

  • Students who are not from the School of Computer Science must have permission from both Computer Science and their home School to enrol.

Assessment methods

  • 75% Written exam
  • 25% Coursework
Timetable
SemesterEventLocationDayTimeGroup
Sem 2 Lecture Roscoe TH B Tue 11:00 - 12:00 -
Sem 2 Lecture Roscoe TH B Mon 11:00 - 12:00 -
Sem 2 w2+ Examples G41 Mon 13:00 - 14:00 M+W
Sem 2 w2+ Examples G41 Mon 14:00 - 15:00 X
Sem 2 w2+ Examples G41 Mon 15:00 - 16:00 Z
Sem 2 w2+ Examples G41 Mon 16:00 - 17:00 Y

Overview

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 very annoying, costly and sometimes life threatening. Methods and techniques to support the building and understanding of such systems are essential. This course unit provides an introduction to the basic computer science ideas underlying such methods. It is also a part of, and an introduction to, the Modelling and Rigorous Development theme.

Aims

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 recognizing 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?

Syllabus

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

Teaching methods

Lectures

22 in total, 2 per week

Examples classes

1 per week (starting in week 2)

Feedback methods

Students present their solutions to set exercises once a week in examples classes. They receive oral feedback to their solutions, and have the opportunity to improve some of their original answers for further feedback.

Study hours

  • Assessment written exam (2 hours)
  • Lectures (24 hours)
  • Practical classes & workshops (11 hours)

Employability skills

  • Analytical skills
  • Oral communication
  • Problem solving

Learning outcomes

Programme outcomeUnit learning outcomesAssessment
A1 B1Describe formal languages using a variety of mechanisms.
  • Examination
  • Individual coursework
A1 B1Define classes of languages and demonstrate translations between those classes.
  • Examination
  • Individual coursework
A1 B1State key properties of classes of languages and determine when those properties hold.
  • Individual coursework
  • Examination
A1 B1Define models of computation and use those models to demonstrate what can and cannot be computed.
  • Individual coursework
  • Examination
A1 B1Produce program specifications and proofs of program correctness.
  • Examination
  • Individual coursework
A1 B1Describe computational complexity and identify the complexity of programs.
  • Examination
  • Individual coursework

Reading list

TitleAuthorISBNPublisherYearCore
Logic in Computer Science: modelling and reasoning about systems.Michael Huth and Mark Ryan.978-0-521-54310-12004
Introduction to Automata Theory, Languages, and ComputationJohn E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman0-201-44124-1Pearson Education2001
Introduction to the Theory of ComputationMichael Sipser978-8131525296Cengage Learning2014

Additional notes

Course unit materials

Links to course unit teaching materials can be found on the School of Computer Science website for current students.