CMSI 385 - Introduction to the Theory of Computation
Home Page and Course Syllabus - fall, 2008
Brief contents
- Class Meetings and Personnel
- Lectures: Tuesdays and Thursdays - 1:35-2:50 pm - Doolan Hall 222
- Instructor: Philip Dorin - Doolan 102 - (310) 338-2832 - pdorin@lmu.edu
- Secretary: Jacqi Davis - Doolan 101 - (310) 338-7351 - JaDavis@lmu.edu
- Objectives and Topics
- The goal is to become familiar with some of the main ideas in the theory of computation. We will emphasize classical automata (especially finite automata, pushdown automata, and Turing machines); formal grammars and languages (especially regular sets, context-free languages, recursive and recursively enumerable languages); computability and decidability.
- Prerequisites
- CMSI 281 - Data Structures and Algorithms I
- MATH 248 - Introduction to Methods of Proof
- Textbook
- Hopcroft, Ullman, and Motwani. Introduction to Automata Theory, Languages, and Computation (3rd edition). Addison-Wesley, 2007.
- Coursework and Grading
- Expect a homework assignment almost every class; a mid-term exam; and a final exam.
- In evaluating the quality of your work, I will take into consideration your total course effort, including homework, quizzes, final exam, and participation (which includes attendance at lectures). Grades will be awarded as follows:
- A... for superior work
- B... for good work
- C... for satisfactory work
- D... for poor work
- F... for failing work
These may be raised by a '+' or lowered by a '-' as deemed appropriate by the instructor.
- Homework Assignments
Revised: August 15, 2008