CS 390 Introduction to Theoretical Computer Science

Spring 2012

See also Orientation Materials


Shunichi Toida, Emeritus Professor
Department of Computer Science, ODU
Office: Dragas 1100H


John C. Martin,
Introduction to Languages and the Theory of Computation,
4th ed., McGraw-Hill, Inc., New York, NY, 2011.


CS 381 (formerly CS 281) Introduction to Discrete Structures
This prerequisite is a must.

MATH 163 (Pre-Calculus II) or equivalent.
Calculus is preferred but not required.

Homework     20%
Test x 1     40%
Final Exam     40%

Test and exam are closed book. In the exam (but not for the test) you may use a one page cheat sheet.
Calculators/computers are NOT allowed.

Important Note:

Lying, cheating, plagiarism and failure to report such cases
all constitute violation of the Honor System.

Office Hours:

Wednesdays 2:30p.m. - 4:00p.m.
You may also walk in any other time or make an appointgment.

Final Exam : 1:00 - 3:30 a.m. Saturday, April 28, 2012 --- Tentative

Course Objectives:

The main objective of this course is to study the concept of computation and limitations of computer and computation. By rigorously expressing the concept of computation, one can characterize problems which are solvable using computers, solvable but hard to solve or relatively easy to solve without referring to any specific computer. In the process, important subjects (practically as well as theoretically) such as finite automata, Turing machines, regular languages and context-free languages are introduced and studied. It is also an important objective of this course that we train ourselves in logical thinking and problem solving. Finally it is also hoped that we become able to read rigorous technical articles.

Course Contents:

First basic mathematics involving relations, functions, mathematical induction and recursive definitions, which are given in Chapter 1, are reviewed. Then in Chapters 2 and 3, one of the practically important classes of languages - regular languages - is studied along with finite automata which process them. Following that, another important class - context-free languages - and push-down automata presented in Chapters 4 -6 are briefly looked at. The theory of regular languages and context-free languages is heavily used in the design of compilers for high level programming languages. Then the key mathematical model for computation - Turing machine - presented in Chapter 7 is studied. It is known that any computer is as powerful as a Turing machine. Also it is conjectured (and generally accepted) that any so called "computation" is a computation by a Turing machine with appropriate built-in rules. Finally, using the concepts of computation and Turing machine, it is shown that there are problems which can not be solved by any computer, which is discussed in Chapter 9.