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 (2nd 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.