CMSC 452 Elementary Theory of Computation

Spring 2009

Class Time: Tuesday and Thursday 11:00am-12:15pm in CSI 2107.

Instructor: Clyde P. Kruskal. Office: AV Williams 3215. Office phone: 405-2683.
e-mail: kruskal at Office Hours: Tuesday, Thursday 1:15pm - 2:45pm. Appointments can be made for other times.

Teaching Assistant: Amitkumar Patel.
email: amit123 at Office Hours: Monday 2:30pm - 3:30pm. Also by Appointment.

Course Overview: Theoretical models of computation, formal grammars and languages, and their relationships. Classifying languages by the mechanisms needed to parse them.

Prerequisites: CMSC 250 and 351. Students are expected to know the basic concepts of discrete mathematics such as simple logic, proof by induction, basic set theory, relations and functions, and equivalence classes.

Course Work: Course work consists of homework assignments (about every week and a half) and two exams (a midterm and final). Homeworks are due by the start of class on the due date. You may discuss general course material and homework problems with classmates, but you should do the homework problems yourself. Assignments are to be written up neatly. Submissions with multiple pages must be stapled. The clarity and conciseness of your presentation will count in the grading of homeworks and exams.

Required Text: Efim Kinber and Carl Smith, Theory of Computing, A gentle Introduction, Prentice-Hall, Inc., Upper Saddle River, New Jersey, 2001. Supplemental Text: H. Lewis and C. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, Inc., Upper Saddle River, New Jersey, 1981.

Syllabus: The following topics from the book will be covered (with the possible exception of the last topic).
- Finte Automata
- Context Free Languages
- Turing Machines
- Undecidability
- Computational Complexity

Other topics that may be covered include:
- Recognizing Context Free Languages
- Primitive Recursive Functions
- Context Sensitive Languages
- PCP and Zero-Knowledge

Here is the syllabus in pdf and in ps


Homework1 pdf ps
Homework2 pdf ps
Homework3 pdf ps
Homework4 pdf ps