Instructor: John Martin, IACC 258 A13, Phone (231)-8197, email John.Martin@ndsu.edu
Class: MWF, 12-12:50, IACC 104
Office Hours: 10:30-11:30 MWF and by appointment.
Course Description: Parsing techniques, context-free languages, Turing machines, recursive and recursively enumerable languages, unrestricted grammars, unsolvable decision problems, computability, introduction to computational complexity.
Course Objectives: By the end of the course, the student should be familiar with context-free grammars as a mechanism for describing certain languages (for example, describing the syntax of programming languages), and with the corresponding models of computation, pushdown automata. He/she should be familiar with general models of computation such as Turing machines and the corresponding languages, and should understand how such models make it possible to formalize the study of decision problems and decision algorithms. He/she should understand the idea of solvability and unsolvability and the idea of reducing one problem (or one language) to another, and should be acquainted with examples of unsolvable decision problems.
Prerequisites: CSCI 335.
Homework: There will be regular homework assignments,
and homework will count 20% of the final grade. For the most
part
the assignments will be problems from the text. In order to
receive credit,
homework
must be turned in by the due date.
Evaluation Procedures and Criteria: The grade
will
be based on hour-exam scores, homework, and
final-exam
score. The overall exam grade is the larger of the two
following
numbers: i) the score obtained by weighting each hour-exam 24%
and the final exam 28%; ii) the score obtained by weighting each
of the two highest hour-exams 28% and
the final 44%. The final total will be obtained by
weighting
the exam grade 80% and the homework 20%.
At the end of the semester, an overall percentage of 85 or higher will be an A, 70 or higher will be at least a B, and 55 or higher will be at least a C. The cutoffs for these letter grades may, but will not necessarily, drop slightly below these numbers.
Makeup exams will normally not be given, and makeup exams after the class has taken the exam will almost never be given. If you miss an exam, then your exam grade will be computed the second way described above (counting the other two and the final more), and the exam you miss will be the exam that is dropped.
Attendance: Although class attendance is not required, you are strongly encouraged to attend class; you are responsible for what goes on in class, including any topics that are not in the text but are discussed in class, and any changes in dates or policies described here.
Course Calendar: The three exams are scheduled for Friday, February 8; Wednesday, March 19; and Wednesday, April 23. The final exam is scheduled for Friday, May 9, at 10:30AM. Tentatively, we will plan to cover Chapters 6 through 11 of the text, except that Sections 6.5, 6.6, 7.5, and 10.4 will be discussed only briefly if at all.
Required Student Resources: The text is Martin, Introduction to Languages and the Theory of Computation, Third Edition, McGraw-Hill, 2003.
Special Needs: Any students with disabilities or other special needs who need special accommodations in this course are invited to share these concerns or requests with the instructor as soon as possible.
Academic Responsibility Policy: All work in this course must be completed in a manner consistent with NDSU University Senate Policy, Section 335: Code of Academic Responsibility and Conduct (http://www.ndsu.nodak.edu/policy/335.htm).