Instructor: Dr. James Glenn
Office: DS 125d
Work Phone: (410)617-5394
FAX: (410)617-2157
Office Hours: M 2-3:30, W 10-10:55, TH 10:40-12:30, F 12-12:55, or by appointment
e-mail:[first initial][last name]@cs.loyola.edu

Course Home Page: http://gunpowder.cs.loyola.edu/~jglenn/478/S2007/index.html

Class Meeting: MWF 1:00pm-1:50pm; Room TBA

Prerequisites: CS/MA 295 (Discrete Structures) or MA 395 (Discrete Methods)

Required Text: Elements of the Theory of Computation (2nd ed.) by Lewis and Papadimitriou

Course Description:
Basic results on the capabilities, limitations, and applications of formal models of computation. Includes finite state machines, push down automata, grammars, computable and non-computable functions, and NP-completeness.

Specific Educational Objectives of the Course:
At the completion of the course, the student will be able to:

• construct finite automata to recognize regular languages;
• perform basic transformations on finite automata such as intersection, determinization, and minimization;
• recognize languages that are not regular;
• construct grammars to generate context-free languages;
• recognize languages that are not context-free;
• construct Turing Machines to compute elementary functions;
• explain the connection between the P vs. NP problem and deterministic and non-deterministic Turing Machines;
• recognize non-computable functions; and
• demonstrate the equivalence of various advanced models of computation.

Conduct of the Course:
Lectures will be used to introduce, explain, and analyze new concepts. Readings from the required textbook will enhance students' understanding of those lectures. Weekly homework assignments (not necessarily done at a computer) will reinforce the concepts discussed in lecture. There will be one final project which can be a research, programming, or mathematical project according to students' individual interests. One midterm exam and a final exam will also be used to evaluate students' progress.

Academic Integrity:
Loyola College Honor Code Statement:

"The Honor Code states that all students of the Loyola Community have been equally entrusted by their peers to conduct themselves honestly on all academic assignments.

The students of this College understand that having collective and individual responsibility for the ethical welfare of their peers exemplifies a commitment to the community. Students who submit materials that are the products of their own minds demonstrate respect for themselves and the community in which they study.

All outside resources or information should be clearly acknowledged. If there is any doubt or question regarding the use and documentation of outside sources for academic assignments, your instructor should be consulted. Any violations of the Honor Code will be handled by the Honor Council"

The Honor Code as is pertains to this class: All designs and code used for programming projects should be the work of only the student submitting the project. Work on research projects and exams should be solely the work of the student whose name appears on the work.

Grading:

• Homework: 30%
• Final Project: 15% (presentations during exam period Wed, May 2 at 1pm)
• Midterm Exams: 15% each (Fri, Feb 23 and Mon, Apr 2)
• Final Exam: 25% (Take home; due Wed, May 2)

Final Grade Distribution:
Final letter grades will be no worse than those in the following table.

A	A-	B+	B	B-	C+	C	C-	D+	D
93%	90%	87%	83%	80%	77%	73%	70%	67%	60%

Topics:

• Deterministic finite automata (DFAs)
• Constructing DFAs
• Operations on DFAs
• Non-deterministic finite automata (NDFAs)
• Equivalence of DFAs and NDFAs
• Limitations of DFAs
• Push-down automata
• Context-free grammars
• Limitations of context-free grammars
• Turing Machines
• The Church-Turing Thesis
• Non-computable functions
• NP-completeness

Midterm Exams: Friday, February 23rd and Monday, April 2nd

FINAL EXAM: Take Home; due Wednesday, May 2nd