COMP31020

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 include:
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 enough?)

Student Effort Hours:

Approaches to Teaching and Learning:

Requirements, Exclusions and Recommendations

Students should have a sound knowledge of mathematics (including set theory, functions and relations, logic, and basic proof techniques) to take this module.

It is STRONGLY RECOMMENDED that students take and pass all first and second stage theory modules in CS before taking this module. If a student has not successfully completed these modules, they should consult the Module Coordinator BEFORE registering for COMP31020.

Module Requisites and Incompatibles

Assessment Strategy

Feedback Strategy/Strategies

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

How will my Feedback be Delivered?

Not yet recorded.