Students entering this course should have a strong background in discrete mathematics, data structures, and algorithms. Students concerned they may not meet the prerequisites for this course are encouraged to contact the course coordinator before registering.

This is a graduate level course and students need to apply and be approved to one of the graduate programs or as a non-program School of Computing and Information Systems graduate student in order to take this course. Minimum admission requirements must be met. Undergraduate students who do not meet admission requirements will not normally be permitted to take this course.

Computer Science 674 is an elective course in the "Theory Stream" of the MSc(IS) program. Central to the theory of computation are the concepts of automata, formal languages, grammar, algorithms, computability, decidability, and complexity. Why study theory when the current focus of Computer Science (and all the more so for Information Systems) is on technology and the pragmatic areas of knowledge concerned with the development and management of computer information systems? The reasons are manifold. Theory provides a simple, elegant view of the complex machine that we call a computer. Theory possesses a high degree of permanence and stability, in contrast with the ever-changing paradigms of the technology, development, and management of computer systems. Further, parts of the theory have direct bearing on practice, such as Automata on circuit design, compiler design, and search algorithms; Formal Languages and Grammars on compiler design; and Complexity on cryptography and optimization problems in manufacturing, business, and management. Last, but not least, research-oriented students will make good use of the theory studied in this course.

Outline

Unit 0: Formation of Preliminary Concepts

Automata, computability, and complexity

Mathematical tools

Definitions, theorems, and proofs

Types of proofs

Unit 1: Regular Languages

Finite automata

Nondeterminism

Regular expressions

Nonregular languages

Unit 2: Context-Free Languages

Context-free grammars

Pushdown automata

Non-context-free languages

Unit 3: The Church-Turing Thesis

Turing machines

Variants of Turing machines

Definition of "algorithm"

Unit 4: Decidability

Decidable languages

The halting problem

Unit 5: Reducibility

Undecidable problems in language theory

A simple undecidable problem

Mapping reducibility

Unit 6: Advanced Topics in Computability

The recursion theorem

Decidability of logical theories

Turing reducibility

A definition of "information"

Unit 7: Time Complexity

Measuring complexity

The class P

The class NP

NP-completeness

NP-complete problems

Learning outcomes

Upon successful completion of this course, you will be able to

discuss key notions of computation, such as algorithm, computability, decidability, reducibility, and complexity, through problem solving.

explain the models of computation, including formal languages, grammars and automata, and their connections.

state and explain the Church-Turing thesis and its significance.

analyze and design finite automata, pushdown automata, Turing machines, formal languages, and grammars.

solve computational problems regarding their computability and complexity and prove the basic results of the theory of computation.

Objectives

The learning objectives of this course are to:

introduce students to the mathematical foundations of computation including automata theory; the theory of formal languages and grammars; the notions of algorithm, decidability, complexity, and computability.

enhance/develop students' ability to understand and conduct mathematical proofs for computation and algorithms.

Evaluation

To receive credit for COMP 674, you must achieve a cumulative course grade of B- (70 percent) or better, and must achieve an average grade of at least 60% on the assignments and 60% on the final examination. Your cumulative course grade will be based on the following assessment.

Activity

Weight

Assignment 1 (after Unit 2)

20%

Assignment 2 (after Unit 5)

20%

Assignment 3 (after Unit 7)

20%

Final Exam (2-day take-home)

40%

Total

100%

Materials

Sipser, M. (2006). Introduction to the Theory of Computation (2^{nd} ed.). Boston, MA: Thompson Course Technology. (Print)

Other materials

The remaining learning materials are distributed in electronic format. At this time, these materials include:

Units 1 to 7 of the Study Guide.

A Study Plan listing the required course completion tasks in logical order.

Detailed descriptions of the requirements for each Assignment.

Additional supporting materials of interest to students may occasionally be made available electronically via the course website and conference.

Special Course Features

IS courses at Athabasca University require that students use computer-mediated communications. We expect students to have access to a computer with connection to the Internet.

Workload for Students in COMP 674

Students can expect to spend a weekly total of 5 to 25 hours on course work--depending on their level of mathematical maturity.

Special Note

Students registered in this course will NOT be allowed to apply for a course extension due to the nature of the course activities.

Athabasca University reserves the right to amend course outlines occasionally and without notice. Courses offered by other delivery methods may vary from their individualized study counterparts.

Opened in Revision 2, April 18, 2012

Updated February 2, 2022, by Student & Academic Services