Red X iconGreen tick iconYellow tick icon

    Overview

    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.

    About this paper

    Paper title Theory of Computing
    Subject Computer Science
    EFTS 0.15
    Points 18 points
    Teaching period Semester 2 (On campus)
    Domestic Tuition Fees ( NZD ) $1,173.30
    International Tuition Fees Tuition Fees for international students are elsewhere on this website.
    Prerequisite
    (COSC 201 or COSC 242) and (MATH 130 or MATH 140) (MATH 160 or MATH 170 prior to 2022)
    Schedule C
    Arts and Music, Science
    Contact

    Computer Science Adviser

    Teaching staff

    Lecturer: 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

    No textbook is required.

    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

    Timetable

    Semester 2

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

    Lecture

    Stream Days Times Weeks
    Attend
    A1 Monday 14:00-14:50 29-35, 37-42
    Tuesday 14:00-14:50 29-35, 37-42

    Tutorial

    Stream Days Times Weeks
    Attend
    A1 Monday 16:00-17:50 29-35, 37-42
    Tuesday 16:00-17:50 29-35, 37-42
    Back to top