Course Calendar              Homework             Interactive Classroom

Sign up for the interactive classroom to view your scores, submit homework, or simply chat about topics discussed in class. All you need is request an account by accessing the Interactive Classroom and clicking at the 'Request an Account' button under the 'Student' heading.

Course Objectives

The goal of this course is to provide solid knowledge of the fundamental concepts and methods of the theory of computation, and to outline some research trends. Two different approaches for "capturing" the idea of computing in a formal mathematical way are discussed - finite state machines and grammars. At the end of the course students will be able to interprete, relate and apply the basic concepts of the theory of computation to problems from different areas of computer science.

Course Overview

We will focus on two distinct and equivalent computing paradigms  - finite state machines, and, rewriting rules or grammars.  Each paradigm is first introduced in its simplest form and gradually generalized. We will proceed from deterministic finite automata, regular expressions and grammars to push down automata and context free grammars, and finally to Turing machines and general grammars.  The languages defined (recognized or accepted) by the two formalisms and the relations between them  are presented in the framework of the Chomsky hierarchy. A discussion of the Church-Turing thesis and its implications summarizes our present knowledge of a "mechanical" computation. The course ends with an outlook to the topics of uncomputability/undecidability and untractable problems.

Prerequisites

MET CS 566 Algorithms.

Course Format and Grading Policy

New material will be presented in lecture format. Reviews, exercises and homework solutions will take place in discussion. Participation in the discussions, although not mandatory, is strongly recommended and may result in extra credit.

Weekly mandatory homework, a midterm and a final examination will provide the basis for the grade. Homeworks are due one week after handed out. Late homework will not be accepted unless permission by the instructor was given prior to the due date.

 No predetermined scale will be used. The final grade will be assigned based on the following weighting

Cheating and plagiarism will not be tolerated. They will result in no credit for the homework or examination. This should not be understood as a discouragement for discussing the material or your particular approach to a problem with other students in the class. On the contrary - I urge you to share your thoughts, questions and solutions. Naturally, if you choose to work in a group, I will be expecting more than one and highly original solutions rather than the same mistakes.

Texts

P. Linz. An Introduction to Formal Languages and Automata. D.C. Heath and Co, 1990 (required).

H. R. Lewis, C. H. Papadimitriou. Elements of the theory of computation. Prentice-Hall, 1998 (optional).

Additional reading lists on specific topics will be distributed throughout the semester.  A good reference book for the theoretically incled student is J. E. Hopcroft, J. D. Ullman. Introduction to automata theory, languages and computation. Addison Wesley, 1979.

Course Information

Page prepared by Tanya Zlateva