Overview
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
Physical course materials
The following course materials are included in a course package that will be shipped to your home prior to your course’s start date:
Sipser, M. (2006). Introduction to the Theory of Computation (2nd ed.). Boston, MA: Thompson Course Technology.
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.