COMP30010 Foundations of Computing

Academic Year 2023/2024

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 exercises. 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
Lectures

24

Tutorial

22

Autonomous Student Learning

76

Total

122

Approaches to Teaching and Learning:
Lectures; tutorial sessions; written exercises; 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 this module.

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
Incompatibles:
IS10060 - Digital Technology


 
Assessment Strategy  
Description Timing Open Book Exam Component Scale Must Pass Component % of Final Grade
Continuous Assessment: One or more in-class test(s) Varies over the Trimester n/a Graded No

100


Carry forward of passed components
Yes
 
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.

Name Role
Mr Jim Quinn Tutor
Timetabling information is displayed only for guidance purposes, relates to the current Academic Year only and is subject to change.
 
Autumn
     
Lecture Offering 1 Week(s) - Autumn: All Weeks Tues 13:00 - 13:50
Lecture Offering 1 Week(s) - Autumn: All Weeks Wed 11:00 - 11:50
Practical Offering 1 Week(s) - Autumn: All Weeks Thurs 14:00 - 15:50
Autumn