CMSC 452 Elementary Theory of Computation

Fall 2005

Class Time: Tuesday and Thursday 12:30-1:45 in CSI 2118.

Instructor: Clyde P. Kruskal. Office: AV Williams 3215. Office phone: 405-2683.
e-mail: Office Hours: Tuesday and Thursday 2:00pm-3:30pm.
Appointments can be made for other times.

Teaching Assistant: Naiqing Gu. Office: AVW 3212.
e-mail: Office Hours: Monday 2:00pm-4:00pm, Friday 2:00pm-3:00pm in AVW 1112.
Appointments can be made for other times.

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 nal). 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. The clarity and conciseness of your presentation will count in the grading of homeworks and exams.

Grading: Final grades will be based on homework assignments, a midterm exam, and a comprehensive final exam. The relative weights of these will be approximately 20% for the homework total, 35% for of the midterm, and 45% for the final exam.

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).
- Finte Automata
- Context Free Languages
- Turing Machines
- Undecidability
- Computational Complexity
We may also cover other topics including
- Recognizing Context Free Languages
- Primitive Recursive Functions
- Context Sensitive Languages

PDF version of the syllabus


Homework 1

Homework 2

Homework 3

Homework 4

Homework 5

Homework 6