COMP30010 Foundations of Computing

Academic Year 2021/2022

This module introduces a branch of computer science named language and automata theory, and covers concepts from computing theory and complexity theory. In particular, it discusses computation models (finite automata, regular expressions, pushdown automata, turing machines), undecidability (what can be computed at all?) and intractability (how fast can it be computed?).

The student will come to understand how these theories relate to, and are used in, everyday practice. Students learn concepts, tools, and techniques individually through a series of written and graded assignments. There are weekly tutorial sessions with demonstrator support.

Show/hide contentOpenClose All

Curricular information is subject to change

Learning Outcomes:

On completion of this module students should be able to:
- Define and use general concepts like computation, algorithm, and language;
- Work with several models of computing including finite state machines, Turing machines, and automata;
- Use appropriate computation models for real applications;
- Understand and use notions of computability and decidability, and their limits;
- Understand and explain the relationships between mathematical proof and computation.

Indicative Module Content:

The topics covered in this module are:
1. Regular Languages (Finite Automata, Regular Expressions)
2. Context-free Languages (Pushdown Automata, Context-free Grammars)
3. Recursively Enumerable Languages (Turing Machines)
4. Undecidability (Does a computer solution/algorithm exist?)
5. Intractability (Can it be solved fast?)

Student Effort Hours: 
Student Effort Type Hours
Autonomous Student Learning








Approaches to Teaching and Learning:
Lectures; tutorial sessions; homework assignments, submitted individually; one or more in-class test(s).
Requirements, Exclusions and Recommendations
Learning Requirements:

Students should have basic knowledge of mathematics (including set theory, functions and relations, logic, and basic proof techniques) to
attend for this module. Students unfamiliar with these topics must
attend remedial tutorials at the beginning of the semester.

Learning Recommendations:

It is strongly recommended that students take and pass all first and
second stage theory modules in CS before taking this module.

Module Requisites and Incompatibles
IS10060 - Digital Technology

Assessment Strategy  
Description Timing Open Book Exam Component Scale Must Pass Component % of Final Grade
Class Test: One or more in-class test(s) Varies over the Trimester n/a Alternative linear conversion grade scale 40% No


Continuous Assessment: Homework Assignments Varies over the Trimester n/a Alternative linear conversion grade scale 40% No


Carry forward of passed components
Resit In Terminal Exam
Spring No
Please see Student Jargon Buster for more information about remediation types and timing. 
Feedback Strategy/Strategies

• Feedback individually to students, post-assessment
• Group/class feedback, post-assessment

How will my Feedback be Delivered?

Not yet recorded.

Timetabling information is displayed only for guidance purposes, relates to the current Academic Year only and is subject to change.
Lecture Offering 1 Week(s) - Autumn: All Weeks Tues 13:00 - 13:50
Lecture Offering 1 Week(s) - 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12 Wed 11:00 - 11:50
Lecture Offering 1 Week(s) - 12 Wed 11:00 - 11:50
Practical Offering 1 Week(s) - Autumn: All Weeks Thurs 14:00 - 15:50
Practical Offering 2 Week(s) - Autumn: All Weeks Fri 14:00 - 15:50