Theory of Computing

University of Otago

Course Description

  • Course Name

    Theory of Computing

  • Host University

    University of Otago

  • Location

    Dunedin, New Zealand

  • Area of Study

    Computer Science

  • Language Level

    Taught In English

  • Prerequisites

    COSC242 and MATH160

  • Course Level Recommendations

    Upper

    ISA offers course level recommendations in an effort to facilitate the determination of course levels by credential evaluators.We advice each institution to have their own credentials evaluator make the final decision regrading course levels.

    Hours & Credits

  • Credit Points

    18
  • Recommended U.S. Semester Credits
    3 - 4
  • Recommended U.S. Quarter Units
    4 - 6
  • 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.

    Teaching Arrangements
    There are two lectures and two 2-hour tutorials every week.

    Course 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%

    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

    Textbooks
    Sudkamp, Languages and Machines: an Introduction to the Theory of Computer Science (Third Edition)

Course Disclaimer

Courses and course hours of instruction are subject to change.

Eligibility for courses may be subject to a placement exam and/or pre-requisites.

Some courses may require additional fees.

Credits earned vary according to the policies of the students' home institutions. According to ISA policy and possible visa requirements, students must maintain full-time enrollment status, as determined by their home institutions, for the duration of the program.

Please reference fall and spring course lists as not all courses are taught during both semesters.

Availability of courses is based on enrollment numbers. All students should seek pre-approval for alternate courses in the event of last minute class cancellations

Please note that some courses with locals have recommended prerequisite courses. It is the student's responsibility to consult any recommended prerequisites prior to enrolling in their course.