Lectures: Tuesdays and Thursdays - 10:50-12:05 pm - Pereira Hall 109
Instructor: Philip Dorin - Doolan 102 - (310) 338-2832 - philip.dorin@lmu.edu
Secretary: Jacqi Davis - Doolan 101 - (310) 338-7351 - JaDavis@lmu.edu
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.
Some of the material in this course (especially the stuff having to do with regular expressions, finite automata, context-free languages, and pushdown machines) is needed in, and is, therefore, pre-requisite to CMSI 488.
CMSI 281 - Data Structures and Algorithms I
MATH 248 - Introduction to Methods of Proof
Hopcroft, Ullman, and Motwani. Introduction to Automata Theory, Languages, and Computation (3rd edition). Addison-Wesley, 2007.
Expect, roughly, a new homework assignment each class; a mid-term exam (Thursday, October 22); and a two-hour final exam (11 am, Tuesday, December 15).
In evaluating the quality of your work, I will take into consideration your total course effort, including homework, midterm exam, and final exam, with emphasis on the exams.
Grades will be awarded as follows: for superior work, A; for good work, B; for satisfactory work, C; for poor work, D; for failing work, F. At the discretion of the instructor, these may be raised by a + or lowered by a -.
Regarding academic honesty and integrity, students are referred to the LMU Bulletin 2008-2010, specifically, the section dealing with the university's honor code and process.
Kindly turn off the ringer on your cell phone before class begins.
Music players, laptops, netbooks, etc., should not be used during class.
The contents of this syllabus are subject to change, as necessary. You should periodically monitor this website to keep abreast of any changes, as well as posted homework assignments, hints, solutions, etc.
Revised: 22:00 on 18 November 2009