Accessibility Skip to Global Navigation Skip to Local Navigation Skip to Content Skip to Search Skip to Site Map Menu

COSC341 Theory of Computing

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
Paper code COSC341
Subject Computer Science
EFTS 0.1500
Points 18 points
Teaching period First Semester
Domestic Tuition Fees (NZD) $1,018.05
International Tuition Fees (NZD) $4,320.00

^ Top of page

Prerequisite
COSC 242 and MATH 160
Schedule C
Arts and Music, Science
Contact
willem@cs.otago.ac.nz
kaye@cs.otago.ac.nz
Teaching staff
Lecturer: Associate Professor Brendan McCane
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.

Assessment:
  • Three written assignments 10% each
  • Final exam 70%
Teaching Arrangements
There are two lectures and two 2-hour tutorials every week/
Textbooks
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

^ Top of page

Timetable

First Semester

Location
Dunedin
Teaching method
This paper is taught On Campus
Learning management system
None

Lecture

Stream Days Times Weeks
Attend
L1 Tuesday 13:00-13:50 9-15, 18-22
Thursday 13:00-13:50 9-15, 17-22

Tutorial

Stream Days Times Weeks
Attend
T1 Tuesday 14:00-15:50 9-15, 18-22
AND
U1 Thursday 14:00-15:50 9-15, 17-22

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
Paper code COSC341
Subject Computer Science
EFTS 0.1500
Points 18 points
Teaching period First Semester
Domestic Tuition Fees Tuition Fees for 2018 have not yet been set
International Tuition Fees Tuition Fees for international students are elsewhere on this website.

^ Top of page

Prerequisite
COSC 242 and MATH 160
Schedule C
Arts and Music, Science
Contact
Computer Science Adviser
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.

Assessment:
  • Three written assignments 10% each
  • Final exam 70%
Teaching Arrangements
There are two lectures and two 2-hour tutorials every week.
Textbooks
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

^ Top of page

Timetable

First Semester

Location
Dunedin
Teaching method
This paper is taught On Campus
Learning management system
None

Lecture

Stream Days Times Weeks
Attend
L1 Tuesday 13:00-13:50 9-13, 15-22
Thursday 13:00-13:50 9-13, 15-22

Tutorial

Stream Days Times Weeks
Attend
T1 Tuesday 14:00-15:50 9-13, 15-22
AND
U1 Thursday 14:00-15:50 9-13, 15-22