CECS 341 Theory of Computation

	CECS 341 Theory of Computation
MCVL Homepage	Department of Computer Engineering and Computer Science

Instructor:

Xinhua Zhuang
313 EBW
Department of Computer Engineering and Computer Science
University of Missouri-Columbia
Columbia, MO 65211
Phone: 882-2382
E-mail: zhuang@cecs.missouri.edu
Office Hours: Tuesday and Thursday, 9:15am - 10:00am, or by appointment
WWW: http://meru.cecs.missouri.edu/courses/cecs341

Objectives:

This course introduces the fundamental mathematical models of computation. We study both the inherent capabilities and limitations of these computational models as well as their relationships with formal languages. Topics to be covered include:

Finite automata and regular languages
Deterministic and nondeterministic computations
Context-free grammars, languages, and pushdown automata
Turing machines
Undecidable problems
Computational complexity, NP-completeness

Prerequisites:

CECS 126
CECS 210

Texts (Reserved in Engineering Library)

Introduction to the Theory of Computation, by Michael Sipser, PWS publishing Co., 1997. (Required)
Hopcroft and Ullman, Introduction to automata theory, languages, and computation, by Hopcroft and Ullman, Addison-Wesley, 1979. (Recommended)

Expected Work:

Reading; homeworks (problem sets); one midterm exam and one final exam.

Grading Policy:

Homeworks: 40 %
Midterm Examination: 25 %
Final Examination: 35 %

The midterm exam will be held during one of the normal class periods. The Final will be comprehensive, covering the entire semester.

Homework Submission Policy

Homeworks will be accepted by the end of class on the day it is due.

Your homework should be neat, legible, and identified with your name and the assignment number. It should be comprehensible: clear, concise, well organized, complete, and most of all, well documented. Staple all sheets together before turning them in.

Penalties for Lateness

Every homework assignment will list a due date for full credit. Late assignments will lose 10% of the maximum score per day (measured noon-to-noon). Assignments will not be accepted three days after the due date.

Collaboration

You may assist each other to understand the material that we are teaching. You may discuss homework assignments with other students at a general level. But all problem set solutions and testing must be done entirely on your own.

Penalties for Cheating

Academic honesty is fundamental to the activities and principles of a university. Cheating will not be tolerated and will be severely punished. For the first offense, you will receive a substantial negative score for that assignment. Any additional offense may result in failure for the course.