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:

Prerequisites:

Texts (Reserved in Engineering Library)

Expected Work:

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

Grading Policy:

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.


Lecture Notes

These lecture notes are in pdf format. You will need Adobe Acrobat Reader to read them.

Theory of Computation

Mathematical Preliminaries

Mathematical Preliminaries

Finite Automata

Regular Languages

Nondeterminism

Regular Languages

Regular Expressions

Pumping Lemma

Summary of Finite Automata

Context-Free Languages

Review

Pushdown Automata

Pushdown Automata

PDA: Equivalence with CFG

Pumping Lemma for CFLs

Properties of CFLs

Universal Models of Computation

Turing Machine

Variants of Turing Machines

Notation of Algorithm

Complexity Theory

The Class P

The Class NP

NP-Completeness


[Home]CECS Multimedia Communications and Visualization Laboratory