Finite state machines and Turing machines; limits to computation and effective procedures; recursive functions and predicates; notions of complexity, and completeness.
This paper covers the fundamental topics of Computer Science as a discipline. COSC 341 is a theoretical paper, but there are many practical implications of the theory - including, but not limited to, categorising problems as easy, hard or impossible.
|Paper title||Theory of Computing|
|Teaching period||First Semester|
|Domestic Tuition Fees (NZD)||$1,038.45|
|International Tuition Fees (NZD)||$4,492.80|
- COSC 242 and MATH 160
- Schedule C
- Arts and Music, Science
- Computer Science Adviser
- More information link
- View more information about COSC 341
- Teaching staff
- Lecturers: Associate Professor Brendan McCane and Dr Yawen Chen
- Paper Structure
- This paper, which assumes some mathematical background, will explore the hierarchy
of languages that are accepted by the fundamental machines of computer science, including
finite automata and Turing machines. Discussion of the limits to computation will
lead to a review of classic problems, such as the "halting problem." The paper concludes
with a discussion of cost in space and time and the classification of languages and
problems according to their complexity.
- Three written assignments 10% each
- Final exam 70%
- Teaching Arrangements
- There are two lectures and two 2-hour tutorials every week.
- Sudkamp, Languages and Machines: an Introduction to the Theory of Computer Science (Third Edition)
- Course outline
- View the course outline for COSC 341
- Graduate Attributes Emphasised
- Interdisciplinary perspective, Lifelong learning, Scholarship, Communication, Critical
thinking, Information literacy, Research, Self-motivation.
View more information about Otago's graduate attributes.
- Learning Outcomes
- Students will gain an understanding of:
- The theoretical foundations of computer science
- Fundamental descriptions of machines and their capabilities
- The hierarchy of languages and the type of machine required to recognise them
- The limits of computation
- The computational classes P and NP
- Common proof methods for classifying a problem in P, NP or NP-complete
- Basic concepts of approximation algorithms for hard problems