COMP2270
10 units
2000 level
Course handbook
Description
This course introduces formal models of computation and the problems that they can solve. It presents Turing machines and equivalent models of computation. It also discusses the fundamental limitations of what can be computed. It covers finite state machines, regular expressions and regular grammars as well as context-free languages and grammars and non-context free grammars. It includes algorithms and decision procedures for regular and context-free languages, Turing machine, decidability and complexity analysis
Availability2024 Course Timetables
Callaghan
- Semester 1 - 2024
Learning outcomes
On successful completion of the course students will be able to:
1. Explain the importance of automata as modelling tools and apply them to computational problems
2. Explain the role of context-free languages and their limitations
3. Explain the basis of theory of computation, in particular the role of key problems in defining classes of equivalent problems from a computational perspective
4. Discuss the limitations of computational procedures
Content
- Preliminaries (review of basic mathematical concepts)
- Finite automata
- Language theory
- Turing machine
- Decidability and reducibility
- Complexity theory
Assumed knowledge
MATH1510 Discrete Mathematics, SENG1120 Data Structures
Assessment items
Written Assignment: Assignment 1
Written Assignment: Assignment 2
In Term Test: Class Test
Online Learning Activity: Online multiple choice questions
Formal Examination: Formal Examination
Compulsory Requirement: Pass requirement 40% - Must obtain 40% in this assessment item to pass the course.
Contact hours
Semester 1 - 2024 - Callaghan
Lecture-1
- Face to Face On Campus 2 hour(s) per week(s) for 13 week(s) starting in week 1
Tutorial-1
- Face to Face On Campus 2 hour(s) per week(s) for 12 week(s) starting in week 2
Course outline
- COMP2270 - Semester 1, 2024 (Callaghan) (PDF, 282.4 KB)
The University of Newcastle acknowledges the traditional custodians of the lands within our footprint areas: Awabakal, Darkinjung, Biripai, Worimi, Wonnarua, and Eora Nations. We also pay respect to the wisdom of our Elders past and present.